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

1、.第 1 章 最優(yōu)化問題的基本概念§1.1 最優(yōu)化的概念最優(yōu)化就是依據(jù)最優(yōu)化原理和方法，在滿足相關(guān)要求的前提下，以盡可能高的效率求得工程問題最優(yōu)解決方案的過程。§1.2 最優(yōu)化問題的數(shù)學(xué)模型1. 最優(yōu)化問題的一般形式findx1 , x2 , xnmin f ( x1 , x2 , xn )s.t. gu ( x1, x2, xn )0u1,2, phv ( x1 , x2, xn )0v1,2, q2. 最優(yōu)化問題的向量表達(dá)式findXmin f ( X )s.t. G ( X )0H(X)0式中： X x1 , x2 , xn TG( X ) g1 ( X ), g2

2、( X ), g p ( X ) TH ( X )h1 ( X ), h2 ( X ), hp ( X ) T3. 優(yōu)化模型的三要素設(shè)計變量、約束條件、目標(biāo)函數(shù)稱為優(yōu)化設(shè)計的三要素！設(shè)計空間：由設(shè)計變量所確定的空間。 設(shè)計空間中的每一個點都代表一個設(shè)計方案。§1.3 優(yōu)化問題的分類按照優(yōu)化模型中三要素的不同表現(xiàn)形式，優(yōu)化問題有多種分類方法：1 按照模型中是否存在約束條件，分為約束優(yōu)化和無約束優(yōu)化問題2 按照目標(biāo)函數(shù)和約束條件的性質(zhì)分為線性優(yōu)化和非線性優(yōu)化問題3 按照目標(biāo)函數(shù)個數(shù)分為單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化問題4 按照設(shè)計變量的性質(zhì)不同分為連續(xù)變量優(yōu)化和離散變量優(yōu)化問題第 2 章最優(yōu)化問

3、題的數(shù)學(xué)基礎(chǔ)§2.1n 元函數(shù)的可微性與梯度.一、可微與梯度的定義1. 可微的定義設(shè) f ( X ) 是定義在 n 維空間 Rn 的子集 D 上的 n 元實值函數(shù)，且 X 0D 。若存在 n 維向量 L ，對于任意 n 維向量 P ，都有l(wèi)imf ( X 0P) f ( X 0 ) LT P0P0P則稱 f ( X ) 在 X 0 處可微。2. 梯度設(shè)有函數(shù) F(X) ，X x1 , x2 , , xn T ，在其定義域連續(xù)可導(dǎo)。我們把 F ( X ) 在定義域某點 X 處的所有一階偏導(dǎo)數(shù)構(gòu)成的列向量，定義為F ( X ) 在點 X 處的梯度。記為：TF ( X k )F,F, ,F

4、x1 x2xn梯度有 3 個性質(zhì)：函數(shù)在某點的梯度方向為函數(shù)過該點的等值線的法線方向；函數(shù)值沿梯度方向增加最快，沿負(fù)梯度方向下降最快；梯度描述的只是函數(shù)某點鄰域的局部信息。§2.2 極小點及其判別條件一、相關(guān)概念1. 極小點與最優(yōu)解設(shè) f ( X ) 是定義在 n 維空間 Rn的子集 D 上的 n 元實值函數(shù)，若存在X *D 及實數(shù)0，使得XN(X*, )D ( XX * ) 都有 f ( X * ) f ( X ) ，則稱 X *為 f ( X ) 的局部極小點；若f ( X * )f ( X ) ，則稱 X * 為 f ( X ) 的嚴(yán)格局部極小點。若 XD ，都有 f ( X

5、* )f ( X ) ，則稱 X * 為 f ( X ) 的全局極小點，若 f ( X * ) f ( X ) ，則稱 X * 為 f ( X ) 的全局嚴(yán)格極小點。findX對最優(yōu)化問題minf ( X )而言s.t. G ( X )0H(X) 0滿足所有約束條件的向量X x , x, xT 稱為上述最優(yōu)化問題的一個可行解， 全12n體可行解組成的集合稱為可行解集。在可行解集中，滿足：*.2. 凸集和凸函數(shù)凸集：設(shè) DRn ，若對所有的 X 1、 X 2D ，及0,1 ，都有X 1(1) X 2D ，則稱 D 為凸集。凸函數(shù)：設(shè) f : D R nR1 ，D 是凸集，如果對于所有的 X 1、

