《最優(yōu)化方法》復(fù)習(xí)題

1、最優(yōu)化方法復(fù)習(xí)題一、 簡述題1、怎樣判斷一個函數(shù)是否為凸函數(shù)(例如：判斷函數(shù)f(x) 2x1x2 - 2x2 - 10x! 5x2是否為凸函數(shù))2、寫出幾種迭代的收斂條件.3、 熟練掌握利用單純形表求解線性規(guī)劃問題的方法(包括大M法及二階段法)見書本61頁(利用單純形表求解)；69頁例題(利用大M法求解、二階段法求解);4、簡述牛頓法和擬牛頓法的優(yōu)缺點.簡述共軛梯度法的基本思想.寫出Goldstein、Wolfe非精確一維線性搜索的公式。5、敘述常用優(yōu)化算法的迭代公式.(1) 0.618法的迭代公式：k乜血一比)J - 二 ak (bk - ak).k 二 ak|(bk aQ,(2) Fib

2、on acci法的迭代公式:(k",2，n-1) FnJj*-k 二 ak(bk - ak )Fn_k 1(3) Newton一維搜索法的迭代公式：xk沖=xk - Ggk 1(4) 推導(dǎo)最速下降法用于問題 min f(x)二-xTGx bTx c的迭代公式:2TXk 廠 Xk-罟J'f(Xk)gk Gkgxk(5) Newton法的迭代公式：xk 彳=xk -八 2 f (xk) " f (xk).1(6) 共軛方向法用于問題min f(x) hTQx bTx c的迭代公式:dkTQdk、計算題雙折線法練習(xí)題 課本135頁 例3.9.1FR共軛梯度法例題：課本15

3、0頁 例4.3.5二次規(guī)劃有效集：課本213頁例6.3.2,所有留過的課后習(xí)題二、練習(xí)題：1、 設(shè)A Rn n是對稱矩陣，b Rn, cR，求f (x) =*xTAx bTx c在任意點x處 的梯度和Hesse矩陣.解 l f (x)二 Ax b, I f (x)二 A .2、 設(shè)()=f：x d ),其中 f : Rn )R二階可導(dǎo)，Rn,d Rn,t R，試求:(t).解 ：(t)八 f(x td) Td,(t) =dT'、2f (x td)d .3、證明：凸規(guī)劃min f(x)的任意局部最優(yōu)解必是全局最優(yōu)解.證明 用反證法.設(shè)S為凸規(guī)劃問題min f (x)的局部最優(yōu)解，即存在x

4、的某X手個鄰域N、.(x)，使f (x)乞f (x),-x. N.(x) S .若x不是全局最優(yōu)解，則存在x S，使f(x) :： f (x).由于f(x)為S上的凸函數(shù)，因此 -'(0,1)，有f( x (1 - )x) _ f (乂)(1 一 ) f (x) ： f (x).當'充分接近1時，可使 x - (1)x N (x) S，于是f (壬)乞f ( x - (1-%)x)，矛盾.從而x是全局最優(yōu)解.'min f (x) =2捲 _x2+x3;s.t 3禺 +x2 +x；3 蘭 60,4、已知線性規(guī)劃：x -2x2 2x3 -10,X1 +X2 x3 蘭 20,

5、X1,X2,X30.(1) 用單純形法求解該線性規(guī)劃問題；(2) 寫出線性規(guī)劃的對偶問題； 解 (1)引進變量X4,X5,X6，將給定的線性規(guī)劃問題化為標準形式:Lmin f (x) =2為x2 + x3;|s.t 3捲 +x2 +x3 +x4 =60,cX| 2x2 +2x3 +花=10,為十 X2 X3 +X6 =20,為，X2,X60.所給問題的最優(yōu)解為X = (0,20,0)T，最優(yōu)值為f = _20 .(2)所給問題的對偶問題為："max g(y) = -60% _10y2 _20y3;S.t 一3 y! - y2 - y3 蘭 2,'一 yi +2y2 y3 蘭

