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

1、第1章最優(yōu)化冋題的基本概念.1最優(yōu)化的概念最優(yōu)化就是依據(jù)最優(yōu)化原理和方法，在滿足相關(guān)要求的前提下，以盡可能高的效率 求得工程問題最優(yōu)解決方案的過程。1.2最優(yōu)化問題的數(shù)學(xué)模型1. 最優(yōu)化問題的一般形式f i n dx1,X2,Xnm i nf (X1,X2,Xn)s.t. gu(X1,X2,，Xn) 0 u =1,2,p hv(X1,X2,，Xn) =0 v=1,2，q2. 最優(yōu)化問題的向量表達(dá)式? i n d Xm i nf(X)s.t. G(X) 0，使得 YX 己 N(X*P)c D(X HX*)都有 f(X*) f(X)，則稱 X* 為 f (X)的局部 極小點(diǎn)；若f(X*)f(X),

2、則稱X*為f(X)的嚴(yán)格局部極小點(diǎn)。, , * * *若VX D，都有f(X ) f(X)，則稱X為f(X)的全局極小點(diǎn)，若f (X ) f (X)， 則稱X*為f(X)的全局嚴(yán)格極小點(diǎn)。find X對最優(yōu)化問題n f (X)而言st. G(X) 0H(X)=0滿足所有約束條件的向量X =Xi，X2，XnT稱為上述最優(yōu)化問題的一個(gè)可行解，全 體可行解組成的集合稱為可行解集。在可行解集中，滿足：f(X*) =mi nf(X)的解稱為優(yōu)化問題的最優(yōu)解。2.凸集和凸函數(shù)凸集：設(shè)D匸Rn，若對所有的X1、X2迂D，及a C 0,1，都有aX1 +(1a)X2壬D，則稱D為凸集。凸函數(shù)：設(shè)f : D U

3、 RnT R1，D是凸集，如果對于所有的X1、X2壬D，及a 0,1，都有 fktX(a)X2Uaf(X1H(a)f(X2),則稱 f(X)為 D 上的凸函數(shù)。、局部極小點(diǎn)的判別條件駐點(diǎn)：設(shè)f(X)是定義在n維空間Rn的子集D上的n元實(shí)值函數(shù)，X是D的內(nèi)點(diǎn)， 若7 f(X*) =0，則稱X*為f(X)的駐點(diǎn)。局部極小點(diǎn)的判別：設(shè)f(X)是定義在n維空間Rn的子集D上的n元實(shí)值函數(shù)，具 有連續(xù)的二階偏導(dǎo)數(shù)。若X*是f (X)的駐點(diǎn)，且V2f(X*)是正定矩陣，則X*是f(X)的 嚴(yán)格局部極小點(diǎn)。三、全局極小點(diǎn)的判別1.凸規(guī)劃對于優(yōu)化問題：盯叢爲(wèi).1.-,p若f(X)、gi(X)都是凸函數(shù)，貝U稱

4、該優(yōu)化問題為凸規(guī)劃。2.全局極小點(diǎn)的判別若優(yōu)化問題為凸規(guī)劃，貝U該優(yōu)化問題的可行集為凸集，其任何局部最優(yōu)解都是全局 最優(yōu)解。(能否證明)第3章無約束優(yōu)化方法3.1下降迭代算法及終止準(zhǔn)則一、數(shù)值優(yōu)化方法的基本思想方向的確定原則是使函數(shù)值下降）前進(jìn)一定的步長 降的新設(shè)計(jì)點(diǎn)Xk半，然后以該點(diǎn)為新的初始點(diǎn)， 的最優(yōu)點(diǎn)X* 0基本思想就是在設(shè)計(jì)空間內(nèi)選定一個(gè)初始點(diǎn)Xk，從該點(diǎn)出發(fā)，按照某一方向S（該 a k，得到一個(gè)使目標(biāo)函數(shù)值有所下 重復(fù)上面過程，直至得到滿足精度要求該思想可用下式表示：Xk=Xk+akSk、迭代計(jì)算的終止準(zhǔn)則工程中常用的迭代終止準(zhǔn)則有3種:點(diǎn)距準(zhǔn)則相鄰兩次迭代點(diǎn)之間的距離充分小時(shí)，迭

5、代終止。 數(shù)學(xué)表達(dá)為：Xk*-Xk|8函數(shù)下降量準(zhǔn)則（值差準(zhǔn)則）相鄰兩次迭代點(diǎn)的函數(shù)值之差充分小，迭代終止。 數(shù)學(xué)表達(dá)為：f(x5)- f (Xk) 梯度準(zhǔn)則目標(biāo)函數(shù)在迭代點(diǎn)處的梯度模充分小時(shí)，迭代終止。 數(shù)學(xué)表達(dá)為：Vf(Xk*) 0及L、ko，使當(dāng)k k。時(shí)下式:|xk X*| ko時(shí)下式:|xk+-X*|kLTk成立，則稱&k 為線性收斂。3.超線性收斂設(shè)序列k 收斂于解X*，若任給P 0都存在ko 0，使當(dāng)k ko時(shí)下式:|xM-x*卜 P|xk x*|成立，則稱&k 為超線性收斂。3.2 一維最優(yōu)化方法一、確定初始區(qū)間的進(jìn)退法任選一個(gè)初始點(diǎn)x0和初始步長h，由此可確定兩點(diǎn)Xj = x

6、0和X2 =為+ h，通過比較 這兩點(diǎn)函數(shù)值f(xi)、f (X2)的大小，來決定第三點(diǎn)X3的位置。比較這三點(diǎn)函數(shù)值是否 呈“高一一低一一高”排列特征，若是則找到了單峰區(qū)間，否則向前或后退繼續(xù)尋求下 一點(diǎn)。進(jìn)退法依據(jù)的基本公式:Xj =X0X3 =X2 +h具體步驟為：任意選取初始點(diǎn)Xo和恰當(dāng)?shù)某跏疾介Lh ；f(Xi)、X2右側(cè),f(X2)；應(yīng)加大步長向前搜索。轉(zhuǎn);令 為=x0，取X2 = x1 + h，計(jì)算若f(Xi)f(X2),說明極小點(diǎn)在若f(Xi) C f(X2)，說明極小點(diǎn)在X1左側(cè),應(yīng)以Xi點(diǎn)為基準(zhǔn)反向小步搜索。轉(zhuǎn);高”排列，說明Xi, X3大步向前搜索：令h= 2h，取XXh，計(jì)