6、 X 2D ，及0,1 ，都有 f X 1(1)X 2f ( X 1 ) (1) f ( X 2 ) ，則稱 f ( X ) 為 D 上的凸函數(shù)。二、局部極小點的判別條件駐點：設(shè) f ( X ) 是定義在 n 維空間 Rn 的子集 D 上的 n 元實值函數(shù)， X * 是 D 的點，若f ( X * )0 ，則稱 X * 為 f ( X ) 的駐點。局部極小點的判別：設(shè)f ( X ) 是定義在 n 維空間 Rn 的子集 D 上的 n 元實值函數(shù)，具有連續(xù)的二階偏導(dǎo)數(shù)。 若 X * 是 f ( X ) 的駐點，且2 f ( X * ) 是正定矩陣， 則 X * 是 f ( X ) 的嚴(yán)格局部極小點

7、。第 3 章 無約束優(yōu)化方法§3.1 下降迭代算法及終止準(zhǔn)則一、數(shù)值優(yōu)化方法的基本思想基本思想就是在設(shè)計空間選定一個初始點X k ，從該點出發(fā)，按照某一方向Sk （該方向的確定原則是使函數(shù)值下降）前進(jìn)一定的步長k ，得到一個使目標(biāo)函數(shù)值有所下降的新設(shè)計點 X k 1 ，然后以該點為新的初始點， 重復(fù)上面過程， 直至得到滿足精度要求的最優(yōu)點 X* 。該思想可用下式表示： X k 1X kk Sk二、迭代計算的終止準(zhǔn)則工程中常用的迭代終止準(zhǔn)則有3 種：點距準(zhǔn)則相鄰兩次迭代點之間的距離充分小時，迭代終止。數(shù)學(xué)表達(dá)為：X k 1X k函數(shù)下降量準(zhǔn)則（值差準(zhǔn)則）相鄰兩次迭代點的函數(shù)值之差充分小

8、，迭代終止。數(shù)學(xué)表達(dá)為：f ( X k 1 )f ( X k )梯度準(zhǔn)則.目標(biāo)函數(shù)在迭代點處的梯度模充分小時，迭代終止。數(shù)學(xué)表達(dá)為：f ( X k 1 )三、算法的收斂速度對于某一確定的下降算法，其優(yōu)劣如何評價？人們通常采用收斂速度來評價。下面給出度量收斂速度的幾個概念。1. P 階收斂設(shè)序列 X k收斂于解 X *，若存在常數(shù) P0 及 L 、 k0 ，使當(dāng) kk0 時下式：X k 1X *L X kX *p成立，則稱 X k為 P 階收斂。2. 線性收斂設(shè)序列 X k收斂于解 X * ，若存在常數(shù) k0 、 L 及( 0,1) ，使當(dāng) kk0 時下式：X k 1X *L k成立，則稱X k

9、 為線性收斂。3. 超線性收斂設(shè)序列 X k收斂于解 X * ，若任給0 都存在 k00 ，使當(dāng) kk0 時下式：X k 1X *X k X *成立，則稱X k為超線性收斂。§3.2 一維最優(yōu)化方法一、確定初始區(qū)間的進(jìn)退法任選一個初始點x0 和初始步長 h ，由此可確定兩點x1x0 和 x2x1h ，通過比較這兩點函數(shù)值f ( x1 ) 、 f ( x2 ) 的大小，來決定第三點x3 的位置。比較這三點函數(shù)值是否呈“高低高”排列特征，若是則找到了單峰區(qū)間，否則向前或后退繼續(xù)尋求下一點。進(jìn)退法依據(jù)的基本公式：x1x0x2x1hx3x2h具體步驟為：任意選取初始點x0 和恰當(dāng)?shù)某跏疾介L

