《最优化方法》复习题

1、精品文档 最优化方法复习题 一、 简述题 1、怎样判断一个函数是否为凸函数 （例如：判断函数f（x） 2x1x2 - 2x2 -10X! 5x2是否为凸函数） 2、写出几种迭代的收敛条件. 3、 熟练掌握利用单纯形表求解线性规划问题的方法（包括大M法及二阶段法） 见书本61页（利用单纯形表求解）； 69页例题（利用大M法求解、二阶段法求解）; 4、简述牛顿法和拟牛顿法的优缺点. 简述共轭梯度法的基本思想. 写出Goldstein、Wolfe非精确一维线性搜索的公式。 5、叙述常用优化算法的迭代公式. (1) 0.618法的迭代公式： 已=ak +i(bk aQ. f 人=ak +卩心亠(bk

2、aQ, (2) Fib on acci法的迭代公式：彳心十(k = 1,2,川，n1). -k 二 ak(bk - ak) F n_k 卅 (3) Newton一维搜索法的迭代公式：Xk = xG gk 1 (4) 推导最速下降法用于问题 min f(x)二-xTGx - bTx c的迭代公式： 2 T xk 1 =Xkgf7rkf (xk) 9k Gk gxk (5) Newton法的迭代公式：Xk .1 =Xk -p 2 f (xj七 f (Xk). 1 （6）共轭方向法用于问题min f（x）bTx c的迭代公式: dkTQdk 、计算题 双折线法练习题 课本135页 例3.9.1 FR

3、共轭梯度法例题：课本150页 例4.3.5 二次规划有效集：课本213页例6.3.2, 所有留过的课后习题 二、练习题： 1、 设A运R仪是对称矩阵，b Rn, c e R ,求f (x) = *丁 Ax + bTx + c在任意点x处 的梯度和Hesse矩阵. 解 f (x)二 Ax b, I f (x)二 A . 2、 设()=f(x d ),其中 f ：RnR 二阶可导，Rn,d Rnt R ,试求;：(t). 解 ：(t)八 f(x td)Td,(t)二 dT、2f (x td)d . 3、证明：凸规划min f(x)的任意局部最优解必是全局最优解. 证明 用反证法.设S为凸规划问题m

4、inf(x)的局部最优解，即存在x的某 X辛 个：邻域N (x)，使f (xH f (x), -x 叫.(刃门S .若x不是全局最优解，则存在 x S，使f (x) ： f (x).由于f(x)为S上的凸函数，因此 -(0,1)，有 f( x (1 - )xf 仅)(1 一 )f (x： f (x). 当充分接近1时，可使x (1 ，)x Nx)ns，于是f(x)乞f( x (1-，)x)， 矛盾.从而x是全局最优解. min f (x) =2為 _x2 十花； s.t 3x1 十 X2 +怡兰 60, 4、 已知线性规划：*x -2x2 +2x3 10, 为+屜一X3兰20, IX1,X2,

5、X30. (1) 用单纯形法求解该线性规划问题； (2) 写出线性规划的对偶问题； 解 (1)引进变量X4,X5,X6，将给定的线性规划问题化为标准形式： min f (x) = 2片 _x2 + x3; s.t 3捲 +x2 +x3 +x4 =60, 为2x2+2x3+X5 =10, N 十乂？ X3 +X5 =20, 为兀，川必KO. 所给问题的最优解为X二(0, 20,0)T，最优值为亍=_20 . (2)所给问题的对偶问题为： ”maxg(y) =-60y)-10y2 -20y3; S.t - 3yi - y2 - y3 一 2, 一 yi +2y2 y3 兰一1, -2丫2 + y3

6、 兰1， 力丛以ho. 0.2 , 初 5、用0.618法求解min(t) =(t -3)2，要求缩短后的区间长度不超过 始区间取0,10 解第一次迭代： 取力=0,10, ； 72 . 确定最初试探点1,1分别为 1 =印 0.382(0 aj =3.82 ,Vai 0.618(66)=6.18 . 求目标函数值： 1)=(3.82 -3)2 =0.67 ,:(叫)=(6.18 -3)2 =10.11 . 比较目标函数值：(J*). 比较叫 =6.18 -0 0.2 =；. 第二次迭代： a2 =a -4 -3 第一次迭代: x(1x(0) (0)、T(0) (0,3) (0,3) 13丿

7、1 A 2、 I 4 l3丿 W 4丿 2 2 4 人3 第二次迭代: x(2)次 5x八f(x) f(x(1)TG f(x(1)() -3/2 (1、 0丿 f-3/27/4、 1/4； 2 2、 (-3/ 2 A 、0 丿一 J/4丿 2 4 A A 過1,y，迭代 7、用FR共轭梯度法求解 min f (x)=(捲_X2X3)2(_%X2X3)2(%X2_X3)2，取x(0) 两次.若给定；=0.01,判定是否还需进行迭代计算. 2 2 2 解 f (x) =3(X1X2X3 ) -2(%X2 X1X3 X2X3), 1 再写成 f(x)rxTGx , G 6 -2-2 -2 6-2，可

8、f(x)=Gx . 厂2 -2 6 第一次迭代: v f (x(0) =(0,4,0)t，令 d。=f(x ) =(0,-4,0)丁 ,从x(0)出发，沿do进行一维搜索，即求minf (x(0)d。)=2 一16482的最优解, /_0 得 (1)(0)T =1/6,x=x odo =(1/2,1/3,1/2). 第一次迭代： l f (x)=(4/3,0,4/3)丁 . o 屮X) if(x(0) di - -f(x(1) ： odo=(-4/3,-8/9,-4/3)T. 从x(1)出发，沿di进行一维搜索，即求 14 吶蚣ar(厂3 ,-4 ) 3 92 3 (1 4、) -2 2 2

9、3 1 8、 6 -2 K 3 9 -2 6丿 1 4口 扎 1=2。故 x(2) ，故x(2)为最优解。 = X(1) Jd=0，由于 X(x(2) I ) 10、用有效集法求解下面的二次规划问题: 2 2 min f (x)=捲x2 -2捲4x2 st. -xi -x21 亠 0 x1 _ 0,x2 _ 0. 解：取初始可行点 x(0) =(0,0), A。二A(x(0)二2,3.求解等式约束子问题 min d； d； -2d1 -4d2 s.t d = 0,d? = 0 得解和相应的Lagrange乘子 d(0) =(0,0)T, (一2,一4)丁 故得 x=x(0) =(0,0)T,A

10、 二人 3二2 转入第二次迭代。求解等式约束子问题 2 2 min d-i d2 -2d -4d2 st di = 0 得解 d(1)=(0,2)t =0 计算 b _aTx ：-min1, iaTd(D i J3,aTd冷 a d 2 令 x 二x ：id =(0,1)T,A2 二 AiU1二1,2 转入第三次迭代。求解等式约束子问题 min d12 d； -2d2d2 s.t di d2 =0,di =0 得解和相应的Lagrange乘子 d=(0,0)T, =(2,0)丁 由于，_0 ,故得所求二次规划问题的最优解为 = (0,1)T 相应的Lagrange乘子为 二(2,0,0) 最速

11、下降法的优缺点： 优点：方法简单，计算量较小；最速下降法为全局收敛，对初 始点的要求很少。 缺点：最速下降法的收敛速度与变量的尺度关系很大，对有些 例子，在极小点附近产生显著的锯齿现象，收敛十分缓慢；最 速下降法的最速下降仅是一种局部性质，即从局部来看目标函数 的值下降得最快，但从总体来看它可能走了许多弯路。 牛顿法的优缺点： 优点：牛顿法的收敛速度快，为二阶收敛；公式简单， 计算方便。 缺点：牛顿法要求f（x）二阶可微，迭代中需多次计算 ;牛顿法具有局部收敛性，对初始点的要求比较苛刻。 共轭梯度法的优缺点： 优点：计算公式简单，存储量较小，对初始点要求很少，对二 次函数具有二次终止性；收敛速度介于最速下降法和牛顿法之 间，对高维（n较大）的非线性函数具有较高的效率。对于二 次函数具有二次终止性，一般情况下优于共轭梯度法。 缺点：共轭梯度法的收敛性依赖于精确的一维搜索，计算量较 大；共轭梯度法的一些理论背景至今尚不清楚，