7、算f(x3)； 若 f(X2) f(X3),說明極小點(diǎn)在X3右側(cè)，應(yīng)加大步長向前搜索。此時(shí)要注意做變 換：舍棄原X1點(diǎn)，以原X2點(diǎn)為新的X1點(diǎn)，原X3點(diǎn)為新的X2點(diǎn)。轉(zhuǎn)，直至出現(xiàn)“高一 低一一高”排列，則單峰區(qū)間可得；反向小步搜索(要注意做變換)：為了保證X3點(diǎn)計(jì)算公式的一致性，做變換：將 原x2點(diǎn)記為新xi點(diǎn)，原xi點(diǎn)記為新x2點(diǎn)，令h U -丄h，取X3 = X2 + h，轉(zhuǎn)41。例：用進(jìn)退法確定函數(shù)f(x)=x2-6x+9的單峰區(qū)間a，b,設(shè)初始點(diǎn)X0=O, h =解：寫X0 =0 h =1；.Xj =x0 =0X2 =*4 +h =1 f (xj =9 f (x2)= 4寫 f(Xi)

8、f(X2)說明極小點(diǎn)在X2點(diǎn)右側(cè)，應(yīng)加大步長向前搜索令 hu 2h =2咒1 =2，取 x3 =X2 +h =1 +2=3則 f(X3)=0常 f(X2)A f(X3)說明極小點(diǎn)在X3點(diǎn)右側(cè)，應(yīng)加大步長向前搜索舍棄原x1 =0的點(diǎn)，令Xj = 1 X2 = 3，則f (x1)=4 f(X2)= 0令 hu2h=2%2=4，取 x3=X2+h=3+4 = 7則 f(X3)=16 A f(X2)=0、f(X2)、f(X3)呈“高一一低一一高”排列/.Xi,X3為單峰區(qū)間，即區(qū)間1，7即為所求、黃金分割法黃金分割法是基于區(qū)間消去思想的一維搜索方法，其搜索過程必須遵循以下的原則：對稱取點(diǎn)的原則：即所插

9、入的兩點(diǎn)在區(qū)間內(nèi)位置對稱；插入點(diǎn)繼承的原則：即插入的兩點(diǎn)中有一個(gè)是上次縮減區(qū)間時(shí)的插入點(diǎn);等比收縮的原則：即每一次區(qū)間消去后，單峰區(qū)間的收縮率A保持不變。設(shè)初始區(qū)間為a，b，則插入點(diǎn)的計(jì)算公式為:x1 =a +0.382(b-a)X2 =a +0.618(b a)黃金分割法的計(jì)算步驟如下： 給定初始區(qū)間a，b和收斂精度名; 給出中間插值點(diǎn)并計(jì)算其函數(shù)值：Xj =a+0.382(ba)f (X1)X2 = a+0.618(b-a) f (x2).?比較f(Xi)、f(x2)，確定保留區(qū)間得到新的單峰區(qū)間a, b；收斂性判別：計(jì)算區(qū)間a, b長度并與s比較，若b-a s ;繼承原 x1 點(diǎn)，即 X

10、2 =0.056 f(X2)=0.115插入 xa +0.382(b -a) = 3 +0.382x(1.944 + 3) = 1.111 f (xj = -0.987V f(X2) f (xj舍棄(0.056 , 1.944，保留-3 , 0.0560.056-(3)名;繼承原 X1 點(diǎn)，即 X2=1.111f(X2)=0.987插入 為=a +0.382(b -a) = -3+0.382 咒(0.056 +3) = -1.832f (x1H -0.306V f(x2 f (x1)保留-1.832 ,0.0560.056(1.832) s ;繼承原 X2 點(diǎn)，即 X1=-1.111f(X1)

11、=-0.987插入 X2 = -1.832 +0.618x(0.056 +1.832) = -0.665f (x2H -0.888 f(X2) f(X1)保留-1.832 , -0.665如此迭代，到第8次，保留區(qū)為-1.111,-0.940_0.940 -(1.111) =0.171 8 X* 二丄咒匸行“ +0.940) = -1.0255f(x*) =0.99923.3梯度法、基本思想對于迭代式Xk=Xk+akSk，當(dāng)取搜索方向Sk =Xf(Xk)時(shí)構(gòu)成的尋優(yōu)算法，稱 為求解無約束優(yōu)化問題的梯度法。、迭代步驟給定出發(fā)點(diǎn)xk和收斂精度計(jì)算Xk點(diǎn)的梯度F(Xk)，并構(gòu)造搜索方向S-VF(Xk

12、)；令X心=xk乜kSk，通過一維搜索確定步長ak，即: L /k . k k .min F (X S )2成立，輸出X* =Xk*、F(X*) =F(X心)，尋優(yōu)結(jié)求得新點(diǎn)收斂判斷：若IVF(Xk)|束；否則令k= k+1轉(zhuǎn)繼續(xù)迭代，直到滿足收斂精度要求。三、梯度法的特點(diǎn)梯度法尋優(yōu)效率受目標(biāo)函數(shù)性態(tài)影響較大。若目標(biāo)函數(shù)等值線為圓，則一輪搜索就 可找到極致點(diǎn)；若當(dāng)目標(biāo)函數(shù)等值線為扁橢圓時(shí)，收斂速度則顯著下降。梯度法中相鄰兩輪搜索方向相互垂直。(是否會(huì)證明) 3.4牛頓法牛頓法分為基本牛頓法和阻尼牛頓法兩種。= -2f(xk)-Vf(xk)時(shí)對于迭代式xk+ = xk +ksk，當(dāng)取k三1且搜索

13、方向Sk構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的基本牛頓法；對于迭代式XkP=Xk+akSk，取搜索方向Sk =-W2f(Xk)d可f(Xk)，k為從xk出發(fā)、沿牛頓方向做一維搜索獲得的最優(yōu)步長，所構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu) 化問題的阻尼牛頓法。搜索方向Sk =TV2f(xk)dVf(xk)稱為牛頓方向。這里需要注意的是會(huì)求海塞陣的逆矩陣。3.5變尺度法我們把具有Xk屮=Xk-akAf(Xk)迭代模式的尋優(yōu)算法稱為變尺度法。2其搜索方向表達(dá)式為:在迭代開始的時(shí)候,sk = Apf(xk)，稱為擬牛頓方向，其中Ak稱為變尺度矩陣。A0=l ;隨著迭代過程的繼續(xù)，AkT J于f(Xk)L叭(

14、Xk)。因此，變尺度法從梯度法出發(fā)，隨著迭代過程的繼續(xù)最終趨向于牛頓法。3.6共軛梯度法一、共軛方向的概念設(shè)H為對稱正定矩陣，若有兩個(gè)n維向量S1和S2,滿足SiTS2 = 0 ,則稱向量S與S關(guān)于矩陣H共軛，共軛向量的方向稱為共軛方向。若有一組非零向量Si，S2，Sn滿足ST H ”Sj =0(i工j)，則稱這組向量關(guān)于 矩陣H共軛。對于n元正定二次函數(shù)，依次沿著一組共軛方向進(jìn)行一維搜索，最多n次即可得到極值點(diǎn)。、共軛方向的形成1對于函數(shù) f(X f(x1,x2 ,xn) =-XThX +bTx +C2沿任意方向S0在設(shè)計(jì)空間上任意做兩條平行線，分別與目標(biāo)函數(shù)等值線切于點(diǎn) X1、X2，令S1

15、 = x2 -X1，則S0、S1關(guān)于矩陣H共軛。(能否給出證明)三、共軛梯度法對于迭代式Xk+ = xk +aksk，取搜索方向Sk+ =Xf(Xk+) + PkSk其中：s0=Xf(X0)，Pk =可(Xk + ) Ff(xk)共軛梯度法相鄰兩輪搜索方向是一對共軛方向。3.7鮑威爾法基本迭代公式仍舊是：xk十=X k +aksk基本鮑威爾法每輪搜索分為兩步：一環(huán)的搜索 +在該環(huán)搜索完畢后生成的新方向上的一維搜索。對于基本鮑威爾法，相鄰兩輪搜索生成的搜索方向是共軛的。修正鮑威爾法與基本鮑威爾法類似，所不同的是每環(huán)搜索后生成的新方向要利用鮑 威爾條件判別其可用性。注意掌握鮑威爾條件的表達(dá)式和應(yīng)用

16、!每環(huán)搜索方向組的生成:1第一環(huán)的搜索方向組就是各坐標(biāo)軸方向2 .下一環(huán)的搜索方向組由本環(huán)搜索方向組和本環(huán)生成的新方向共同確定，方法是： 若本環(huán)的搜索結(jié)果滿足鮑威爾條件， 則將本環(huán)搜索方向組中使目標(biāo)函數(shù)下降量最大的方 向去掉，并將本環(huán)生成的新方向遞補(bǔ)進(jìn)去，就形成下一環(huán)的搜索方向組；若本環(huán)的搜索 結(jié)果不滿足鮑威爾條件，則下一環(huán)的搜索方向組仍舊沿用本環(huán)搜索方向組不變。下一環(huán)搜索起點(diǎn)的確定:下一環(huán)搜索起點(diǎn)由本環(huán)搜索結(jié)果確定，方法是：若本環(huán)的搜索結(jié)果滿足鮑威爾條件, 則以本環(huán)搜索終點(diǎn)為起點(diǎn)，沿新生成的方向作一維搜索，得到的新點(diǎn)作為本輪的搜索終點(diǎn)，也是下一輪的搜索起點(diǎn)；若本環(huán)的搜索結(jié)果不滿足鮑威爾條件，

17、則取本環(huán)搜索終點(diǎn) 和反射點(diǎn)中目標(biāo)函數(shù)值小的點(diǎn)作為本輪的搜索終點(diǎn)，也是下一輪的搜索起點(diǎn)。這里需要注意的是反射點(diǎn)的計(jì)算：X爲(wèi)=2Xnk -Xok式中：Xk七是本環(huán)起點(diǎn)Xok相對于本環(huán)終點(diǎn)Xk沿新生成方向的反射點(diǎn)。例:對于無約束目標(biāo)函數(shù) minf (X)+2x2 -4xi -2xX2，利用修正 Powell 法從X0=出發(fā)求最優(yōu)解。解:令 x0=x0 _1 _ 0p= P=(e,e2)X； =x0 乜0令 f (xl) -。得：a =2則：xl=【3令 f X 2)=0 得：a = 0.5 貝U: x21h5該環(huán)生成的新搜索方向?yàn)椋篠1 = x2-x(1435引尤對s1進(jìn)行有效性判別:反射點(diǎn)X1 =

18、2X2 -x0-*1511.512f1 =f(x0)=3f2= f(x2) = 7.5f3 = f(x4)=7Ai = faOlfMi1)二3 (7) =4，也 2 = f (Xi1) - f(x2) =7-(7.5) =0.5故最大下降量im =d =4故：f3f1 和(f1-2f2+f3)(f1-f2m)2m(f1-f3)2 均成立方向S1可用以x2為起點(diǎn)，沿S1方向作一維搜索:x3 =x2 + J31+訂2 13 21.5卜丄3 + 2 I0.51.5 + 0.50由 min f(x3)= f(X2 + aS1)得=2/5 =0.4故，本輪尋優(yōu)的終點(diǎn)為：X1 = x3 =；.；做收斂性判別：=丿2.82 +0.72，應(yīng)繼續(xù)搜索x x0下一輪尋優(yōu)過程的起點(diǎn)為：x2 - x3 = F8!L1.7下一輪尋優(yōu)過程的搜索方向組為：2, S1) 繼續(xù)依樣搜索直至滿足收斂精度解：構(gòu)造懲罰函數(shù)*(X,rk)(X,rki ；:臺(tái)+X2k-2X, +1+r (3-X2)-2% +1令旦cx1=2捲-2 =0cx1= 2x2