10、h ；令 x1x0 ，取 x2x1h ，計算 f ( x1 ) 、 f ( x2 ) ；若 f ( x1)f (x2 ) ，說明極小點在x2 右側(cè)，應(yīng)加大步長向前搜索。轉(zhuǎn) ；若 f ( x1)f (x2 ) ，說明極小點在x1 左側(cè)，應(yīng)以 x1 點為基準(zhǔn)反向小步搜索。轉(zhuǎn) ；.大步向前搜索：令h2h ，取 x3x2h ，計算 f (x3 ) ；若 f ( x2 ) f ( x3 ) ，則 f (x1 ) 、f (x2 ) 、f ( x3 ) 呈“高低高” 排列，說明 x1 , x3 即為所求的單峰區(qū)間；若 f ( x2 ) f ( x3 ) ，說明極小點在 x3 右側(cè)，應(yīng)加大步長向前搜索。 此時

11、要注意做變換：舍棄原 x1 點，以原 x2 點為新的 x1 點，原 x3 點為新的 x2 點。轉(zhuǎn) ，直至出現(xiàn)“高 低高”排列，則單峰區(qū)間可得；反向小步搜索（要注意做變換） ：為了保證 x3 點計算公式的一致性，做變換：將原 x2 點記為新 x1 點，原 x1 點記為新 x2點，令 h1 h ，取 x3x2 h ，轉(zhuǎn) 4例：用進(jìn)退法確定函數(shù) f ( x)x 26x9的單峰區(qū)間 a， b ，設(shè)初始點 x00 ， h 1。解： x00h 1 x1x0 0x2x1 h1f (x1 ) 9f (x2 ) 4f ( x1 )f (x2 )說明極小點在 x2 點右側(cè)，應(yīng)加大步長向前搜索令 h2h212，取

12、x3x2h123則 f (x3 )0 f ( x2 ) f ( x3 )說明極小點在 x3 點右側(cè)，應(yīng)加大步長向前搜索舍棄原 x10 的點，令 x11 x23，則 f ( x1 )4 f ( x2 ) 0令 h 2h2 2 4 ，取 x3x2h3 4 7則 f ( x3 ) 16 f ( x2 ) 0f ( x1 ) 、 f (x2 ) 、 f (x3 ) 呈“高低高”排列 x1 ,x 3 為單峰區(qū)間，即區(qū)間 1 ，7 即為所求二、黃金分割法黃金分割法是基于區(qū)間消去思想的一維搜索方法，其搜索過程必須遵循以下的原則：對稱取點的原則：即所插入的兩點在區(qū)間位置對稱；插入點繼承的原則：即插入的兩點中有

13、一個是上次縮減區(qū)間時的插入點；等比收縮的原則：即每一次區(qū)間消去后，單峰區(qū)間的收縮率保持不變。.設(shè)初始區(qū)間為 a ，b ，則插入點的計算公式為：x1a0.382( ba)x2a0.618(ba)黃金分割法的計算步驟如下：給定初始區(qū)間 a ， b 和收斂精度；給出中間插值點并計算其函數(shù)值：x1a0.382(ba)f (x1 )x2a0.618(ba)f (x2 ) ；比較 f ( x1 ) 、 f (x2 ) ，確定保留區(qū)間得到新的單峰區(qū)間 a，b ；收斂性判別：計算區(qū)間a，b長度并與比較，若ba，輸出x*1 (ab)2否則轉(zhuǎn) ；在保留區(qū)間繼承一點、插入一點，轉(zhuǎn)。例：使用黃金分割法求解優(yōu)化問題：m

