附录5：《最优化方法》复习题

1、k附录5最优化方法复习题11、 设A Rn n是对称矩阵，b Rn,c R，求f(x) -xT Ax bTx c在任意点x处 的梯度和Hesse矩阵.解 f (x) Ax b,2f (x) A .2、设(t)f (x td)，其中 f ：Rn R 二阶可导，x Rn,dRn,tR，试求 (t).解(t) f(x td) Td, (t) dT 2f (x td)d.3、设方向d Rn是函数f (x)在点x处的下降方向，令H I ddT f(x) f(x)TdT f(x)f(x)T f(x)其中I为单位矩阵，证明方向p H f (x)也是函数f (x)在点x处的下降方向.证明由于方向d是函数f(x

2、)在点x处的下降方向，因此 f(x)Td 0，从而f(x)Tpf(x)TH f(x)f(x)T(IdT：(x)f (:昇：l)f(x)f(x)T f(x)f (x)Tdf(x)T f(x)f (x)Td 0，所以，方向p是函数f(x)在点x处的下降方向.4、S Rn是凸集的充分必要条件是m 2,捲龙丄,xm S,X1,X2丄,xm的一切凸组合都属于S .证明 充分性显然.下证必要性.设S是凸集，对m用归纳法证明.当m 2时,k 1由凸集的定义知结论成立，下面考虑 m k 1时的情形.令xixi，i 1k 1其中 Xi S, i 0, i 1,2, L , k 1，且 i 1.不妨设 k 1 1

3、 (不然 x Xk1 S，i 1结论成立)，记 yix，有 x (1 k i)yk iXk i ,i 1 k ik又一0, i 1,2,L ,k,1 ,1 k 1i 1 1 k 1则由归纳假设知，y S,而xk 1 S，且S是凸集，故x S .5、设S Rn为非空开凸集，f:SR在S上可微，证明：f为S上的凸函数的充要条件是 f(X2) f(xjf(xJT(X2 xj, X1,X2 S .证明 必要性.设f是S上的凸函数，贝U xX2 S及 (0,1)，有f( X2 (1)xjf (X2) (1)f(xj，于是 f(X1(X2 xj)心)似)f(xj，因S为开集，f在S上可微，故令0,得f(x

4、JT(X2X1)f (X2)f (X1)，即 f(X2)f (X1)f(x()T(X2x(),X1,X2S .充分性.若有 f(X2) f (X1)f(X1)T(X2 X1), X1,X2 S，则 0,1，取 xX1 (1)X2 S，从而f (X)T(X2 x)，f(X1)f (x) f (x)T(X1 x)， f (X2)f (x)将上述两式分别乘以和1 后，相加得f (X1) (1)f (X2)f(x)f (x)T( X1 (1)X2 x)f (X) f ( X1 (1)X2)，所以f为凸函数.6证明：凸规划min f(x)的任意局部最优解必是全局最优解.证明 用反证法.设X S为凸规划问

5、题minf (x)的局部最优解，即存在X的某x S个 邻域N (X)，使f (x)f(x), x N (x)I S .若X不是全局最优解，则存在% S，使f (% f(x).由于f(x)为S上的凸函数，因此(0,1)，有f( x (1)% f(X) (1)f(X% f(X).当 充分接近1时，可使 x (1)% N (X)I S，于是f(X) f( x (1)% ,矛盾从而x是全局最优解.7、 设S Rn为非空凸集，f : SR是具有一阶连续偏导数的凸函数，证明：x是冋题min f (x)的最优解的充要条件 是：f (x)T(x x) 0, x S .x S证明 必要性.若x为问题min f

6、(x)的最优解.反设存在 S，使得x Sf(x)T(% x) 0,则d %x是函数f (x)在点x处的下降方向，这与x为问题 min f (x)的最优解矛盾.故f(x)T(x x) 0, x S .x S充分性.若 f(x)T(x x) 0, x S .反设存在)% S，使得f(% f(x).f (x (% x) f (乂) f ( % (1)x) f (乂)f(% (1)f(x) f(x)f(% f(旳 0(0,1)，因S为凸集，f在S上可微，故令 0,得f(x)T()% x) f(% f (x)0，这与已知条件矛盾，故x是问题mi nf(x)的最优x S解.8、 设函数f (x)具有二阶连

7、续偏导数，Xk是f (x)的极小点的第k次近似，利用f (x)在点Xk处的二阶Taylor展开式推导Newton法的迭代公式为2 1Xk 1 Xk f (xk)f (xk).证明 由于f(x)具有二阶连续偏导数，故T1t 2f (X)(x)f(Xk)f(Xk)(XXk)-(XXk)f (Xk)(XXk).且2f(Xk)是对称矩阵，因此(X)是二次函数.为求(X)的极小点，可令(X) 0，即 f (Xk)2 f (Xk)(x Xk) 0，若 2f (Xk)正定，则上式解出的(x)的平稳点就是(X)的极小点，以它作为f (X)的极小点的第k 1次近似，记为Xk 1，即 xk 1Xk 用单纯形法求解

8、该线性规划问题的最优解和最优值; 写出线性规划的对偶问题； 求解对偶问题的最优解和最优值.解 (1)引进变量X4.X5.X6，将给定的线性规划问题化为标准形式: f (Xk) 1 f (Xk)，这就得到了 Newton法的迭代公式.9、叙述常用优化算法的迭代公式.(1)0.618法的迭代公式:(1)(bk ak),(bkak).ak(2)Fib on acci法的迭代公式:Fn k 1.-(bkFn k 1ak),(k ak),n 1).(3)Newton 一维搜索法的迭代公式:tk 1tk(tk) (tk).(4)最速下降法用于问题min f (x)1 TTx Qx b x2c的迭代公式:f

9、(Xk)T f (Xk)f (Xk)Xk 1Xkf (Xk)TQ f (Xk)(5)Newton法的迭代公式:Xk 12 1Xk f (Xk)f(Xk).(6)共轭方向法用于问题min f (x)1 TTx Qx b xc的迭代公式:akkf(Xk)Tdkdk .Xk 1Xk旦(bkFn k 1dQdk10、已知线性规划：min f (x)2为 x2 x3;s.t. 3x1X2X360,X2x22X310,XX2X320,MMXs0.min f (x) 2x-i x2 x3;s.t 3xi X2 X3 X4 60,X 2x2 2x3 X5 10,X2 X3 X520,为，X2,L ,X60.X

10、iX2X3X4X5X6X431110060X51-2201010X611*-100120f-21-10000X420210-140X530001250X211-100120f-30000-1-20所给问题的最优解为X (0, 20,0)T，最优值为f 20 .(2) 所给问题的对偶问题为：maxg(y)60yi 10y2 20y3；s.t 3yi y2 y32,(1)yi 2y2 y31,yi 2y2 y31,yi,y2,y3 0.(3) 将上述问题化成如下等价问题：min h(y)60yi10y220y3；s.t 3y)y2 y32,yi2y2 y31,yi2y2 y31,yi,y2,y3

11、0.引进变量y4, y5, y6，将上述问题化为标准形式:(2)min h(y) 60比 10y220y3；s.t 3yi y2 y3 屮 2,yi 2y2 y3 y51,yi 2y2 y3 讨61,yi,y2,L ,y6 0.y1y2y3y4y5y6Y4-3-1-11002y5-12-1*010-1y6-1-210011h-60-10-200000y4-2-301-103y31-210101y6-2000110h-40-5000-20020问题(2)的最优解为y (0,0,1)T，最优值为h 20 (最小值).问题(1)的最优解为y (0,0,1)T，最优值为g 20 (最大值).0.2 ,

12、 初11、用0.618法求解 min (t) (t 3)2，要求缩短后的区间长度不超过始区间取0,10 解第一次迭代：取亦0,10,0.2 确定最初试探点1 , 1分别为1 印 0.382(b| 印)3.82 ,1 a 0.618(0 印)6.18 .求目标函数值：(1)(3.82 3)20.67 ,( 1)(6.18 3)210.11 .比较目标函数值:(1) ( 1).比较 1 a1 6.18 0 0.2第二次迭代：a2a10, b2 16.18, 2 13.82,( 2)( 1) 0.672a20.382(b2a2 ) 0.382(6.180)2.36,( 2 ) (2.363)20.4

13、(2)( 2 ), 2a2 3.82 第三次迭代：a3a20, b3 23.82, 3 22.36,( 3)( 2 ) 0.43a30.382( b3a3 ) 0.382(3.820)1.46,( 3) (1.463)22.37(3)( 3), b33 3.82 1.46第四次迭代：a4 31.46, b4b33.82,432.36, ( 4 )( 3 )0.44 a40.618(b4a4)1.460.0.618(3.82 1.46)2.918,( 4 ) 0.0067( 4 )( 4 ), b443.822.36第五次迭代：a5 42.36, b5b43.82,542.918, ( 5)(

14、4 )0.0067 5 a50.618(b5a5)3.262, ( 5)0.0686 ( 5 )( 5 ), 5a53.2622.36第六次迭代：a6 a52.36, b653.262, 6 52.918, ( 6)( 5) 0.0067 6 a60.382(b6a6)2.7045, ( 6 )0.087 ( 6 )( 6 ), b663.262 2.7045第七次迭代：a7 62.7045, b7b63.262, 76 2.918, ( 7 ) ( 6 ) 0.00677 a70.618(b7a7)3.049, ( 7 )0.002 (7)(7), b77第八次迭代：a872.918, b8

15、b73.262,873.049,( 8)(7) 0.002 .8a80.618(a8)3.131,(8)0.017 .(8)(8), 8a8.第九次迭代：ag2.918, bg83.131,gg3.049,( g)(8) 0.002 .9 ag0.382(bgag)2.ggg,(g)0.000001 .(g)(g), gag3.0492.918故 X -93.024.212、用最速下降法求解min f(x) xj 2x1X2 2xf 4xi 3x2，取x(0) (1,1)T，迭代两次.解 f(x) (2x1 2x24,2X1 4X2 3)t ,将f (x)写成f (x)TQx bTx的形式，则

16、Q24*第一次迭代:x(1)(0)f(x)T f(x(0)f (x(0) )TQ f (x(0)(0)f(x(0)第二次迭代:0(0,3) 32 2(0,3)241/4x(2)x(1)(1)、Tf(x )(1) f(x )f (x(1)TQ f(x)f(x)3/2(3/2,0)1 01/4T_23/2(3/ 2,0)2 407/41/413、用FR共轭梯度法求解2 2min f (x)(捲 x2 x3)(论 x2 x3)(论 xX3)2取 X(0)G，1)t，迭代两次.若给定0.01,判定是否还需进行迭代计算.解 f (x)3(X12 X22 X32)1再写成 f (x)xtGx , G22(

17、x-|X2622262 ， f (x) Gx226X1X3X2X3),f(x(0) (0, 4,0)T ,第一次迭代：f(x(0)(0,4,0)t，令 d。从x(0)出发，沿d0进行一维搜索，即求mipfa d)2 1648 2的最优解,得1/6,x x(0)(1/2,1/3,1/2)T .第一次迭代:f (x)(4/3,0,4/3)t .f(x )f(x(0)d1f(x(1)( 4/3, 8/9, 4/3)t .从x(1)出发，沿d1进行一维搜索，即求622231 4181418dj (JJ)2622 3392339226141 4mi。f(x2 3的最优解，得31 8,x1/2x(1)1d

18、11/ 31/2384/38/9(0,0,0) T .4/3此时f(x(2)(0,0,0)T,f(x(2)00.01 .得问题的最优解为X (0,0,0) T，无需再进行迭代计算.14、用坐标轮换法求解 min f (x) x： 2x2 4为2X1X2，取x(0)(1,1)T，迭代一步.解从点x(0)(1,1出发，沿e (1,0)T进行一维搜索,即求 min f (x(0)0 e) 243的最优解，得02,x(1)(0) x00(3,1)T .再从点x(1)出发，沿e(0,1)T进行一维搜索，即求mip f(xe：) 2 2 27的最优解，得11/2,x x1e2(3,3/2)T .15、用

19、Powell 法求解 min f (x) xf x； 3为，取 x(0) (0,0) T，初始搜索方向组d。(0,1)T,d1 (1,0)T，给定允许误差0.1 (迭代两次).解第一次迭代：令y(0)x(0)(0,0)T，从点y(0)出发沿d0进行一维搜索，易得0 0, yy(0)0d0 (0,0)T ；接着从点y出发沿d1进行一维搜索，得3(2)(1)3 T1 2,y y1d1(20)由此有加速方向d2yy(|,0)T .因为d23/2，所以要确定调整方向.由于 f (y(0) 0,f(y)0,f(y)9，按(8417 )式有4f(y)f(y(2) maxf(y(j) f(y(j 1)| j

20、 0,1，因此m 1，并且又因f(2yf(y(m) f(y(m 1)f(y)f(y(2)y(0)0,故(8418 )式不成立于是，不调整搜索方向组，并令 x(1)y(2)(|,0)T 第二次迭代：取y(0)x(1)(|,0)T，从点y(0)出发沿d。作一维搜索,3 (1)(0)3 3T0 ,y y0d0( , ) 4 2 4接着从点y出发沿方向d1作一维搜索，得315 3、t1 8,y y 1d1 ()-由此有加速方向(0)3 3 td2 y y (8讦因为d23.5/8，所以要确定调整方向因f(y(0)故按(8417 )式易知m 0，9，f(y(1)并且45f(y(2)18964，f(y(m

21、)f(y(m 1)f(y(0) f(y)916由于f(2y(2)y(0)4516，因此(8.4.18 )式成立。于是，从点y(2)出发沿d2作一维搜索，得2d2 (2,1)T。1 2 ,x y同时，以d2替换d0，即下一次迭代的搜索方向组取为3 3d0(1,0)T，d1(打16、用外罚函数法在直线 x y 1上求一点P(x,y)，使得P到原点0(0,0)的距离近似最短，取10.5,2,10解令 f(x,y) x2y2，问题可归为求解如下最优化问题min f (x, y) x2y2;s.t. h(x, y) x y 10.引入罚函数F(x, y, k) x2 y2k(x y 1)2 则原约束最优化问题相应的