附录5最优化方法复习题

1、k附录5最优化方法复习题1、设A Rnn是对称矩阵，b Rn,c R，求f(x)1-xtAx bTx c在任意点x处2 的梯度和Hesse矩阵.解 f(x) Ax b, 2f (X) a .2、设(t)f (X td)，其中f :Rn R二阶可导，XRn,dRn,t R，试求(t).解 (t)TT 2f(x td) d, (t) d f(X td)d .3、设方向d Rn是函数f(X)在点x处的下降方向,% S，使 f (%f(X).由于f(X)为S上的凸函数，因此H I ddT f(x) f(x)T dT f(x)f(x)T f(x)其中I证明为单位矩阵，证明方向P H f(x)也是函数f

2、(X)在点X处的下降方向.由于方向d是函数f(X)在点X处的下降方向，因此f(x)Td 0，从而f(x)T Pf(x)TH f(x)f(x)T(I 卷 ff) f(x)f(x)T f(x)f (X)Td f(x)T f(x)f(x)Td 0，所以,方向P是函数f(x)在点X处的下降方向.4、 SRn是凸集的充分必要条件是m 2, X1, X2,L , Xm S,X1,X2丄,Xm的一切凸组合都属于S .证明 充分性显然.下证必要性.设S是凸集，对m用归纳法证明.当m 2时,k 1iX，i 1由凸集的定义知结论成立，下面考虑 m k 1时的情形.令X其中Xik 10, i 1, 2, L , k

3、 1，且 i 1.不妨设 k 11 (不然 X xk 1 S，i 1结论成立)，记yiXi，有 Xi 1 1 k 1(i k i) y k iXk i ,k又一0, i 1,2,L ,k,1 k 1i 1 1 k 1则由归纳假设知，y s,而Xk i S ,且S是凸集，故Xf为S上的凸函数的5、设S Rn为非空开凸集，f : S R在S上可微，证明:充要条件是f(X2)f (Xi)f (Xi)T(X2Xi),Xi,X2证明必要性.设f是S上的凸函数,则Xi , X2(0,1)，有f( X2 (i)Xi)f(X2) (1)f(x,),于是 f (Xi(X2Xi) f(X)f(X2)f(Xi),因

4、S为开集，f在S上可微，故令f(x,)T(X2 X,), Xi,X2 S .f (Xi)T(X2 Xi) f (X2) f (Xi)，即 f(X2) f(Xi)充分性.若有 f(X2)f (Xi)f (Xi)T(X2 Xi), Xi,X2则 0,i，取 Xx, (1)x2S，从而f (Xi)f (X)f (x)T(Xi将上述两式分别乘以和i 后,相加得f(Xi) (i)f(X2) f(x)f (x)T( Xi (i)X2 X)f (X) f ( Xi (i)X2)所以f为凸函数.6证明：凸规划min f (x)的任意局部最优解必是全局最优解.证明用反证法.设X S为凸规划问题minf(X)的局

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

6、x处的下降方向，这与x为问题min f(x)的最优解矛盾.故f(X)T(x x) 0, x S .充分性.若 f(X)T(x X) 0, X S .反设存在)% S，使得f(X) f(X).f(x (% X) f(x) f ( % (1)X) f(X)f(% 0 )f(x)f(x)f(% f(X) 0( (0,1)，因S为凸集，f在S上可微，故令 0,得f(X)T(% X) f(% f (x) 0，这与已知条件矛盾，故x是问题mi nf(x)的最优x S解.8、设函数f(x)具有二阶连续偏导数，Xk是f(x)的极小点的第k次近似，利用f(x)在点Xk处的二阶Taylor展开式推导Newton法

7、的迭代公式为2 1Xk 1Xk f (Xk)f (Xk).证明 由于f(x)具有二阶连续偏导数，故Xk)T 2f (Xk)(X Xk).为求 (X)的极小点，可令1f (x)(x)f(Xk)f (Xk)T(x Xk) -(X且2f(xk)是对称矩阵，因此(X)是二次函数.(X) 0，即 卩 f(Xk)2f(Xk)(x Xk) 0,若 2f(Xk)正定，则上式解出的(X)的平稳点就是(X)的极小点，以它作为f (x)的极小点的第k 1次近似，记为Xk 1，即Xk 1 Xk 2 f (Xk) 1 f (Xk)，这就得到了 Newton法的迭代公式.9、叙述常用优化算法的迭代公式.0.618法的迭代

8、公式:akak(1)(bkak),(bk ak).ak(2)Fib on acci法的迭代公式:Fn k 1Fak(bkn k 1 冲bkFn k 1ak ),(k 1,2,L ,n 1) ak)Newton 一维搜索法的迭代公式:tk 1 tk(tk)(tk)最速下降法用于问题 minf(x)1xTQX bTxc的迭代公式:Xk 1Xkf(Xk)T f(Xk)f(Xk)TQ f(Xk)f (Xk)(5)Newton法的迭代公式：Xk i Xk 2f(Xk) 1f(Xk) 共轭方向法用于问题 minf(x)Xk 1Xk-xtQx bTx 2f(Xk)Tdkddk c的迭代公式:10、已知线性规

9、划:min f (x)2为x2 x3;s.t. 3x1x22x2X2x360,2x310,x320,为，X2,X30.(1)(2)dkTQdk用单纯形法求解该线性规划问题的最优解和最优值;写出线性规划的对偶问题;求解对偶问题的最优解和最优值.解 (1)引进变量X4,X5,X6，将给定的线性规划问题化为标准形式:min f(X) 2xi x? X3；s.t 3xi X2 X3 X4 60,X 2x2 2x3 X5 10,X2 X3 X320,为，X2,L ,X60.X1X2X3X4X5X6X431110060X51-2201010X611*-100120f-21-10000X420210-140

10、X530001250X211-100120f-30000-1-20所给问题的最优解为X (0, 20,0)T，最优值为f 20 .(2)所给问题的对偶问题为:maxg(y)60s.t 3y1 y2y1 2y2y1 2y2%2肆3y3y3y30.10y2 20y3；2,1,1,(3)将上述问题化成如下等价问题:min h(y)s.t 3y1y1y160% 10y2 20y3； y3 2,y31,y31,0.y22y22y2yi,y2,y3引进变量y4, y5, y6，将上述问题化为标准形式:20y3；2,1,1,问题(2)的最优解为y问题(1)的最优解为y(0,0,1)T，最优值为g 20 (最

11、大值).min h(y) 60比 10y2 s.t 3y1 y2 y3*y1 2y2 y3 y5 y1 2y2 y3 y6 y1,y2,L ,y60.yy2y4y5yy4-3-1-11002y5-12-1*010-1y6-1-210011h-60-10-200000y4-2-301-103y31-210101y6-2000110h-40-5000-20020(0,0,1)T，最优值为h 20 (最小值).11、用0.618法求解 min (t) (t 3)2，要求缩短后的区间长度不超过0.2，初 始区间取0,10.解第一次迭代:取亦0,10,0.2确定最初试探点1分别为1 a10.382(b1

12、印)3.82 ,1 a 0.618(b1 a1)6.18 .求目标函数值:(1)(3.823)20.67 ,( 1)(6.18 3)210.11.比较目标函数值:(1)(1)比较 1 a1 6.180 0.2第二次迭代：a2 a10, b216.18, 2 1 3.82,( 2)( 1) 0.67 2a20.382(b2a2 ) 0.382(6.180)2.36,2 ) (2.36 3)20.4( 2 ), 2a2 3.82第三次迭代：a3 a20, b323.82, 3 22.36,( 3)2 ) 0.4 3 a30.382( b3a3 )0.382(3.820)1.46,3)2(1.46

13、3)22.37( 3), b33.82 1.46第四次迭代：a43 1.46, b4b33.82,4 3 2.36,0.44 a4 0.618( b4a4)1.460.0.618(3.821.46)2.918,0.0067 ( 4 ) ( 4), b43.822.36第五次迭代：a54 2.36, b5b43.82,5 4 2.918,4)0.0067 5 a5 0.618( b5a5)3.262, ( 5)0.0686 ( 5 )( 5 ), 5a53.262 2.36第六次迭代：a6 a52.36, b63.262, 6 52.918, ( 6 )0.0067 6 a60.382(b6a6

14、)2.7045, ( 6 )0.087 ( 6 ), b63.262 2.7045第七次迭代：a76 2.7045, b7 b6 3.262, 76 2.918, ( 7 )( 6) 0.0067 7 a7 0.618(b7 a7 ) 3.049, ( 7 )0.002 (7)(7), b77第八次迭代:a82.918, b8b73.262,3.049,( 8)7) 0.002 a80.618(b8a8)3.131,0.017 .8)(8), 8a81第九次迭代:a9a82.918, b93.131,3.049,( 9)8) 0.002 a90.382(b9a9)2.999,9)0.00000

