当前位置：文档库 › 最优化方法教案(1)

最优化方法教案(1)

第一章最优化问题与数学预备知识

最优化分支：线性规划，整数规划，几何规划，非线性规划，动态规划。又称规划论。

应用最优化方法解决问题时一般有以下几个特点： 1. 实用性强

2. 采用定量分析的科学手段

3. 计算量大，必须借助于计算机

4. 理论涉及面广

应用领域：工业，农业，交通运输，能源开发，经济计划，企业管理，军事作战……。

§1.1 最优化问题实例

最优化问题：追求最优目标的数学问题。经典最优化理论：

（1）无约束极值问题：),,,(opt 21n x x x f

（),,,(m in

21n x x x f 或),,,(m ax 21n x x x f ）

其中，

),,,(21n x x x f 是定义在n 维空间上的可微函数。

解法（求极值点）：求驻点，即满足

),,(0),,(0

),,(1

1121n x n x n x x x f x x f x x f n

并验证这些驻点是否极值点。

（2）约束极值问题：),,,(opt 21n x x x f

s.t.

)(,,2,1,0),,,(21n l l j x x x h n j

解法：采用Lagrange 乘子法，即将问题转化为求Lagrange 函数

)

,,(),,,(),,;,,,(11

21121n j j l

j n l n x x h x x x f x x x L 的无约束极值问题。

近代最优化理论的实例：

例1 (生产计划问题) 设某工厂有3种资源B 1，B 2，B 3，数量各为b 1，b 2，b 3，要生产10种产品A 1，…，A 10 。每生产一个单位的A j 需要消耗B i 的量为a ij ，根据合同规定，产品A j 的量不少于d j ，再设A j 的单价为c j 。问如何安排生产计划，才能既完成合同，又使总收入最多？（线性规划问题）

数学模型：设A j 的计划产量为 j x ，z 为总收入。目标函数： max

j j j x c z

约束条件：

,,2,1,3,2,1,10

j d x i b x a j j

j i j ij

线性规划问题通常采用单纯形法来求解。

例2 (工厂设址问题) 要在m 个不同地点计划修建m 个规模不完全相同的工厂，他们的生产能力分别是m a a a ,,21 （为简便起见，假设生产同一种产品），

第i 个工厂的建设费用

m i f i ,,2,1, 。又有n 个零售商店销售这种产品，对

这种产品的需求量分别为n b b b ,,21

，从第i 个工厂运送一个单位产品到第

个零售商店的运费为c ij 。试决定应修建哪个工厂，使得既满足零售商店的需求，又使建设工厂和运输的总费用最小。（混合整数规划问题）

数学模型：设第i 个工厂运往第j 个零售商店的产品数量为x ij （i=1，…，m ；j=1，…，n ），且

m i i y i ,,1,

,1 否则个工厂如果修建第

目标函数： min 11

i n j ij ij i i x c y f z 约束条件：

j m i x m i y n

j b x m i y a x ij i m i j ij n

j i i ij ,,1;,,1 ,0,,1 ,1 0,,1 ,,,1 ,11 或

整数规划问题通常可用分枝定界法或割平面法来求解。

例3 (投资计划问题) 假设某一个生产部门在一段时间内可用于投资的总金额为a 亿元，可供选择的项目总共有n 个，分别记为1，2，…n 。并且已知对第j 个项目的投资总数为j a 亿元，而收益额总数为j c 亿元。问如何使用资金a 亿元，才能使单位投资获得的收益最大。（非线性规划问题）

数学模型：设n j j x j ,,1 ,

,1 否则个项目投资对第目标函数：

max 1

j j

j n

j j

a x c z

约束条件：

n j x a x a j

j j j ,,1 ,1 01

或

非线性规划问题的求解方法很多，是本课的重点。

动态规划是解决“多阶段决策过程”的最优化问题的一种方法，基于“Bellman 最优性原理”，例如：资源分配问题，生产与存储问题。

例4 (多参数曲线拟合问题)已知热敏电阻R 依赖于温度T 的函数关系为

21x T x e

x R （*）

其中，321,,x x x 是待定的参数，通过实验测得T 和R 的15组数据列表如下，如何确定参数321,,x x x ？

建立数学模型：测量点),(i i R T 与曲线)(T R 对应的点产生“偏差”，即

[32

i x T x i i e

x R S

得如下无约束最优化问题：

[)(min 32

i x T x i i e

x R x f

通常采用最小二乘法。

§1.2 最优化问题的数学模型

一、最优化问题的数学模型 1. 定义1：设向量T 21T 21],,,[ ,],,,[m m b b b a a a .

若),,2,1( m i b a i i ，则记或；若),,2,1( m i b a i i

，则记或

。

2．一般模型：

))(m ax )((m in ),,,()(opt 21x f x f x x x f x f n 或，（1）

s.t. )3( ,,1 ,0)()2(

,,1 ,0)(l j x h m i x S j

其中，T

21],,,[n

x x x x ；)( x f ，)(x S i ，)(x h j 是关于变量n x x x ,,,21 的实值连续函数，一般可假定它们具有二阶连续偏导数。

3．向量模型：

))(m ax )((m in )(opt x f x f x f 或，（1）

s.t.

)3( ,,1 ,0)()2(

,,1 ,0)(l j x h m i x S

其中，T 21],,,[n x x x x

，)(x f 称为目标函数；

)( x S i ，)( x h j 称为约束函数；

满足约束条件（2），（3）的点称为容许解或容许点（或可行解）；可行解的全体称为容许域（或可行域），记为R ；

满足（1）的容许点称为最优点或最优解（或极小（大）点），记为*

x ；)

( x f 称为最优值；

不带约束的问题称为无约束问题，带约束的问题称为约束问题；若目标函数

)(x f ，约束函数)( x S i ，)( x h j 都是线性函数，则称为线性

规划；若其中存在非线性函数，则称为非线性规划；

若变量只取整数，称为整数规划；若变量只取0，1，称为0—1规划。注：因0)( x h 0)( x h ，0)(- x h ，则最优化问题一般可

写成

0)( ..)

(opt x S t s x f

二、最优化问题的分类

动态规划

非线性规划线性规划约束问题维问题一维问题无约束问题静态规划最优化问题n

§1.3 二维问题的图解法

例1.

32m ax 21x x z

0,164 82 ..2

1121

x x x x x t s

解：1. 由全部约束条件作图，求出可行域R ：凸多边形OABC 2. 作出一条目标函数的等值线：设 63221

x x ，作该直线即为一条目

标函数的等值线，并确定在可行域内，这条等值线向哪个方向平移可使z 值增大。

3. 平移目标函数等值线，做图求解最优点，再算出最优值。顶点)2,4(B 是最优点，即最优解T x

]24[

，最优值14 z 。

分析：线性规划问题解的几种情况（1）有唯一最优解（上例）；

（2）有无穷多组最优解：目标函数改为

42m ax 21x x z

（3）无可行解：增加约束52

x ，则 R 。

（4）无有限最优解（无界解）：例

m ax 21x x z

0,2- 4

2 ..2

12121

x x x x x x t s

结论：（1）线性规划问题的可行域为凸集，特殊情况下为无界域或空集。（2）线性规划问题若有最优解，一定可在其可行域的顶点上得到。

例2.

1)-()2m in(2221x x

0,05 05 ..212122

x x x x x x x t s

解：目标函数等值线： 11)-()2(2221 x x

C 为最优点 0

52122

x x x x x ，得T x ]14[ 定义2：在三维及三维以上的空间中，使目标函数取同一常数的点集

是常数r r x f x ,)( 称为等值面。

§1.4 预备知识

（一）线性代数一、 n 维向量空间n

1. 向量的内积：设T 21T 21],,,[ ,],,,[n n y y y y x x x x ，则

内积为

i i

i n n T

y x y x y x y x y x 1

2211

2. 向量的范数（或长度或模）：设n

x R ，若实数x

具有以下

性质：（1）

,0 x 当且仅当0 x 时0 x ；

（2）R , x x ；

（3

）n y x y x y x R ,, .

则称

为n

R 上的向量的范数，简记为

。

规定了向量范数的线性空间n

3. 常见的向量范数

向量的p L 范数：

i p i p

x x

， p 1

三个重要的向量范数：

1x ，2x

，

注：若无特殊说明，本书中的

指的是

。

4. y x ,间的距离：y

x 与y 正交：0 y x T

若非零向量组)

1(x ，…，)

(k x

的向量两两正交，称它们是正交向量组。

6. 标准正交基：)

1(e ，…，)

(n e

是n 个正交的单位向量，即

j i j i e

j i T

,0 ,1)

()(

二、特征值和特征向量

定义：设

A 为n 阶方阵，存在数和非零向量x ，使

x Ax ，

则称为矩阵A 的特征值，非零向量x 为矩阵A 属于特征值的特征向量。三、正定矩阵

定义：设A 为n 阶实对称方阵，若对任意非零向量x ，均有0 Ax x T ，

则称Ax x

为正定二次型，A 为正定矩阵，记0 A ；若0 Ax x T ，半正定

二次型，

A 为半正定矩阵，记0 A 。

类似有负定（半负定）二次型，负定（半负定）矩阵的概念。性质：实对称方阵

A 为正定矩阵（负） A 的特征值均为正（负）

A 的各阶顺序主子式均为正（奇数阶为

负，偶数阶为正）

实对称方阵

A 为半正定矩阵 A 的特征值均非负

A 的各阶顺序主子式均为非负

（二）数学分析

一、梯度和海色（Hesse ）矩阵

1. 多元函数的可微性可微定义：设1R R : n D f ，D x 0，若存在n 维向

量l ，对n p

R 0 ，总有

0)()(lim T 000 p

p l x f p x f p （1）则称函数

)(x f 在点0x 处可微。

式（1）等价于

p p l x f p x f 0)()(T 00 （2）

其中， p 0

是

的高阶无穷小。

定理1：（可微的必要条件）若函数)(x f 在点0x 处可微，则)(x f 在该点

关于各个变量的偏导数存在，且

02010)(,,)(,)(

n x x f x x f x x f l

2. 梯度（1）概念梯度：令

)(,,)(,)()(

n x x f x x f x x f x f

则称)(x f 为n 元函数

)(x f 在x 处的梯度（或记为)(grad x f ）。又称为

)(x f 关于x 的一阶导数。

注：式（2）等价于

p x f x f p x f 0)()()(T 000 （3）

等值面：在三维和三维以上的空间中，使目标函数取同一

数值的点集},)({R r r x f x

称为等值面（曲面）。

方向导数：设

1R R : n f 在点0x 处可微，向量n p R 0 ，e 是p

方向上的单位向量，则极限

x f te x f t )

()(lim 000

称为函数

)(x f 在点0x 处沿p 方向的方向导数，记作p

x f )

(0。

方向导数的几何解释：方向导数p

x f )

(0表示函数)(x f 在点0x 处沿方向

的

p 的变化率。

函数的下降（上升）方向：设

1R R : n f 是连续函数，点n x R 0 ，

n p R 0 为一方向，若存在0 ，对于),0( t ，都有

)()(00x f tp x f （)()(00x f tp x f ）

则称

p 方向是函数)(x f 在点0x 处的下降（上升）方向；

结论

1：若方向导数

(0 p

x f ，则方向p 是)(x f 在点0x 处的下降方向；若方向导数

(0 p

x f ，则方向p 是)(x f 在点0x 处的上升方向；

（2）性质【性质1】：梯度)(0x f

为等值面)()(0x f x f 在点0x 处的

切平面的法矢（向）量。

【性质2】：梯度方向是函数具有最大变化率的方向。定理2：设

1R R : n f 在点0x 处可微，则方向导数

cos )()()

(0T 00x f e x f p

x f

其中，e 是p 方向上的单位向量，为梯度与p 的夹角。

结论2：1）与梯度)(0x f

方向成锐角的方向是上升方向；与梯度)

(0x f 方向成钝角的方向是下降方向；

2）梯度方向是函数值上升最快的方向，称为最速上升方向；负梯度方向是函数值下降最快的方向，称为最速下降方向。

（3）几种特殊函数的梯度公式

（1）0

C ，C 为常数；

（2）b x b )(T

，其中 T

21,,,n b b b b ；

（3）

x x x 2)(T ；（4）若Q 是对称方阵，则Qx Qx x 2)(T

例

3. 泰勒（Taylor ）公式与Hesse 矩阵性质1：设

R R :)( n x f 具有一阶连续偏导数，则

p f x f p x f T )()()( （*）

其中，)10( p x ，即介于x 与 p x 之间。

性质2：设

R R :)( n x f 具有二阶连续偏导数，则

p f p p x f x f p x f )(2

1)()()(2

T T

（*‘

）

其中

222

222122122122122)()()()()

()

()()

()()(n n n n n x x f x x x f x x x f x x x f x x f x

x x f x x x f x x x f x x f x f

为函数

)(x f 关于x 的二阶导数，称为)(x f 的海色（Hesse ）矩阵。

结论1：当2)(C x f 时，

n j i x x x f x x x f i

j j i ,,1, ,)()(2

2 （即海色矩阵对称）。

注1：1) 设向量函数T 21)](,),(),([)

(x g x g x g x g m 时，

n m n

m m x x g x x g x x g x x g x x g x x g x x g x x g x

x g x g )()()()()()

()()

()

()(212222

11121

称为向量函数)(x g 在点x 处的导数（梯度）。

2) 向量函数

T 21)](,),(),([)(x g x g x g x g m 在点0x 处可微是指所

有分量都在点0x 处可微。

关于向量函数常见的梯度：（1）n C

0 ，n C R ；（2）n I x )

(，n x R ；

（3）,)

(T A Ax n m A R

（4）设)()(0

tp x f t ，其中1R R : n f ，1

1R R : ，则 p tp x f t T 0)()( ，p tp x f p t )()(02T

（三）极小点的判定条件（求)(min x f ）一、基本概念

1. 点0x 的邻域： 0, ),(0

0 x

x x x N

2. 局部极小点：设1R R : n D f . 若存在点D x *和数0 ，

对D x

N x ),(*

都有)()(*x f x f ，则称*x 为)(x f 在D 上的（非

严格）局部极小点；若)()(*x f x f （*x x ），则称*

x 为)(x f 在D 上的

严格局部极小点。

3. 全局极小点：设

1R R : n D f . 若存在点D x *，对于

D x 都有)()(*

x f x f ，则称*x 为)(x f 在D 上的（非严格）全局极

小点；若)()(*x f x f （*x x ），则称*

x 为)(x f 在D 上的严格全局极小

点。

性质：全局极小点必是局部极小点；但局部极小点不一定是全局极小点。

类似有极大点的概念。因)](min[)(max x f x f ，本书主要给出极小

问题。

4. 驻点：设1R R : n D f 可微，D x *，若0)(* x f ，

则称点*

x 为

)(x f 的驻点或临界点。

二、极值的条件

定理1（一阶必要条件）设1R R : n D f 具有一阶连续偏导数，*

x 是D 的内点，若*

x 是

)(x f 的局部极小点，则

0)(* x f

定理2（二阶必要条件）设

1R R : n D f 具有二阶连续偏导数，若*

是

D 的内点且为)(x f 的局部极小点，则)(*

2x f 是半正定的，即对

n p R 恒有

02T p x f p )(*

例

定理3（二阶充分条件）设

1R R : n D f 具有二阶连续偏导数，*x 为

D 的内点，且0)(* x f ，若)(*

2x f 正定，则*x 为)(x f 的严格局部极

小点。

（四）凸函数与凸规划一、凸集

1. 凸集的定义：一个n 维向量空间的点集D 中任意两点的连线仍属于这个集合，即对D x x 21,，有

)10( )1(21 D x x

则称该点集D 为凸集。

2. 凸集的性质：（1）凸集的交集仍是凸集)(21D D ；

（2）数乘凸集仍是凸集} ,{D x x y y D ；

（3）凸集的和集仍是凸集}, ,{2121D z D x z x y y D D

特别规定，空集是凸集。 3. 超平面：设n R

且R ,0 b ，则集合

}R ,{T n x b x x H 称为n R 中的超平面，

称为该超平面的法

向量，即b x a x a x a H

n n 2211:；（是凸集）

半空间：集合

}R ,{T n

x b x x 称为n R 中的一个半空间。超球：

r x 。

4. 凸组合：设

l x x x ,,,21 为n

R 中的l 个点，若存在l

a a a ,,,21

且

1 ,101

i i i a a ，使得

l l x a x a x a x 2211

则称x 为l x x x ,,,21

的凸组合。

若l a a a ,,,21

均为正，则称为严格凸组合。

5. 顶点（或极点）：设D 是凸集，D x ，若x 不能用D 内不同两点1x 和

2x 的凸组合表示，即)10( )1(21 x x x ，则称x 为D 的顶点。

二、凸函数

1. 凸函数：设

1R R : n D f ，D 是凸集，若对D x x 21,

及]1

,0[ ，都有 )( )(1)())1((2121x f x f x x f

则称

)(x f 为凸集D 上的凸函数；若

)10( )( )(1)())1((2121 x f x f x x f

则称

)(x f 为凸集D 上的严格凸函数。

类似有凹函数的定义。

2.几何意义：函数图形上连接任意两点的线段处处都在函数图形的上方。

3. 性质性质1：)(x f 为凸集D 上的凸函数，0 k ，则)(x kf 也为D 上

的凸函数。

性质2：两个凸函数的和仍是凸函数。))()((21x f x f

推论1：凸集D 上有限个凸函数

)(x f i 的非负线性组合

0 ),()(11 i m m k x f k x f k

仍为D 上的凸函数。

性质3：若)(x f 为凸集D 上的凸函数，则对R ，)(x f 的

水平集} ,)({D x x f x D

是凸集。

性质4：

)(x f 为凸集D 上的凹函数 )(x f 为凸集D 上的凸函数。

4. 凸函数的充分必要条件定理1（一阶条件）设1R R : n D f 可微，D 是凸集，则

（1）

)(x f 为凸函数对D x x 21,，恒有

)-()( )()(12T 112x x x f x f x f

（2）

)(x f 为严格凸函数对D x x 21,，21x x 恒有

)-()( )()(12T 112x x x f x f x f

定理2（二阶条件）设1R R : n D f 具有二阶连续偏导数，D 为开

凸集，则（1）

)(x f 在D 内为凸函数对D x ，)(2x f 是半正定的；

（2）若)(2

x f 正定，则)(x f 在D 内为严格凸函数。

特殊地，n 元二次函数为C x b Qx x x f T T

1)(（Q 为对称矩阵）；

若Q 正定，则

)(x f 称为正定二次函数。

性质：正定二次函数是严格凸函数。（因为Q x f )(2

）

5. 凸函数的极值定理3 设1R R : n D f 为凸集D 上的凸函数，则

（1）

)(x f 的任一局部极小点*x 为全局极小点；

（2）若)(x f 具有二阶连续偏导数，且存在D x *，使0)(* x f ，

则*

x 为

)(x f 在D 上的全局极小点；

（3）若

)(x f 为严格凸函数，且全局极小点存在，则必唯一。

特殊：对于正定二次函数

C x b Qx x x f T T

1)(，有

b Qx x f )(，得唯一驻点b Q x 1* 为唯一的全局极小点。

6. 凸规划问题：非空凸集D 上的凸函数的极小化问题。考虑凸规划问题：)(min x f ，n

x R (1)

s.t.

)3( ,,1 ,0)()2(

,,1 ,0)(l j x h m i x S j

i 其中，)(x S i 为n

R 上的凹函数，)(x h j 为n

R 上的线性函数，

},,1;,,1,0)(,0)({l j m i x h x S x D j i 为凸集， 1R R : n D f 为D 上的凸函数。

注：线性函数既可视为凸函数，又可视为凹函数。二次规划：

C x b Qx x x f T T

1)(min

s.t.

d Cx p Ax 其中，n

x R ，

n m A ，n l C ，Q 半正定或正定。

（五）下降迭代算法

1. 下降迭代算法的步骤

（1）选择一个初始点0x ，令k ：=0

（2）检验k x 是否最优？若是，则停止迭代；若不是，则（3）确定一个下降方向

k p ：存在0 ，对0(,)t ，使得

k k k x f tp x f

（4）从点k x 出发，沿方向

k p 进行直线搜索（一维搜索），即求步长k t 使

k k k k k tp x f p t x f m in

（5）计算k k k k p t x x 1

，令k ：=k +1，转（2）

2. 直线搜索及其性质（1）简记

),(p x ls z ：

p t x z tp x f p t x f 00min 表示从点x 出发，沿方向

p 进行直线搜索，得到极小点z 。

（2）定理：设目标函数

)(x f 具有一阶连续偏导数，若),(p x ls z ，则

0)(T p z f

证明：（反正法）设T

0()f z p ，则

1）T 0()f z p ，此时p 是点z 的下降方向； 2）T

0()f z p ，此时p 是点z 的下降方向；

与),(p x ls z

矛盾。

3. 收敛速度

定义1：设序列}{k x 是线性赋范空间

},{R n

中的点列，n x R * ，若 0lim *

x x k k

则称序列}{k x 收敛于*

x ，记为*lim x x k

。定义2：设向量函数

21)(,),(),()(x f x f x f x f m ，n D

x R ，

若当00 x x

时，总有0)()(0 x f x f ，则称)(x f 在点0x 连续；

若

)(x f 在D 内每一点都连续，则称)(x f 在D 内连续。

特别地，m=1时，

)(x f 为数量函数，则

)()()()(00x f x f x f x f

定义3：设序列}{k x 收敛于

*x ，若存在与k 无关的数)1( 和

)0( ，使得当k 从某个)0(0 k 开始，都有

x x x k k

则称序列}{k x 收敛的阶为，或}{k x 为阶收敛。

当1 ，且10 时，称线性收敛或一阶收敛；当2

时，称二阶收敛；

当21

时，称超线性收敛。

4. 计算终止准则

计算终止准则根据相继两次迭代的结果

a. 根据相继两次迭代的绝对误差（不常用）

11 k k x x ，21)()( k k x f x f

b. 根据相继两次迭代的相对误差

311 k k k x x x ，411

)()

()( k k k x f x f x f

c. 根据目标函数梯度的模足够小

5)( k x f

54321,,,, 为给定的足够小的正数。

以上准则统称为Himmelblau 计算终止准则，简称H 终止准则。

第二章线性规划

§2.1 数学模型

一、线性规划的标准型

1. 繁写形式：n n x c x c x c z

2211m in

s.t.

0,, 2122112222212111212111n m

n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a

其中，m i b i

,,2,1 ,0 （否则，等式两端同乘以“-1”）。

2. 缩写形式： n

j j

j x c z

min

s.t.

n j x m i b x a j

i n

j j ij ,,2,1 , 0,,2,1,1

3. 向量形式：X C z

T min

s.t.

X b x p n

j j j

其中，T 21],,,[n c c c C

，T 21],,,[n x x x X ，T 21],,,[m b b b b ，

T 21],,,[mj j j j a a a p 。

4. 矩阵形式：X

C z

T min

s.t.

0X b AX 其中，

]

,,,[21212222111211n

mn m m n n p p p a a a a a a a a a A

《最优化方法》复习题(含答案)

附录5 《最优化方法》复习题 1、设n n A R ?∈是对称矩阵，,n b R c R ∈∈，求1()2 T T f x x Ax b x c =++在任意点x 处的梯度和Hesse 矩阵．解 2(),()f x Ax b f x A ?=+?=． 2、设()()t f x td ?=+，其中:n f R R →二阶可导，,,n n x R d R t R ∈∈∈，试求()t ?''．解 2()(),()()T T t f x td d t d f x td d ??'''=?+=?+． 3、设方向n d R ∈是函数()f x 在点x 处的下降方向，令 ()()()()() T T T T dd f x f x H I d f x f x f x ??=--???，其中I 为单位矩阵，证明方向()p H f x =-?也是函数()f x 在点x 处的下降方向．证明由于方向d 是函数()f x 在点x 处的下降方向，因此()0T f x d ?<，从而 ()()()T T f x p f x H f x ?=-?? ()()()()()()()() T T T T T dd f x f x f x I f x d f x f x f x ??=-?--???? ()()()0T T f x f x f x d =-??+?<，所以，方向p 是函数()f x 在点x 处的下降方向． 4、n S R ?是凸集的充分必要条件是12122,,,,,,,,m m m x x x S x x x ?≥?∈L L 的一切凸组合都属于S ．证明充分性显然．下证必要性．设S 是凸集，对m 用归纳法证明．当2m =时，由凸集的定义知结论成立，下面考虑1m k =+时的情形．令1 1k i i i x x λ+==∑，其中,0,1,2,,1i i x S i k λ∈≥=+L ，且1 1 1k i i λ+==∑．不妨设11k λ+≠（不然1k x x S +=∈，结论成立），记11 1k i i i k y x λλ=+=-∑ ，有111(1)k k k x y x λλ+++=-+，

《最优化方法》复习题

《最优化方法》复习题一、简述题 1、怎样判断一个函数是否为凸函数. （例如: 判断函数212 2 212151022)(x x x x x x x f +-++=是否为凸函数） 2、写出几种迭代的收敛条件. 3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大M 法及二阶段法）. 见书本61页(利用单纯形表求解); 69页例题 (利用大M 法求解、二阶段法求解); 4、简述牛顿法和拟牛顿法的优缺点. 简述共轭梯度法的基本思想. 写出Goldstein 、Wolfe 非精确一维线性搜索的公式。 5、叙述常用优化算法的迭代公式．（1）0.618法的迭代公式：(1)(), ().k k k k k k k k a b a a b a λτμτ=+--??=+-? （2）Fibonacci 法的迭代公式：111(),(1,2,,1)() n k k k k k n k n k k k k k n k F a b a F k n F a b a F λμ---+--+? =+-?? =-? ?=+-?? L ．（3）Newton 一维搜索法的迭代公式： 1 1k k k k x x G g -+=-．（4）推导最速下降法用于问题1min ()2 T T f x x Gx b x c = ++的迭代公式： 1()T k k k k k T k k k g g x x f x g G gx +=-? （5）Newton 法的迭代公式：211[()]()k k k k x x f x f x -+=-??．（6）共轭方向法用于问题1min ()2 T T f x x Qx b x c = ++的迭代公式： 1()T k k k k k T k k f x d x x d d Qd +?=-．二、计算题双折线法练习题课本135页例3.9.1 FR 共轭梯度法例题：课本150页例4.3.5 二次规划有效集：课本213页例6.3.2,

北航最优化方法大作业参考

1 流量工程问题 1.1 问题重述定义一个有向网络G=(N,E)，其中N是节点集，E是弧集。令A是网络G的点弧关联矩阵，即N×E阶矩阵，且第l列与弧里(I,j)对应，仅第i行元素为1，第j行元素为-1，其余元素为0。再令b m=(b m1,…,b mN)T，f m=(f m1,…,f mE)T，则可将等式约束表示成： Af m=b m 本算例为一经典TE算例。算例网络有7个节点和13条弧，每条弧的容量是5个单位。此外有四个需求量均为4个单位的源一目的对，具体的源节点、目的节点信息如图所示。这里为了简单，省区了未用到的弧。此外，弧上的数字表示弧的编号。此时，c=((5,5…,5)1 )T， ×13 根据上述四个约束条件，分别求得四个情况下的最优决策变量x=((x12,x13,…,x75)1× )。 13 图 1 网络拓扑和流量需求

1.2 7节点算例求解 1.2.1 算例1（b1=[4;-4;0;0;0;0;0]T）转化为线性规划问题： Minimize c T x1 Subject to Ax1=b1 x1>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x1*=[4 0 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x1=20 1.2.2 算例2（b2=[4;0;-4;0;0;0;0]T） Minimize c T x2 Subject to Ax2=b2 X2>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x2*=[0 4 0 0 0 0 0 0 0 0 0 0 0]T 对应的最优值c T x2=20 1.2.3 算例3（b3=[0;-4;4;0;0;0;0]T） Minimize c T x3 Subject to Ax3=b3 X3>=0 利用Matlab编写对偶单纯形法程序，可求得: 最优解为x3*=[4 0 0 0 4 0 0 0 0 0 0 0 0]T 对应的最优值c T x3=40

最优化方法试题

《最优化方法》试题一、填空题 1.设()f x 是凸集n S R ?上的一阶可微函数，则()f x 是S 上的凸函数的一阶充要条件是（），当n=2时，该充要条件的几何意义是（）； 2.设()f x 是凸集n R 上的二阶可微函数，则()f x 是n R 上的严格凸函数（）（填‘当’或‘当且仅当’）对任意n x R ∈，2()f x ?是（）矩阵； 3.已知规划问题22211212121212min 23..255,0z x x x x x x s t x x x x x x ?=+---?--≥-??--≥-≥?，则在点55(,)66T x =处的可行方向集为（），下降方向集为（）。二、选择题 1.给定问题222121212min (2)..00f x x s t x x x x ?=-+??-+≤??-≤?? ，则下列各点属于K-T 点的是（） A) (0,0)T B) (1,1)T C) 1(,22 T D) 11(,)22T 2.下列函数中属于严格凸函数的是（） A) 211212()2105f x x x x x x =+-+ B) 23122()(0)f x x x x =-< C) 2 222112313()226f x x x x x x x x =+++- D) 123()346f x x x x =+- 三、求下列问题

()22121212121211min 51022 ..2330420 ,0 f x x x x x s t x x x x x x =+---≤+≤≥ 取初始点()0,5T 。四、考虑约束优化问题 ()221212min 4..3413f x x x s t x x =++≥ 用两种惩罚函数法求解。五．用牛顿法求解二次函数 222123123123()()()()f x x x x x x x x x x =-++-++++- 的极小值。初始点011,1,22T x ??= ???。六、证明题 1.对无约束凸规划问题1min ()2 T T f x x Qx c x =+，设从点n x R ∈出发，沿方向n d R ∈ 作最优一维搜索，得到步长t 和新的点y x td =+ ，试证当1T d Q d = 时， 22[() ()]t f x f y =-。 2.设12*** *3(,,)0T x x x x =>是非线性规划问题()112344423min 23..10f x x x x s t x x x =++++=的最优解，试证*x 也是非线性规划问题 144423* 123min ..23x x x s t x x x f ++++=的最优解，其中****12323f x x x =++。

最优化原理大作业

基于粒子群算法的神经网络在电液伺服系统中的应用摘要：由于人工神经网络在解决具有非线性、不确定性等系统的控制问题上具有极大的潜力，因而在控制领域正引起人们的极大关注，并且已在一些响应较慢的过程控制中获得成功应用。由于电液伺服系统属于非线性系统，因此本文利用神经网络控制电液伺服系统，并利用粒子群优化算法训练该神经网络的权值。通过对神经网络的优化实现对电液伺服系统的控制。关键词：神经网络电液伺服系统粒子群算法优化近年来，由于神经网络具有大规模并行性、冗余性、容错性、本质的非线性及自组织自学习自适应能力，所以已成功地应用于众多领域。但在具有复杂非线性特性的机电设备的实时控制方面，虽然也有一些神经网络技术的应用研究，但距实用仍有一段距离。电液伺服系统就属于这类设备[1]。神经网路在用于实时控制时，主要是利用了网络所具有的其输人——输出间的非线性映射能力。它实际上是通过学习来逼近控制对象的动、静态特性。也就是构造实际系统的神经网络模型[2]。本文利用神经网络控制一电液伺服系统，并利用粒子群优化算法训练该神经网络的权值，将结果与BP神经网络控制该系统的结果进行比较。从而得在电液伺服系统中引入神经网络是可行的。 1、粒子群算法粒子群优化算法(Particle Swarm optimization, PSO)是一种进化计算技术, 由Eberhart博士和kennedy博士发明, 源于对鸟群捕食的行为研究, 粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解[3]。算法最初受到飞鸟和鱼类集群活动的规律性启发，利用群体智能建立了一个简化模型，用组织社会行为代替了进化算法的自然选择机制，通过种群间个体协作来实现对问题最优解的搜索[4]。在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置 v[]=v[]+c1*rand()*(pbest[]-present[]) + c2*rand()*(gbest[]-present[]) present[]=persent[]+v[] 式中ω为惯性权重，ω取大值可使算法具有较强的全局搜索能力，ω取小值则算法倾向于局部搜索。一般的做法是将ω初始取0.9并使其随迭代次数的增加而线性递减至0.4，这样就可以先侧重于全局搜索，使搜索空间快速收敛于某一区域，然后采用局部精细搜索以获得高精度的解；c1、c2为两个学习因子，一般取为2；randl和rand2为两个均匀分布在(0，l)之间的随机数；i=1，2，?，m；k=1，2，?，d。另外，粒子在每一维的速度Vi都被一个最大速度Vmax所限制。如果当前粒子的加速度导致它在某一维的速度超过该维上的最大速度Vmax，则该维的速度被限制为最大速度[5]。粒子群算法流程如下： (一)初始化粒子群。设群体规模为m，在允许的范围内随机设置粒子的初始位置和速度。 (二)评价每个粒子的适应值。 (三)调整每一个粒子的位置和速度。 (四)如果达到最大迭代次数genmax或误差达到最初设定数值终止迭代，否则返回(2)。 2、神经网络神经网络一般由输入层、隐含层、输出层组成。对于输入信号，先向前传播到隐节点，经过节点作用函数后，再把隐节点的输出信息传播到输出节点，最后输出结果。节点的作用函数通常选取S 型函数f（x）=1/（1+e-x）。神经网络算法的学习过程分为正

天津大学《最优化方法》复习题(含答案)

天津大学《最优化方法》复习题（含答案）第一章概述(包括凸规划) 一、判断与填空题 1 )].([arg )(arg min max x f x f n n R x R x -=∈∈ √ 2 {}{} .:)(m in :)(m ax n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题)(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的严格局部最优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍

属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法 A 为下降算法，则对{} ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ . 13 算法迭代时的终止准则（写出三种）：_____________________________________。 14 凸规划的全体极小点组成的集合是凸集。 √ 15 函数R R D f n →?:在点k x 沿着迭代方向}0{\n k R d ∈进行精确一维线搜索的步长k α，则其搜索公式

最优化方法大作业答案

1.用薄钢板制造一体积5m 3，长度不小于4m ，无上盖的货箱，要求钢板耗量最小。确定货箱的长x 1、宽x 2和高x 3。试列出问题的数学模型。解：min 32312122x x x x x x z ++= s.t 5321=x x x 41≥x 0,,321≥x x x 2.将下面的线性规划问题表示为标准型并用单纯形法求解 max f=x 1+2x 2+x 3 s ．t ．2x 1+x 2-x 3≤2 -2x 1+x 2-5x 3≥-6 4x 1+x 2+x 3≤6 x i ≥0 i=1，2，3 解：先化标准形： Min 321x x x z -+= 224321=+-+x x x x 6525321=++-x x x x 646321=+++x x x x 列成表格：

1 2 1 610011460105122001112----- 可见此表已具备1°，2°，3°三个特点，可采用单纯形法。首先从底行中选元素-1，由2/2,6/2,6/4最小者决定选第一行第一列的元素2，标以记号，迭代一次得 1 2 1 2102310401162010021212 11-------- 再从底行中选元素-2/3，和第二列正元素1/2，迭代一次得 1 2 12 32 30 210231040116201002121211- ------ 再从底行中选元素-3，和第二列正元素2，迭代一次得 4 2 3 3 410120280114042001112--- 再迭代一次得 10 2 30 2 10 6 221023 1010213000421021013-- 选取最优解：

(完整版)机械优化设计试卷期末考试及答案

第一、填空题 1.组成优化设计的数学模型的三要素是设计变量、目标函数和约束条件。 2.可靠性定量要求的制定，即对定量描述产品可靠性的参数的选择及其指标的确定。 3.多数产品的故障率随时间的变化规律，都要经过浴盆曲线的早期故障阶段、偶然故障阶段和耗损故障阶段。 4.各种产品的可靠度函数曲线随时间的增加都呈下降趋势。 5.建立优化设计数学模型的基本原则是在准确反映工程实际问题的基础上力求简洁。 6.系统的可靠性模型主要包括串联模型、并联模型、混联模型、储备模型、复杂系统模型等可靠性模型。 7. 函数f(x 1,x 2)=2x 12 +3x 22-4x 1x 2+7在X 0=[2 3]T 点处的梯度为，Hession 矩阵为。（2.）函数()22121212,45f x x x x x x =+-+在024X ??=????点处的梯度为120-?? ????，海赛矩阵为2442-???? -?? 8.传统机械设计是确定设计；机械可靠性设计则为概率设计。 9.串联系统的可靠度将因其组成单元数的增加而降低，且其值要比可靠度最低的那个单元的可靠度还低。 10.与电子产品相比，机械产品的失效主要是耗损型失效。 11. 机械可靠性设计揭示了概率设计的本质。 12. 二元函数在某点处取得极值的充分条件是()00f X ?=必要条件是该点处的海赛矩阵正定。 13.对数正态分布常用于零件的寿命疲劳强度等情况。 14.加工尺寸、各种误差、材料的强度、磨损寿命都近似服从正态分布。 15.数学规划法的迭代公式是 1k k k k X X d α+=+ ，其核心是建立搜索方向，模型求解两方面的内容。 17.无约束优化问题的关键是确定搜索方向。 18.多目标优化问题只有当求得的解是非劣解时才有意义，而绝对最优解存在的可能性很小。 19.可靠性设计中的设计变量应具有统计特征，因而认为设计手册中给出的数据

北京理工大学级数学专业最优化方法期末试卷试题A卷MT.doc

课程编号 : 0 7 0 0 0 2 0 3 北京理工大学 2 0 0 7 - 2 0 0 8 学年第二学期 2005 级数学专业最优化方法终考试卷（ A 卷） 1． (20 分 )某化工厂有三种资源 A 、 B 、 C ，生产三种产品甲、乙、丙，设甲、乙、丙的产量分别为 x 1,x 2,x 3 ,其数学模型为： max z 3 x 1 2 x 2 5 x 3 1 2 x 2 3 430 ( A 资源限制 ) x x 3 x 1 2 x 3 460 ( B 资源限制 ) s.t 4 x 2 420 (C 资源限制 ) x x 1 , x 2 , x 3 0 请回答如下问题：（ 1）给出最优生产方案；（ 2）假定市场信息表明甲产品利润已上升了一倍，问生产方案应否调整？（3）假定增加一种添加剂可显着提高产品质量，该添加剂的资源限制约束为： x 1 2 x 2 3x 3 800 问最优解有何变化？ 2． (12 分 )用 Newton 法求解 min f ( x ) 4 x 12 x 22 2 x 12 x 2 ，初始点取为 x 0 (1, 1)T ，迭代一步。 3．(10 分 )用 FR 共轭梯度法求解三个变量的函数 f ( x ) 的极小值，第一次迭代的搜索方向为 p 0 (1, 1,2)T ，沿 p 0 做精确线搜索，得 x 1 ( x 11 , x 21 , x 31 )T ，设 f ( x 1 ) 2, f ( x 1 ) 2 ，求从 x 1 出发的搜索方向 p 1 。 x 11 x 21 4． (15 分 ) 给定下面的 BFGS 拟 Newton 矩阵修正公式： H k 1 ( I s k y k T )H k ( I s k y k T )T s k s k T ， y k T s k y k T s k y k T s k 其中 s k x k 1 x k , y k g k 1 g k 用对应的拟 Newton 法求解： min f ( x ) x 1 2 2x 1 x 2 2 x 22 4 x 1 ，初始点取为 x 0 (0,0) T ， H 0 I 。 5． (15 分 )写出问题取得最优解的 Kuhn-Tucker （ K － T ）必要条件，并通过 K － T 条件求出问题 K － T 点及相应 Lagrange 乘子。 6(12 分 )．求约束问题在 x (0,0) T 及 x 2 (1,0) T 处的下降方向集合、可行方向集合以及可行下降方向集合，并画图表示出来 1 7（ 8 分）考察优化问题 min f ( x ) s.t. x ， D 设 D 为凸集， f ( x ) 为 D 上凸函数，证明： f ( x) 在 D 上取得极小值的那些点构成的集合是凸集。 8（ 8 分）设 min f ( x ) 1 x T Ax b T x c ，其中 A 为对称正定矩阵， x * 为 f ( x ) 的极小值点，又设 x 0 ( x*) 可表示为 2 x 0 x * p ，其中 R 1， p 是 A 对应于特征值的特征向量，证明：若从 x 0 出发，沿最速下降方向做精确一维搜索，则一步达到极小值点。课程编号 :07000203 北京理工大学 2008-2009 学年第一学期 2006 级数学专业最优化方法终考试卷（ A 卷） 1． (15 分 ) 用单纯形法求解线性规划问题 2． (10 分 )写出线性规划问题的对偶问题并证明该对偶问题没有可行解。 3． (15 分 )考虑用最速下降法迭代一步 min f ( x) x 12 2x 22 ，初始点取为 x 0 ( 1, 1)T 。（ 1）采用精确一维搜索；（ 2）采用 Wolfe 条件进行不精确一维搜索，其中 0.1, 0.9 。 4． (15 分 )用 DFP 拟牛顿法求解 min f ( x) x 12 2x 22 初始点取为 x 0 1 ，初始矩阵 H 0 2 1 。 1 1 1 5． (15 分 )证明集合 S { x | x 1 2x 2 4, 2x 1 x 2 6} 是凸集，并计算原点 (0,0) 到集合 S 的最短距离。 6． (15 分 ?) 考虑问题（1）用数学表达式写出在点 ( 1 , 5)T 处的下降可行方向集。 3 3 （ 2）假设当前点在 (0,0) T 处，求出用投影梯度法进行迭代时当前的下降可行方向（搜索方向）。 7（ 7 分）证明：在精确一维搜索条件下，共轭梯度法得到的搜索方向是下降方向。

最优化方法大作业答案

武工院你们懂的 1.用薄钢板制造一体积5m 3，长度不小于4m ，无上盖的货箱，要求钢板耗量最小。确定货箱的长x 1、宽x 2和高x 3。试列出问题的数学模型。解：min 32312122x x x x x x z ++= s.t 5321=x x x 41≥x 0,,321≥x x x 2.将下面的线性规划问题表示为标准型并用单纯形法求解 max f=x 1+2x 2+x 3 s ．t ．2x 1+x 2-x 3≤2 -2x 1+x 2-5x 3≥-6 4x 1+x 2+x 3≤6 x i ≥0 i=1，2，3 解：先化标准形： Min 321x x x z -+= 224321=+-+x x x x 6525321=++-x x x x 646321=+++x x x x

列成表格： 00001216 100114 60105122001112----- 可见此表已具备1°，2°，3°三个特点，可采用单纯形法。首先从底行中选元素-1，由2/2,6/2,6/4最小者决定选第一行第一列的元素2，标以记号，迭代一次得 0000 1 2 121023 10 40116201002 1 21 211-------- 再从底行中选元素-2/3，和第二列正元素1/2，迭代一次得 1 002 1232 30210231 040116201002121211-- ----- 再从底行中选元素-3，和第二列正元素2，迭代一次得 4002 3 03410120280114042001112--- 再迭代一次得

10 23021 062 21023 1010 213 000421 2 10 13- - 选取最优解： 01=x 42=x 23=x 3. 试用DFP 变尺度法求解下列无约束优化问题。 min f （X ）=4（x 1-5）2+（x 2-6）2 取初始点X=（8，9）T ，梯度精度ε=0.01。解：取I H =0,初始点()T X 9,8= 2221)6()5(4)(-+-=x x x f ??????--=?122408)(21x x x f ???? ??=?624)() 0(x f T x f d )6,24()()0()0(--=-?= )0(0)0()1(d x x α+= T )69,248(00αα--= ])669()5248(4min[)(min 2020)0(0)0(--+--?=+αααd x f )6()63(2)24()2458(8) (00)0(0)0(=-?-+-?--=+ααααd d x df 13077.013017 0≈= α ???? ??=???? ??--?+???? ??=21538.886153.462413077.098)1(x

13-14(1)最优化方法期末试卷

2013-2014学年第一学期数学计算经数专业《最优化方法》（课程）期末试卷试卷来源：自拟送卷人:赵俊英打印：赵俊英乔凤云校对：赵俊英一．填空题（20分） 1．最优化问题的数学模型一般为：____________________________，可行域D 可以表为_____________________________，若____________________，称* x 为问题的全局最优解. 2.()()??? ? ??+???? ?????? ??=212121 312112)(x x x x x x x f ，则=?)(x f ， =?)(2 x f . 3.设f 连续可微且0)(≠?x f ，若向量d 满足，则它是f 在x 处的一个下降方向. 4. 无约束最优化问题：min (),n f x x R ∈，若k x 是不满足最优性条件的第k 步迭代点，用共轭梯度法求解时，搜索方向k d =______________ 5. 函数R R D f n →?:在点k x 沿着迭代方向}0{\n k R d ∈进行精确一维线搜索的步长k α，则其搜索公式为 . 6 .举出一个具有二次终止性的无约束二次规划算法： . 7.函数222 21 12313()226f x x x x x x x x =+++- （填是或不是）严格凸函数. 二．（18分）简答题： 1. 设计求解无约束优化问题的一个下降算法，并叙述其优缺点. 2. 叙述单折线法的算法思想. 3. 写出以下线性规化问题的对偶： 1234123412341234134min ()2536..873411,762323,324712,0,0,0.f x x x x x s t x x x x x x x x x x x x x x x =-+-??-+++=?? +++≥??+++≤? ≤≥≥??

最优化方法大作业

发动机空燃比控制器引言：我主要从事自动化相关研究。这里介绍我曾经接触过的发动机空燃比控制器设计中的优化问题。发动机空燃比控制器设计中的最优化问题 AFR =a f m m && (1) 空燃比由方程（1）定义，在发动机运行过程中如果控制AFR 稳定在14.7可以获得最好的动力性能和排放性能。如果假设进入气缸的空气流量a m &可以由相关单元检测得到，则可以通过控制进入气缸的燃油流量f m &来实现空燃比的精确控制。由于实际发动机的燃油喷嘴并不是直接对气缸喷燃油，而是通过进气歧管喷燃油，这么做会在进气歧管壁上液化形成油膜，因此不仅是喷嘴喷出的未液化部分燃油会进入气缸，油膜蒸发部分燃油也会进入气缸，如方程（2）。这样如何更好的喷射燃油成为了一个问题。 1110101122211ττττ?? ?? -?? ??????????=+????????-????????????-???? ? ??? ?? ????????? ?f f f v X x x u x x X x y =x && (2) 其中12、,==ff fv x m x m &&=f y m &,=fi u m &这里面，表示油膜蒸发量ff m &、fv m &表示为液化部分燃油、fi m &表示喷嘴喷射的燃油，在τf 、τv 、X 都已知的情况下，由现代控制理论知识，根据系统的增广状态空间模型方程（3） 0000001 1 011011114.70ττττ????-?? ??????????=-+-??????????????? ??????????????? ?? ??=?????? f f v v a X X u +q q m y q x x x &&& (3) 其中()0 14.7?t a q = y -m &。由极点配置方法，只要设计控制器方程（4），就可以使得y 无差的跟踪阶跃输入，那么y 也能较好的跟踪AFR *a m /&。 12-- u =K q K x (4) 这里面的12、K K 确定，可由主导极点概念降维成两个参数12C ,C ，虽然都是最终稳态无差，但是目标是使得瞬态过程中y 和阶跃输入y r 的差异尽可能的小。所以原问

修订过的最优化方法复习题

《最优化方法》复习题第一章引论一、判断与填空题 1 )].([arg )(arg m in m ax x f x f n n R x R x -=∈∈ √ 2 {}{}.:)(min :)(max n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题 )(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切)(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的严格局部最优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为单调下降算法，则对{} ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ .

最优化方法考试试题

华南农业大学期末考试试卷（A 卷） 2010--2011学年第 1 学期考试科目：运筹学与最优化方法考试类型：（闭卷）考试考试时间： 120 分钟学号姓名年级专业一、用单纯形法求解下列线性规划问题（共 15 分） 12121212max 105349 ..528,0z x x x x s t x x x x =++≤?? +≤??≥?

二、灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分） 12121212max 62 ..33,0z x x x x s t x x x x =++≥?? +≤??≥? 三、解下列0-1型整数规划问题（共 10 分） 12345123451345124512345max 325232473438..116333,,,,01 z x x x x x x x x x x x x x x s t x x x x x x x x x =+--+++++≤??+-+≤?? -+-≥??=?或

四、利用库恩-塔克（K-T ）条件求解以下问题（共 15 分） 22121122 121212 max ()104446..418,0f X x x x x x x x x s t x x x x =+-+-+≤??+≤??≥? 五、用内点法求解下列非线性约束最优化问题（共 15 分） 21 121 2min ()6923..3 f X x x x x s t x =-++≥??≥?

六、给定初始点(0)(1,1)T X =，用最速下降法迭代一次研究下列函数的极大值。（共 15 分） 22 121122()46222f X x x x x x x =+--- 七、某人因工作需要购置了一辆摩托车,他可以连续使用或任一年末将旧车卖掉,换一辆新车,下表列出了于第i 年末购置或更新的车至第j 年末的各项费用的累计(含更新所需费用、运行费用及维修费用等)，试据此确定该人最佳的更新策略，使从第一年至第五年末的各项费用的累计之和为最小。（共 15 分）

大连理工优化方法大作业MATLAB编程

function [x,dk,k]=fjqx(x,s) flag=0; a=0; b=0; k=0; d=1; while(flag==0) [p,q]=getpq(x,d,s); if (p<0) b=d; d=(d+a)/2; end if(p>=0)&&(q>=0) dk=d; x=x+d*s; flag=1; end k=k+1;

if(p>=0)&&(q<0) a=d; d=min{2*d,(d+b)/2}; end end %定义求函数值的函数fun，当输入为x0=（x1，x2）时，输出为f function f=fun(x) f=(x(2)-x(1)^2)^2+(1-x(1))^2; function gf=gfun(x) gf=[-4*x(1)*(x(2)-x(1)^2)+2*(x(1)-1),2*(x(2)-x(1)^2)]; function [p,q]=getpq(x,d,s) p=fun(x)-fun(x+d*s)+0.20*d*gfun(x)*s'; q=gfun(x+d*s)*s'-0.60*gfun(x)*s'; 结果： x=[0,1]; s=[-1,1]; [x,dk,k]=fjqx(x,s) x =-0.0000 1.0000 dk =1.1102e-016 k =54

function f= fun( X ) %所求问题目标函数 f=X(1)^2-2*X(1)*X(2)+2*X(2)^2+X(3)^2+ X(4)^2- X(2)*X(3)+2*X(1)+3*X(2)-X(3); end function g= gfun( X ) %所求问题目标函数梯度 g=[2*X(1)-2*X(2)+2,-2*X(1)+4*X(2)-X(3)+3,2*X(3)-X(2)-1,2*X(4)]; end function [ x,val,k ] = frcg( fun,gfun,x0 ) %功能：用FR共轭梯度法求无约束问题最小值 %输入：x0是初始点，fun和gfun分别是目标函数和梯度 %输出：x、val分别是最优点和最优值，k是迭代次数 maxk=5000;%最大迭代次数 rho=0.5;sigma=0.4;

《最优化方法》期末试题

作用： ①仿真的过程也是实验的过程，而且还是系统地收集和积累信息的过程。尤其是对一些复杂的随机问题，应用仿真技术是提供所需信息的唯一令人满意的方法。 ②仿真技术有可能对一些难以建立物理模型或数学模型的对象系统，通过仿真模型来顺利地解决预测、分析和评价等系统问题。 ③通过系统仿真，可以把一个复杂的系统化降阶成若干子系统以便于分析，并能指出各子系统之间的各种逻辑关系。 ④通过系统仿真，还能启发新的策略或新思想的产生，或能暴露出在系统中隐藏着的实质性问题。同时，当有新的要素增加到系统中时，仿真可以预先指出系统状态中可能会出现的瓶颈现象或其它的问题。 2.简述两个Wardrop 均衡原理及其适用范围。答： Wardrop提出的第一原理定义是：在道路的利用者都确切知道网络的交通状态并试图选择最短径路时，网络将会达到平衡状态。在考虑拥挤对行驶时间影响的网络中，当网络达到平衡状态时，每个 OD 对的各条被使用的径路具有相等而且最小的行驶时间；没有被使用的径路的行驶时间大于或等于最小行驶时间。 Wardrop提出的第二原理是：系统平衡条件下，拥挤的路网上交通流应该按照平均或总的出行成本最小为依据来分配。第一原理对应的行为原则是网络出行者各自寻求最小的个人出行成本，而第二原理对应的行为原则是网络的总出行成本最小。 3.系统协调的特点。答：（1）各子系统之间既涉及合作行为，又涉及到竞争行为。（2）各子系统之间相互作用构成一个反馈控制系统，通过信息作为“中介”而构成整体（3）整体系统往往具有多个决策人，构成竞争决策模式。（4）系统可能存在第三方介入进行协调的可能。 6．对已经建立了概念模型的系统处理方式及其特点、适用范围。答：对系统概念模型有三种解决方式。 1.建立解析模型方式对简单系统问题，如物流系统库存、城市公交离线调度方案的确定、交通量不大的城市交叉口交通控制等问题，可以运用专业知识建立系统的量化模型（如解析数学模型），然后采用优化方法确定系统解决方案，以满足决策者决策的需要，有关该方面的内容见第四、五章。在三种方式中，解析模型是最科学的，但仅限于简单交通运输系统问题，或仅是在实际工程中一定的情况下（仅以一定的概率）符合。所以在教科书上很多漂亮的解析模型，无法应用于工程实际中。 2.建立模拟仿真模型方式对一般复杂系统，如城市轨道交通调度系统、机场调度系统、城市整个交通控制系统等问题，可以对系统概念模型中各个部件等采用变量予以量化表示，并通过系统辨识的方式建立这些变量之间关系的动力学方程组，采用一定的编程语言、仿真技术使其转化为系统仿真模型，通过模拟仿真寻找较满意的优化方案，包括离线和在线均可以，有关该方面的内容见第七章。模拟仿真模型比解析模型更能反映系统的实际，所以在交通运输系统中被更高层次的所使用，包括

预测与决策试卷及答案解析

经济预测与决策考试形式：闭卷考试时量：150分钟总分：100分一．单选题1*15=15分 1.经济预测的第一步是（）A A.确定预测目的，制定计划 B.搜集审核资料 C.建立预测模型 D.评价预测成果 2.对一年以上五年以下的经济发展前景的预测称为（）B A.长期经济预测 B.中期经济预测 C.短期经济预测 D.近期经济预测 3.（）回归模型中，因变量与自变量的关系是呈直线型的。C A.多元 B.非线性 C.线性 D.虚拟变量

4.以下哪种检验方法的零假设为：B1=B2=…=Bm=0？B A.r检验 B.F检验 C.t检验 D.DW检验 5.以数年为周期，涨落相间的波浪式起伏变动称为（）D A.长期趋势 B.季节变动 C.不规则变动 D.循环变动 6. 一组数据中出现次数最多的变量值，称为（）A A.众数 B.中位数 C.算术平均数 D.调和平均数 7. 通过一组专家共同开会讨论，进行信息交流和相互启发，从而诱发专家们发挥其创造性思维，促进他们产生“思维共振”，达到相互补充并产生“组合效应”的预测方法为（）A A.头脑风暴法 B.德尔菲法

C.PERT预测法 D.趋势判断预测法 8.（）起源于英国生物学家高尔登对人类身高的研究。B A.定性预测法 B.回归分析法 C.马尔科夫预测法 D.判别分析预测法 9.抽样调查的特点不包括（）D A.经济性 B.时效性 C.适应性 D.全面性 10.下图是哪种多项式增长曲线（）B A.常数多项式 B.一次多项式 C.二次多项式

D.三次多项式 11.根据历年各月的历史资料，逐期计算环比加以平均，求出季节指数进行预测的方法称为（）C A.平均数趋势整理法 B.趋势比率法 C.环比法 D.温特斯法 12.经济决策按照目标的性质和行动时间的不同，分为（）D A.宏观经济决策和微观经济决策 B.高层、中层和基层决策 C.定性决策和定量决策 D.战术决策和战略决策 13.（）是从最好情况出发，带有一定冒险性质，反映了决策者冒进乐观的态度。B A.最大最小决策准则 B.最大最大决策准则 C.最小最小后悔值决策准则 D.等概率决策准则 14.如果某企业规模小，技术装备不良，担负不起较大的经济风险，则该企业应采用（）A

最优化大作业

最优化方法大作业 ---------用优化算法求解函数最值问题

摘要最优化(optimization) 是应用数学的重要研究领域.它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。最优化问题一般包括最小化问题和最大化问题，而最大化问题可以通过简单的转化使之成最最小化问题。最小化问题分为两类，即约束最小化和无约束最小化问题。在此报告中，前两个问题属于无约束最小化问题的求解，报告中分别使用了“牛顿法”和“共轭梯度法”。后两个问题属于有约束最小化问题的求解，报告中分别用“外点法”和“内点法”求解。虽然命名不一样，其实质都是构造“惩罚函数”或者“障碍函数”，通过拉格朗日乘子法将有约束问题转化为无约束问题进行求解。再此报告中，“外点法”和“内点法”分别用了直接求导和调用“牛顿法”来求解无约束优化问题。在此实验中，用“共轭梯度法”对“牛顿法”所解函数进行求解时出现错误，报告中另取一函数用“共轭梯度法”求解得到正确的结果。此实验中所有的函数其理论值都是显见的，分析计算结果可知程序正确，所求结果误差处于可接受范围内。报告中对所用到的四种方法在其使用以前都有理论说明，对“外点法”中惩罚函数和“内点法”中障碍函数的选择也有相应的说明，另外，对此次试验中的收获也在报告的三部分给出。本报告中所用程序代码一律用MATLAB编写。【关键字】函数最优化牛顿法共轭梯度法内点法外点法 MATLAB

一，问题描述 1，分别用共轭梯度发法和牛顿法来求解一下优化问题 ()()()()()4 41432243221102510min x x x x x x x x x f -+-+-++= 2，分别用外点法和内点发求解一下优化问题 ?? ?≥-++0 1.min 212 231x x t s x x 二、问题求解用牛顿法求解 ()()()()()4 414 322 432 21102510min x x x x x x x x x f -+-+-++= 1.1.1问题分析：取步长为1而沿着牛顿方向迭代的方法称为牛顿法，在牛顿法中，初始点的取值随意，在以后的每次迭代中，()[] ()k k k k x f x f x x ??-=-+1 21，直到终止条件成立时停止。 1.1.2 问题求解注：本程序编程语言为MATLAB ，终止条件为()162 110-≤?x f ，初始取值为 [10 10 10 10] M 文件（求解函数）如下： function s=newton1(f,c,eps) %c 是初值，eps 为允许误差值 if nargin==2 eps=; elseif nargin<1 error('') % return end syms x1 x2 x3 x4