附錄5最優(yōu)化方法復(fù)習題

1、k附錄5最優(yōu)化方法復(fù)習題1、設(shè)A Rnn是對稱矩陣，b Rn,c R，求f(x)1-xtAx bTx c在任意點x處2 的梯度和Hesse矩陣.解 f(x) Ax b, 2f (X) a .2、設(shè)(t)f (X td)，其中f :Rn R二階可導(dǎo)，XRn,dRn,t R，試求(t).解 (t)TT 2f(x td) d, (t) d f(X td)d .3、設(shè)方向d Rn是函數(shù)f(X)在點x處的下降方向,% S，使 f (%f(X).由于f(X)為S上的凸函數(shù)，因此H I ddT f(x) f(x)T dT f(x)f(x)T f(x)其中I證明為單位矩陣，證明方向P H f(x)也是函數(shù)f

2、(X)在點X處的下降方向.由于方向d是函數(shù)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是函數(shù)f(x)在點X處的下降方向.4、 SRn是凸集的充分必要條件是m 2, X1, X2,L , Xm S,X1,X2丄,Xm的一切凸組合都屬于S .證明 充分性顯然.下證必要性.設(shè)S是凸集，對m用歸納法證明.當m 2時,k 1iX，i 1由凸集的定義知結(jié)論成立，下面考慮 m k 1時的情形.令X其中Xik 10, i 1, 2, L , k

3、 1，且 i 1.不妨設(shè) k 11 (不然 X xk 1 S，i 1結(jié)論成立)，記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則由歸納假設(shè)知，y s,而Xk i S ,且S是凸集，故Xf為S上的凸函數(shù)的5、設(shè)S Rn為非空開凸集，f : S R在S上可微，證明:充要條件是f(X2)f (Xi)f (Xi)T(X2Xi),Xi,X2證明必要性.設(shè)f是S上的凸函數(shù),則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為凸函數(shù).6證明：凸規(guī)劃min f (x)的任意局部最優(yōu)解必是全局最優(yōu)解.證明用反證法.設(shè)X S為凸規(guī)劃問題minf(X)的局

5、部最優(yōu)解，即存在X的某X S個鄰域N (X)，使f (X)f(X), X N (X)I S .若X不是全局最優(yōu)解，則存在(0,1)，有f( x (1)% f(x)(1)f()% f(x).當 充分接近1時，可使 x (1)% N (x)| S，于是f(x) f( x (1)%矛盾.從而x是全局最優(yōu)解.7、設(shè)S Rn為非空凸集，f : S R是具有一階連續(xù)偏導(dǎo)數(shù)的凸函數(shù)，證明：X是問題min f (x)的最優(yōu)解的充要條件是:f (x)T(x x) 0, X S .證明 必要性.若X為問題min f(x)的最優(yōu)解.反設(shè)存在 S，使得X Sf (x)T(% x) 0,則d % x是函數(shù)f (x)在點

6、x處的下降方向，這與x為問題min f(x)的最優(yōu)解矛盾.故f(X)T(x x) 0, x S .充分性.若 f(X)T(x X) 0, X S .反設(shè)存在)% 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)的最優(yōu)x S解.8、設(shè)函數(shù)f(x)具有二階連續(xù)偏導(dǎo)數(shù)，Xk是f(x)的極小點的第k次近似，利用f(x)在點Xk處的二階Taylor展開式推導(dǎo)Newton法

7、的迭代公式為2 1Xk 1Xk f (Xk)f (Xk).證明 由于f(x)具有二階連續(xù)偏導(dǎo)數(shù)，故Xk)T 2f (Xk)(X Xk).為求 (X)的極小點，可令1f (x)(x)f(Xk)f (Xk)T(x Xk) -(X且2f(xk)是對稱矩陣，因此(X)是二次函數(shù).(X) 0，即 卩 f(Xk)2f(Xk)(x Xk) 0,若 2f(Xk)正定，則上式解出的(X)的平穩(wěn)點就是(X)的極小點，以它作為f (x)的極小點的第k 1次近似，記為Xk 1，即Xk 1 Xk 2 f (Xk) 1 f (Xk)，這就得到了 Newton法的迭代公式.9、敘述常用優(yōu)化算法的迭代公式.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、已知線性規(guī)

9、劃:min f (x)2為x2 x3;s.t. 3x1x22x2X2x360,2x310,x320,為，X2,X30.(1)(2)dkTQdk用單純形法求解該線性規(guī)劃問題的最優(yōu)解和最優(yōu)值;寫出線性規(guī)劃的對偶問題;求解對偶問題的最優(yōu)解和最優(yōu)值.解 (1)引進變量X4,X5,X6，將給定的線性規(guī)劃問題化為標準形式: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所給問題的最優(yōu)解為X (0, 20,0)T，最優(yōu)值為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ōu)解為y問題(1)的最優(yōu)解為y(0,0,1)T，最優(yōu)值為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，最優(yōu)值為h 20 (最小值).11、用0.618法求解 min (t) (t 3)2，要求縮短后的區(qū)間長度不超過0.2，初 始區(qū)間取0,10.解第一次迭代:取亦0,10,0.2確定最初試探點1分別為1 a10.382(b1

12、印)3.82 ,1 a 0.618(b1 a1)6.18 .求目標函數(shù)值:(1)(3.823)20.67 ,( 1)(6.18 3)210.11.比較目標函數(shù)值:(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)出發(fā)，沿d0進行一維搜索,即求 min f(X®do)2 1648 2的最優(yōu)解,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出發(fā)，沿d1進行一維搜索，即求min f(x1 4 1 8 1 41) (2 3 ,3 9 ,2 312131243894的最優(yōu)解，得3此時31-,X()1/24/3X1d11/338/9881/24/3f(x )(0,0,0)T,| f(x(2)|00.01(0,0,0) T 得問題的最優(yōu)解為x (0,0,0) T，無需再進行迭代計算.14、用坐標輪換法求解min f (x) x： 2xf 4為2%2，取x(0)(1,1)T，迭代步.解從點x(0)(1,1)T出發(fā)，沿ei (1

18、,0)T進行一維搜索,即求 min f(x(0)e) 2 43的最優(yōu)解，得2,x1/2,x(2)X x®00(3,1)T .再從點X出發(fā),沿e2(0,1)T進行一維搜索,即求minfde2)2 2 27的最優(yōu)解，得程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®出發(fā)沿d0進行一維搜索，易得00, y y(0)0d0(0,0)T ；接著從點y出

19、發(fā)沿d1進行一維搜索，得3 (2)(1)/3 c、T1 2,y y1d1 (2,0)由此有加速方向d2 yy®(|,0)T .因為lldzll 3/2，所以要確定調(diào)整方向.由于什)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 )式不成立.于是，不調(diào)整搜索方向組，并令 Xy(2)(|,0)T .第二次迭代：取y®X(|,0)T，從點y(0)出發(fā)沿d0作一維搜索，得3 (1)(0)/3 3T0 ；,y y0*

20、(；,；) 4 2 4接著從點y出發(fā)沿方向d1作一維搜索，得3 (1)Z15 3 T1 8，y V1d1 (討-由此有加速方向d2 y(2) y(0)(|'|)T -因為|d2|3亦/8 ，所以要確定調(diào)整方向.因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出發(fā)沿d2作一維搜索，得2d2 (2,1)T o1 2 -,x()y()3同時，以d2替換d0，即下一次迭代的搜索方向組取為33d0 (訶,d1(打16、用外罰函數(shù)法在直線 x y 1上求一點P(x,y)，使得P到原點0(0,0)的距離近似最短，取1 0.5,2,1° 4解令 f (x, y) x2y2，問題可歸為求解如下最優(yōu)化問題2 2min f (x, y) x y ;s.t. h(x, y) x y 10.引入罰函數(shù)F(x,y,'22/八 2k) x y k(x y 1).則原約束最優(yōu)化問題相應(yīng)的一系列無約束最優(yōu)化問題為:min F(x, y, k)，其中1°.5,k2 k,k1,