14、in f(x)x22x，3 x50.2 。解： x1a0.382(ba)30.382(53)0.056f ( x1 )0.115x2a0.618(ba)30.618(53)1.944f ( x2 )7.667 f ( x2 )f ( x1 )舍棄（ 1.944 ，5 ，保留 -3，1.9441.944(3)；繼承原 x1 點，即 x20.056f ( x2 ) 0.115插入 x1a0.382(ba)3 0.382(1.9443)1.111f ( x1 )0.987 f ( x2 )f (x1 )舍棄（ 0.056 ，1.944，保留 -3 ，0.0560.056( 3)；繼承原 x1 點，即

15、 x21.111f ( x2 )0.987插入 xa0.382(ba)3 0.382( 0.0563)1.832fx1 )0.3061( f ( x2 )f (x1 )保留 -1.832，0.0560.056(1.832)；繼承原 x2 點，即 x11.111f (x1 )0.987插入 x21.8320.618(0.0561.832)0.665f (x2 )0.888. f ( x2 )f (x1 )保留 -1.832 ，-0.665如此迭代，到第 8次，保留區(qū)為 -1.111,-0.9400.940 ( 1.111) 0.171 x*1( 1.1110.940)1.0255f ( x* )

16、0.9992§3.3 梯度法一、基本思想對于迭代式 X k 1X kk Sk ，當(dāng)取搜索方向 Skf ( X k ) 時構(gòu)成的尋優(yōu)算法， 稱為求解無約束優(yōu)化問題的梯度法。二、迭代步驟給定出發(fā)點 X k 和收斂精度；計算 X k 點的梯度 F ( X k ) ，并構(gòu)造搜索方向 SkF ( X k ) ；令 X k 1X kk Sk ，通過一維搜索確定步長k ，即：min F ( X kk Sk )求得新點 X k1收斂判斷：若F ( X k 1 )成立，輸出 X *X k 1 、 F ( X * )F ( X k 1 ) ，尋優(yōu)結(jié)束；否則令 kk 1轉(zhuǎn) 繼續(xù)迭代，直到滿足收斂精度要求。

17、三、梯度法的特點梯度法尋優(yōu)效率受目標(biāo)函數(shù)性態(tài)影響較大。若目標(biāo)函數(shù)等值線為圓，則一輪搜索就可找到極致點；若當(dāng)目標(biāo)函數(shù)等值線為扁橢圓時，收斂速度則顯著下降。梯度法中相鄰兩輪搜索方向相互垂直。§3.4 牛頓法牛頓法分為基本牛頓法和阻尼牛頓法兩種。對于迭代式 X k 1X kk Sk ，當(dāng)取k1且搜索方 向 S k2 f (X k ) 1f ( X k ) 時構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的基本牛頓法；對于迭代式 X k 1X kk Sk ，取搜索方向 Sk 2 f ( X k ) 1f ( X k ) ， k為從 X k出發(fā)、沿牛頓方向做一維搜索獲得的最優(yōu)步長，所構(gòu)成的尋優(yōu)算法，稱

18、為求解無約束優(yōu)化問題的阻尼牛頓法。搜索方向 Sk2 f ( X k ) 1f ( X k ) 稱為牛頓方向。.這里需要注意的是會求海塞陣的逆矩陣。§3.5 變尺度法我們把具有 X k 1X kk Ak f ( X k ) 迭代模式的尋優(yōu)算法稱為變尺度法。其搜索方向表達(dá)式為： SkAkf ( X k ) ，稱為擬牛頓方向，其中 Ak 稱為變尺度矩陣。在迭代開始的時候， A0I ；隨著迭代過程的繼續(xù)， Ak2 f ( X k ) 1 f ( X k ) 。因此，變尺度法從梯度法出發(fā)，隨著迭代過程的繼續(xù)最終趨向于牛頓法。§3.6 共軛梯度法一、共軛方向的概念設(shè) H 為對稱正定矩陣

19、， 若有兩個 n 維向量 S1 和 S2 ，滿足 S1THS20 ，則稱向量 S1與 S2 關(guān)于矩陣 H 共軛，共軛向量的方向稱為共軛方向。若有一組非零向量 S1 ， S2 ， ， Sn 滿足 SiT H Sj 0 (ij ) ，則稱這組向量關(guān)于矩陣 H 共軛。對于 n 元正定二次函數(shù)，依次沿著一組共軛方向進(jìn)行一維搜索，最多n 次即可得到極值點。二、共軛方向的形成對于函數(shù) f ( X )f ( x1 , x2 , xn )1XTHX BTX C2沿任意方向X2，令 S1X 2三、共軛梯度法對于迭代式其中： S0S0 在設(shè)計空間上任意做兩條平行線，分別與目標(biāo)函數(shù)等值線切于點X 1 、X 1 ，則

20、 S0 、 S1關(guān)于矩陣 H 共軛。X k 1X kk Sk ，取搜索方向 Sk 1f ( X k 1 )k Skf ( X k21 )f ( X 0 ) ， k2f ( X k)共軛梯度法相鄰兩輪搜索方向是一對共軛方向。§3.7 鮑威爾法基本迭代公式仍舊是：X k 1X kk Sk基本鮑威爾法每輪搜索分為兩步：一環(huán)的搜索 +在該環(huán)搜索完畢后生成的新方向上的一維搜索。對于基本鮑威爾法，相鄰兩輪搜索生成的搜索方向是共軛的。修正鮑威爾法與基本鮑威爾法類似，所不同的是每環(huán)搜索后生成的新方向要利用鮑.威爾條件判別其可用性。注意掌握鮑威爾條件的表達(dá)式和應(yīng)用！每環(huán)搜索方向組的生成：1 第一環(huán)的搜

21、索方向組就是各坐標(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)搜索起點的確定：下一環(huán)搜索起點由本環(huán)搜索結(jié)果確定， 方法是：若本環(huán)的搜索結(jié)果滿足鮑威爾條件，則以本環(huán)搜索終點為起點，沿新生成的方向作一維搜索，得到的新點作為本輪的搜索終點，也是下一輪的搜索起點；若本環(huán)的搜索結(jié)果不滿足鮑威爾條件，則取本環(huán)搜索終點和反射點中目標(biāo)函數(shù)值小的點作

22、為本輪的搜索終點，也是下一輪的搜索起點。這里需要注意的是反射點的計算：X nk2 2X nkX 0k式中： X nk2 是本環(huán)起點 X 0k 相對于本環(huán)終點 X nk 沿新生成方向的反射點。例：對于無約束目標(biāo)函數(shù)minf ( X )x122x224x12x1 x2，利用修正 Powell法從X 01出發(fā)求最優(yōu)解。1解：令 X01 X 01P1P0(e1 , e2 )1X 11X 011101令 f ( X11 ) 0得：2 則： X1131X 21X 110311令 f ( X 21 ) 0得：0.5 則： X 2131.5該環(huán)生成的新搜索方向為：S1X 21X 013121.510.5.對

23、S1 進(jìn)行有效性判別：反射點 X 412X21X 013152121.5f 1f ( X 01 )3f 2f ( X 21 )7.5f 3f (X 41 )71f ( X 01 )f ( X 11 )3 (7)4 ，2 f ( X 11 )f ( X 21 )7 ( 7.5) 0.5故最大下降量m14故： f3f1 和 ( f12 f 2f 3 )( f1f 2m )21m ( f1f 3 ) 2 均成立2方向 S1 可用以 X 12 為起點，沿 S1 方向作一維搜索：X 31X 21S132321.50.51.50.5由 min f ( X 31 )f ( X 21S1)得2 / 50.4故

24、，本輪尋優(yōu)的終點為： X 1X 313.81.7做收斂性判別：X 1X 02.820.7 2，應(yīng)繼續(xù)搜索下一輪尋優(yōu)過程的起點為： X 02X 313.81.7下一輪尋優(yōu)過程的搜索方向組為：(e2 , S1 )第 4 章約束優(yōu)化方法約束優(yōu)化方法要求大家重點掌握懲罰函數(shù)法，包括點法、外點法、混合法。一、外點法構(gòu)造懲罰函數(shù)：pmax gu ( X ),0 2qmin ( X , r k ) f ( X ) r kr k hv ( X )2u 1v1外點法既可以處理不等式約束優(yōu)化問題，又可以處理等式約束優(yōu)化問題。.需要注意的是：懲罰因子 r k隨迭代次數(shù)的增加是遞增的，當(dāng) r k時得到的解就是原問題的

25、最優(yōu)解。例：用外點法求解min f ( X )x12x222x11s.t. 3 x20解：構(gòu)造懲罰函數(shù)( X , r k )x12x222x1 1 r kmax 3x2 ,0 2( X , r k)x12x222x11 r k (3 x2 ) 2當(dāng)3 x20 時x12x222x11當(dāng) 3 x20時令2x1 2 0 x12x22r k (x23) 0x13r k*1*lim x2 3*)9得： x1 1 x2kx1x2f ( x1rk二、點法構(gòu)造懲罰函數(shù)：p1p( X , r k ) f ( X ) r k或： ( X , r k )f ( X )r kln gu (X )u1 gu ( X )

26、u1點法只能處理不等式約束優(yōu)化問題，不能處理等式約束優(yōu)化問題。需要注意的是：懲罰因子r k 隨迭代次數(shù)的增加是遞減的，當(dāng)r k0 時得到的解就是原問題的最優(yōu)解。例：用點法求解約束優(yōu)化問題min f ( X )x1x2s.t.x12x20x10解：構(gòu)造懲罰函數(shù)( X , r k )x1x2 r k ln x2 x12 r k ln x1令1rk2x1rk1x2x120x1x11r kx210x2x12.得 x11 8r k1， x2( 1 8r k1) 2r k416當(dāng) r k0 時，得 x*0f ( x* )00三、混合法構(gòu)造懲罰函數(shù)：p1q( X , r k )f ( X ) r1kr2kh

27、v ( X ) 2u1 gu ( X )v 1pq或： ( X , r k )f ( X )r1klngu ( X )r2khv ( X ) 2u 1v1混合法的特點是：對于不等式約束按照點法構(gòu)造懲罰項，對于等式約束按照外點法構(gòu)造懲罰項?；旌戏瓤梢蕴幚聿坏仁郊s束優(yōu)化問題，也可以處理等式約束優(yōu)化問題。例：用混合懲罰函數(shù)法求解約束優(yōu)化問題min f ( X )x123x2x22s.t.1x10x20解：構(gòu)造懲罰函數(shù)( X , r k )x123x2x22r k ln 1 x1 1k x22r2x1r k1令( X ,r k )1x1032x22x2r k得：x111 2r k， x23211)2(kr當(dāng) r k0 時，得 x*1f ( x* )10第 5章遺傳算法本章要求重點掌握遺傳算法的5 個要素、遺傳算法的尋優(yōu)機(jī)制。一、遺傳算法的5 個要素.1. 編碼將優(yōu)化問題的解編碼，用以模擬生物個體的基因組成；2. 初始種群生成將優(yōu)化問題多個隨機(jī)可行解匯成集合，用以模擬進(jìn)化的生物種群；3. 個體適應(yīng)度評估將優(yōu)化問題目標(biāo)函數(shù)加以變換，生成適應(yīng)度函數(shù)來評價種群個體的適應(yīng)度，用以模擬生物個體對環(huán)境的適應(yīng)能力；4. 遺傳操作包含選擇、交叉、變異選擇：一種使適應(yīng)度函數(shù)值大的個體有更大的存活機(jī)會的機(jī)制，用以模擬環(huán)境對