6、一1,一 yi 2丫2 + y3 蘭1,yi,y2,y0.0.2 , 初5、用0.618法求解min(t) =(t-3)2，要求縮短后的區(qū)間長度不超過始區(qū)間取0,10 解第一次迭代：取力=0,10, ； 72 .確定最初試探點”人分別為a1 - 0.382(0 -印)=3.82 , 7=60.618(6 -印)=6.18 .求目標函數(shù)值：1)=(3.82 -3)2 =0.67 ,:(1)=(6.18 -3)2 =10.11 .比較目標函數(shù)值：(叫).比較叫 =6.18 -0 0.2 =；.第二次迭代：a2 = ai =0, d =叫=6.18, "2 = = 3.82, '(

7、"2) = (' J = 0.67 .2 二 a2 0.382(6 a2) =0.382(6.18 -0) =2.36, ：( 2 )= (2.36 - 3)2 = 0.4 .('2)：(2)2 a? =3.82；.第三次迭代：a3 - a - 0,- "2 二 3.82,打二 '2 - 2.36,( °；) = (' 2)= 0.4 .'3 =a3 0.382(6 -a?) =0.382(3.82 -0) =1.46,：(乜)=(1.46 -3)2 =2.37 .(3)(叮)，b3 - 3 =3.82 -1.46；.第四次

8、迭代:a - 3 = 1.46,匕4 =匕3 = 3.82, w = ”3 = 2.36, '(計)=(”3) = 0.4 .J4 二a4 0.618(b4 -a4) =1.46 0.0.618(3.82 一 1.46) = 2.918, (1)= 0.0067 .( 4)：(%), b4 - 4 =3.82 -2.36 ；.第五次迭代：a5 =，4 =2.36, b5 二 b4 =3.82, ”=2.918,(飛)=(叮)=0.0067 .=a5 0.618(b5 -a5) =3.262, ：(%) =0.0686 .( 5)：(5), % a5 =3.262 2.36 ；.第六次迭