15、1 .9)(9),9a93.049 2.918亍3.02412、用最速下降法求解2min f (x) x1 2x1x22x|4x13X2，取 x®（1”，迭代两次.解 f(x) (2X14,2X1 4X2 3)t ,将f(x)写成f(x)11xTQx bTx的形式，则Q224,b第一次迭代:(0)f(X(0)T f(X(0)f(x®)TQ f(x®)£/ (0)、f(x )0(0,3) 32 2(0,3) 241/4第二次迭代:x（2）x(1)f(x)Tf(x)f(x)Tq f(x)f(x)13/2(3/ 2,0)021/42(3/ 2,0) 23/20

16、7/41/413、用FR共轭梯度法求解2min f (x) (x1 x2 x3)( x1 x2X3)2(xi xX3)2，取X®(*1,$，迭代两次.若给定0.01,判定是否还需进行迭代计算.解 f(X)3(xj2X2X32)2(XiX2X1X3 X2X3),1再写成f(x) 2XtGx ,22， f (X) Gx6第一次迭代:f(X(0)(0,4,0)T，令 d。f(X(0)(0, 4,0)T，从X(0)出发，沿d0进行一维搜索,即求 min f(X®do)2 1648 2的最优解,01/6,x X(0)0d0(1/2,1/ 3,1/2)T .第一次迭代:f(X)(4/3

17、,0,4/3)t .I f(x)f(x®)|2d1f(x)0d0 ( 4/3,8/9, 4/3)t .从X出发，沿d1进行一维搜索，即求min f(x1 4 1 8 1 41) (2 3 ,3 9 ,2 312131243894的最优解，得3此时31-,X()1/24/3X1d11/338/9881/24/3f(x )(0,0,0)T,| f(x(2)|00.01(0,0,0) T 得问题的最优解为x (0,0,0) T，无需再进行迭代计算.14、用坐标轮换法求解min f (x) x： 2xf 4为2%2，取x(0)(1,1)T，迭代步.解从点x(0)(1,1)T出发，沿ei (1

18、,0)T进行一维搜索,即求 min f(x(0)e) 2 43的最优解，得2,x1/2,x(2)X x®00(3,1)T .再从点X出发,沿e2(0,1)T进行一维搜索,即求minfde2)2 2 27的最优解，得程2(3,3/ 2)T .15、用 Powell 法求解 min f (x)向组d0X12 X； 3X1 X1X2，取 X®(0,0)T，初始搜索方(0,1)T,d1(1,0)T，给定允许误差0.1 (迭代两次).解第一次迭代:令y®x(0)(0,0)T，从点y®出发沿d0进行一维搜索，易得00, y y(0)0d0(0,0)T ；接着从点y出

19、发沿d1进行一维搜索，得3 (2)(1)/3 c、T1 2,y y1d1 (2,0)由此有加速方向d2 yy®(|,0)T .因为lldzll 3/2，所以要确定调整方向.由于什)0,f(y)0,廿)9，按(S" ) 式有f(y)f(y)maxf(y)f(y(j 1)| j 0,1，因此m 1,并且f(y(m) f(y(m 1) f(y)f(y)又因f(2yy(0)0,故(8418 )式不成立.于是，不调整搜索方向组，并令 Xy(2)(|,0)T .第二次迭代：取y®X(|,0)T，从点y(0)出发沿d0作一维搜索，得3 (1)(0)/3 3T0 ；,y y0*

20、(；,；) 4 2 4接着从点y出发沿方向d1作一维搜索，得3 (1)Z15 3 T1 8，y V1d1 (討-由此有加速方向d2 y(2) y(0)(|'|)T -因为|d2|3亦/8 ，所以要确定调整方向.因f(y(0)故按(8417 )式易知m 0，9，f(y(1)并且45'f(y(2)18964f (严)f(y(m 1)f(y(0) f(y)916由于f(2严y)45兀，因此(8.4.18 )式成立。于是，从点y出发沿d2作一维搜索，得2d2 (2,1)T o1 2 -,x()y()3同时，以d2替换d0，即下一次迭代的搜索方向组取为33d0 (诃,d1(打16、用外罚函数法在直线 x y 1上求一点P(x,y)，使得P到原点0(0,0)的距离近似最短，取1 0.5,2,1° 4解令 f (x, y) x2y2，问题可归为求解如下最优化问题2 2min f (x, y) x y ;s.t. h(x, y) x y 10.引入罚函数F(x,y,'22/八 2k) x y k(x y 1).则原约束最优化问题相应的一系列无约束最优化问题为:min F(x, y, k)，其中1°.5,k2 k,k1,