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

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

2、x)在点x处的下降方向，因此 f(x)Td 0,从而f (x)T pf (x)T H f(x)f(x)T(IddTdT f(x)f(x) f(x)Tf(x)T f(x)f(x)f (x)T f(x) f (x)Td 0,所以，方向p是函数f (x)在点x处的下降方向.4、S Rn是凸集的充分必要条件是m 2, x-,x2,L ,xm S,x-,x2,L ,xm的一切凸组合都属于S .证明 充分性显然.下证必要性.设S是凸集，对m用归纳法证明.当m 2时,k 1由凸集的定义知结论成立，下面考虑 m k 1时的情形.令xixi ,i 1 k 1其中 xi S, i 0, i 1,2, L , k

3、1 ,且 i 1.不妨设 k 1 1 (不然 x xk1 S, i 1k结论成立)，记y i一 xi，有x (1 k 1)y k诙1 ,i 1 1 k 1k又0, i 1,2,L ,k,1 ,1 k 1i 1 1 k 1则由归纳假设知，y S,而41 S,且S是凸集，故x S.5、设S Rn为非空开凸集，f：SR在S上可微，证明：f为S上的凸函数的充要条件是 f(X2) f(X1)f(X1)T(X2 X1), X1,X2 S .证明 必要性.设f是S上的凸函数，则 X1,X2 S及 (0,1),有f( X2 (1)X1)f(X2)(1)f(X1),于是 f(X_(X2 X1) f(¥

4、)f(X2) f(X1),因S为开集，f在S上可微，故令 0,得f(X1)T(X2X1)f(X2)f(X1),即 f(X2)f(X1)f(X1)T(X2X1),X1, X2S .充分性.若有 f(X2) f(X1)f(X1)T(X2 X1), X1,X2 S ,则 0,1,取 xX1 (1)X2 S,从而f(X1) f (X)f (X)T(X1 X), f (X2) f(X) f (X)T(X2 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

5、)的任意局部最优解必是全局最优解. x S证明 用反证法.设X S为凸规划问题min f(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(

6、x X) 0, x S.x S证明 必要性.若x为问题min f (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 .反设存在，0 S,使得f (% f (x).f(x (% x) f(x) f( % (1)x) f (x)f (x% (1 )f (x) f(x)LL f(% f(x) 0(0,1),因S为凸集，f在S上可微，故令 0,得f(x)T(% x) f(% f (x) 0 ,这

7、与已知条件矛盾，故x是问题min f (x)的最优 x S解.8、设函数f(x)具有二阶连续偏导数，xk是f(x)的极小点的第k次近似，利用f(x)在点xk处的二阶Taylor展开式推导Newton法的迭代公式为21xk 1 xk f (xk) f (xk).证明 由于f(x)具有二阶连续偏导数，故. T1T 2 f (x)(x)f (xk)f(xk)(xxk)-(xxk)f(xk)(xxk).且2f(xk)是对称矩阵，因此 (x)是二次函数.为求 (x)的极小点，可令22 _(x) 0,即 f(xk)f(xk)(x xk) 0,若f(xk)正定，则上式解出的(x)的平稳点就是(x)的极小点，

8、以它作为f(x)的极小点的第k 1次近似，记为xk 1 ,即xk 1 xk 2 f (xk) 1 f (xk),这就得到了 Newton法的迭代公式.9、叙述常用优化算法的迭代公式.(1) 0.618法的迭代公式:(2) Fibonacci法的迭代公式:ak(1)(bka)kak也ak).ak Fn k 1 (bk ak),Fk 1(k 1,2,L ,n 1).ak(bk ak)(3)Newton一维搜索法的迭代公式:tk 1tk(tk) (tk)(4)最速下降法用于问题 min f(x)1 T-x Qx b x c的迭代公式: 2xk 1xkf(xk)T f(xk)fX)TQ f(xk)(5

9、) Newton法的迭代公式：xk 1 xk 2f(xk)1 f(xk).(6)共腕方向法用于问题 min f (x)xk 1xk1 xT Qx bTx c的迭代公式:2f(xJTdk , t dk .dkTQdk10、已知线性规划：min f (x) 2x1 " x3; st 3x1 x2 x3 60,x1 2x2 2x3 10,x1 x2 x3 20,Xi，X2，X30.Fn k 1(1)用单纯形法求解该线性规划问题的最优解和最优值;(2)写出线性规划的对偶问题;(3)求解对偶问题的最优解和最优值.解 (1)引进变量X4,X5,X6,将给定的线性规划问题化为标准形式:min f

10、(x) 2x1 x2 x3; st 3xi X2 X3 X4 60, x1 2x2 2x3 x5 10, Xi X2 X3 X620,Xi,X2,L ,X6 0.XiX2X3X4X5X6X431110060X51-2201010X611*-100120f-21-10000X420210-140X530001250X211-100120f-30000-1-20所给问题的最优解为X (0,20,0) T,最优值为f 20.(2)所给问题的对偶问题为： maxg(y)60y1 10y2 20y3；s.t 3% V2 V3 2,(1)Vi 2y2 V31，yi 2y2 y3 1, Vi，V2，V3 0

11、.(3)将上述问题化成如下等价问题： minh(y) 60yi 10y2 20y3； st 3y1 y2 y3 2,Vi 2y2 y31,Vi 2y2 V3 1, y1,y2,y3 0.引进变量y4, y5, y6,将上述问题化为标准形式：(2)min h(y) 60yl 10y2 20y3; st 3yi V2 y3 Va 2, yi 2y2 y3 y51,yi 2y2 y3 y61,Vi,V2,L ,y6 0.YiY2Y3Y4Y5Y6y4-3-1-11002y5-12-1 *010-1y6-1-210011h-60-10-200000y4-2-301-103y31-210101y6-200

12、0110h-40-5000-20020问题(2)的最优解为y (0,0,1)，最优值为h 20 (最小值).问题(1)的最优解为y (o,0,i)T,最优值为g 20 (最大值).11、用0.618法求解 min (t) (t 3)2 ,要求缩短后的区间长度不超过始区间取0,10 .解第一次迭代：取 0,10,0.2 .确定最初试探点1 ,1分别为1 a1 0.382(b1 a1) 3.82,14 0.618(b1 a1) 6.18.求目标函数值：(1) (3.82 3)2 0.67,( 1) (6.18 3)2 10.11.比较目标函数值：(1)( 1).比较 1 a1 6.18 0 0.2

13、.第二次迭代：a2 a1 0, b21 6.18, 213.82, (2)( 1) 0.67 .2 a2 0.382(2 a2) 0.382(6.18 0) 2.36, ( 2) (2.36 3)2 0.4.(2)( 2), 2 a23.82*第三次迭代：a3a2 0, b323.82, 322.36, ( 3)( 2 ) 0.4 3a3 0.382( b3 a3) 0.382(3.82 0) 1.46, ( 3)2(1.46 3)2 2.37 ( 3)( 3 ), b33.82 1.46第四次迭代：a431.46, b4b33.82,432.36,( 4)( 3)0.44a40.618( b

14、4a4)1.460.0.618(3.821.46)2.918,( 4) 0.0067 ( 4)( 4), b43.822.36第五次迭代：a542.36, b5b43.82,54 2.918,( 5)4)0.0067 5a5 0.618(b5( 5)( 5), 5第六次迭代：a6a5 2.36, b66 a6 0.382( b6 a6)( 6 )( 6), b66第七次迭代：a76 2.7045, b7b67a7 0.618( b7 a7)7 7)( 7), b77第八次迭代：a87 2.918, b8 b78 a8 0.618(b8 a8)a5)3.262, ( 5) 0.0686 a5 3

15、.262 2.365 3.262, 65 2.918, ( 6)( 5) 0.0067 ( 8 )( 8 ), 8 a82.7045, ( 6) 0.087 3.262 2.70453.262, 76 2.918,3.049, ( 7) 0.002 3.262, 873.131, ( 8) 0.017 ( 7)( 6) 0.0067 3.049, ( 8)( 7)0.002 第九次迭代:a9 a8 2.918, b93.131, 99 3.049, ( 9)8) 0.002 .9a9 0.382也a9)2.999, ( 9) 0.000001 .(9)( 9),9a93.049 2.91812

16、、用最速下降法求解2min f (x) x1 2x1x22x24x13x2,取 x(0)(1,1)T,迭代两次.f(x) (2xi2x24,2x 4x2 3)T,将f(x)写成f(x)- TT-x Qx b x的形式,第一次迭代:(1) x(0) xf(x(0)T f(x(0)f(x(0)TQ f (x(0)(0) f (x )第二次迭代:(1) x1/4,b0 (0,3) o32 2 (0,3)2 4f(x(1)Tf(x(1) J(1)、f (x ) Q f (x )(3/2,0)(3/ 2,0)1/4f (x )3/2023/23/ 27/41/413、用FR共腕梯度法求解2,min f

17、(x) (x1 x2 x3)( x1x3)2 (Xix2x3)2取x(Y，1,支两次.若给定 0.01,判定是否还需进行迭代计算.解 f (x) 3(X12 X22 X32) 2(XiX2 X1X3 X2X3),一一 ，、1 T再与成 f(x) xTGx, G2第一次迭代:f(x(0)(0,4,0)T ,令 dOf(x(0)(0, 4,0)T,从x(0)出发，沿d°进行一维搜索，即求min f (x(0)do)2 1648 2的最优解,01/6,x(1)x(0)0d0(1/2,1/3,1/2)T .第一次迭代:f(x)(4/3,0,4/3)T .0f(x(1)2f(x(0)2d1f(

18、x(1)0d0 ( 4/3,8/9, 4/3)T .从x(1)出发，沿d1进行一维搜索，即求min f (x(1)di)(2 32121312438943的最优解,3 8,X(1) x1/21/ 31/24/38/94/3(0,0,0) T .此时f(x(2)(0,0,0)T,f(x)0.01得问题的最优解为X (0,0,0) T,无需再进行迭代计算.14、用坐标轮换法求解min f (x) x2 2x2 4x1 2X1X2 ,取 x(0)(1,1)T ,迭代一 步.解 从点x(0)(1,4出发，沿ei (1,0),进行一维搜索，即求mip f(x(0)e) 2 43的最优解，得0 2,x x

19、(0)°e (3,1)T .再从点x(1)出发，沿62 (0,1),进行一维搜索， 即求minf(x(1)62) 2 2 27的最优解，得1 1/2,x(2) x(1)1e2(3,3/ 2)T.15、用 Powell 法求解 min f (x)x；xf 3x1x1x2,取 x(0)(0,0) T ,初始搜索方向组d0 (0,1)T,d1(1,0)T,给定允许误差 0.1 (迭代两次).解第一次迭代：令y(0)x(0)(0,0)T ,从点y(0)出发沿d°进行一维搜索，易得(1)(0)T0 0, y y0d0 (0,0)；接着从点y出发沿d1进行一维搜索，得3(2)(1)3

20、T1 2,y v 1d1(2,0)由此有加速方向d2 yy(0)(3,0)T .2因为忖213/2,所以要确定调整方向.由于 f(y(0) 0,f(y(1) 0,f(y(2)9,按(8.4.17)式有4f(y)f(y(2) maxf(y(j) f(y(j1)| j 0,1, 因此m 1,并且 (m)(m 1)(1)(2)9f(y ) f(y ) f(y ) f(y )二.4又因f(2yy(0) 0,故(8.4.18 )式不成立.于是，不调整搜索方向组，并令 x(1) y(|,0)T.第二次迭代：取y(0)x(|,0)T,从点y(0)出发沿d°作一维搜索，得3(1)(0)3 3 T。4,y y0d0 (2,4) 接着从点y出发沿方向di作一维搜索，得3 x /15 3 ti -, y yidi (,) 88 4由此有加速方向(2)(0)3 3 Td2 y y(8，4) -189 64，916因为d2 375/8,所以要确定调整方向.因f(y(0)9,f(y(1)45,f(y(2)416故按(8.4.17 )式易知m 0,并且f(y(m) f(y(m1)f(y(0) f(y(1)由于f(2y y(0)451