9、代：a6 =a5 =2.36, b6 二二5 =3.262, % =?；5 =2.918,()=即(5) =0.0067 .6 =a60.382(176)=2.7045, (6) =0.087 .('6)(%), b6 - 飛=3.262 -2.7045；.第七次迭代：a7 二，6 =2.7045, b = b6 =3.262,二 = 2.918,('7) = (%) = 0.0067 .J7 二 a70.618(4 a7) =3.049, Vl7H 0.002 .(d) (S, 6 -；.第八次迭代：a8 = -7 =2.918, b8 =b7 =3.262, 8 二,3.0

10、49, (8) = (») =0.002 .J8 二a* 0.618(b8 -a*) =3.131, (J =0.017 .(AZ, 8 .第九次迭代：a?二a* =2.918, b =3.131,需='9 =3.049, (；) =(8)= 0.002 .9 =a9 0.382(b9 -a9) =2.999, (9) =0.000001 .;：('9) f 9), % a? =3.049 2.918 ：；.故滅二"9 =3.024 .26用最速下降法求解min f (x) = x1 2x-|X2 2x；-4為-3x2,取x(0) =(1,1仁迭代兩次.解

11、l f (x)二(2片 2x2 _4,2x, 4x2 _3)丁 ,2 2、Q =,b =<2 4<_3>1將f (x)寫成f(x) = xtGx bTx的形式，則2第一次迭代:x(1)= x(0)(0)、T(0)f(x ) f(x ) Vf(x(0)v f (x(0) )TG f (x(0)(0,3)(0,3)l3丿(0y' 1 '2、I(0l3丿W 4丿2<2 4 人3第二次迭代:x(2)弘弓丁叫Vf(x)f(x(1)TGf(x(1)(-3/2,0)-3/201/4丿(-3/2,0)-3/2)*7/4)z2 2 丫-3/ 2 I 0 <2 4 &

12、#39;'1/4丿7、用FR共軛梯度法求解1 1min f (x)=(人-X2X3)2(-捲x?X3)2(xx?乜)2，取x(0)= (,1,)T，迭代2 2兩次.若給定；-0.01,判定是否還需進行迭代計算.解 f (x) =3(x12 x22 x32) -2(x2 x-|x3 x2x3),'6-2-乞1再寫成 f(x)= xTGx , G =-26-2，可f (x) =Gx .212-26丿第一次迭代：lf(x®) =(0,4,0) T，令 d。=f(x®) =(0,-4,0)t ,從x(0)出發(fā)，沿do進行一維搜索，即求min f (x(0)d。)=2

13、一1648,的最優(yōu)解,-得0 =1/6,x二x(0) d。=(1/2,1/3,1/2)丁 .第一次迭代：I f (x)=(4/3,0,4 /3)t . ： 0 二N(x)|f(x(0)d, - -f(x(1)： 0d0=(-4/3,-8/9,-4/3)T.從X出發(fā)，沿di進行一維搜索，即求-2-2min f (x"，©) =(1 -4 '-0231 8 ,-4 )3923-2-2的最優(yōu)解，得'11 2、3,x(2)=x=1/ 3+3£/988<1/2>日/3丿二(0,0,0) T.1 =f(x此時)=(0,0,0) T,| 可(x)|

14、=0c0.01 =得問題的最優(yōu)解為x = (0,0,0)T，無需再進行迭代計算.8、求解問題 (方法不限定)min f x = 1 x； - x| -5x1 -10x22 2s.t 2x. -3X2 蘭 30取初始點(0,5 )丁 .x4x2 - 20x-i,x-09、采用精確搜索的 BFGS算法求解下面的無約束問題：1 2 2 min f (x)x1 xx1x22解：取 x(0)=(1,1)TB0 = Ilf(x)二* -x2 0x2 - x!第一步迭代:W(X(0)=(°)d(0) =B0Ff(X(0)=卩)J丿l-1丿1C- ) = f(x(0) rd)(1-. )2 ，令()

15、=0，求得o =1/2;2o o_-11Jo 11 o_-°卜1/21 一 j-112B1 珂 f(x)=G ） = f （x心d），令“（：）= 0，求得宀毛。故x(2)1°丿，由于"（X），故x為最優(yōu)解。第二步迭代：1、1、x=x（0）+%d（0）=1，京 f(x(1) =2，s（1、22丿(0)10、用有效集法求解下面的二次規(guī)劃問題:x；_4x22min f (x)二 x1st. -xi -x2 1 亠 0x1 _ 0, x2 _ 0.解：取初始可行點 x(0) =(0,0),傀=A(x®) =2,3.求解等式約束子問題min d； d； -2d1

16、 -4d2s.t d1 =0,d2 =0得解和相應(yīng)的Lagrange乘子d(0) =(0,0)T, (-2, 4)t故得x=x(0) =(0,0)T,A 二人 3二2轉(zhuǎn)入第二次迭代。求解等式約束子問題2 2min d1 d2 -2d1 -4d2st dr = 0得解d = (0, 2)0.T 0 q x耳=min1,-(rp-a, d計算T (1)"3,航(：0=-a, d令x=x(1)：&=(0,1)T,A2 二 Ai 1二1,2轉(zhuǎn)入第三次迭代。求解等式約束子問題min d12 d| -2d1 -2d2s.t d1 +d2 = 0, d1 = 0得解和相應(yīng)的Lagrange

17、乘子= (0,0)T,。2,0)由于_0 ,故得所求二次規(guī)劃問題的最優(yōu)解為*(2)/C 八Tx 二X =(0,1)，相應(yīng)的Lagrange乘子為'二(2,0,0) T最速下降法的優(yōu)缺點：優(yōu)點：方法簡單，計算量較?。蛔钏傧陆捣槿质諗?，對初 始點的要求很少。缺點：最速下降法的收斂速度與變量的尺度關(guān)系很大，對有些 例子，在極小點附近產(chǎn)生顯著的鋸齒現(xiàn)象，收斂十分緩慢；最 速下降法的最速下降僅是一種局部性質(zhì)，即從局部來看目標函數(shù) 的值下降得最快，但從總體來看它可能走了許多彎路。牛頓法的優(yōu)缺點： 優(yōu)點：牛頓法的收斂速度快，為二階收斂；公式簡單， 計算方便。缺點：牛頓法要求 f（x） 二階可微，迭代中需多次計算 ；牛頓法具有局部收斂性，對初始點的要求比較苛刻。 共軛梯度法的優(yōu)缺點： 優(yōu)點：計算公式簡單，存儲量較小，對初始點要求很少，對二 次函數(shù)具有二次終止性；收斂速度介于最速下降法和牛頓法之 間，對高維（