最優(yōu)化方法復習資料

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

2、 .優(yōu)化模型的三要素設計變量、約束條件、目標函數稱為優(yōu)化設計的三要素！設計空間：由設計變量所確定的空間。設計空間中的每一個點都代表一個設計方案。1.3優(yōu)化問題的分類按照優(yōu)化模型中三要素的不同表現形式，優(yōu)化問題有多種分類方法：1 按照模型中是否存在約束條件，分為約束優(yōu)化和無約束優(yōu)化問題2 按照目標函數和約束條件的性質分為線性優(yōu)化和非線性優(yōu)化問題3 按照目標函數個數分為單目標優(yōu)化和多目標優(yōu)化問題4 按照設計變量的性質不同分為連續(xù)變量優(yōu)化和離散變量優(yōu)化問題第 2 章 最優(yōu)化問題的數學基礎2.1 n元函數的可微性與梯度一、可微與梯度的定義1 .可微的定義設 f(X)是定義在n維空間 Rn的子集D上的n

3、 元實值函數，且X0 D 。若存在n維向量 L ，對于任意n 維向量 P ，都有f(X0 P) f(X0) LTPlPim0P0則稱f ( X )在 X0處可微。2 .梯度設有函數F(X) ， X x1,x2, ,xnT，在其定義域內連續(xù)可導。我們把F(X) 在定義域內某點X 處的所有一階偏導數構成的列向量，定義為 F (X)在點 X處的梯度。記為：k F F FTF(Xk), ,x1 x2x n梯度有 3 個性質：函數在某點的梯度方向為函數過該點的等值線的法線方向；函數值沿梯度方向增加最快，沿負梯度方向下降最快；梯度描述的只是函數某點鄰域內的局部信息。2.2極小點及其判別條件一、相關概念1

4、.極小點與最優(yōu)解設 f(X)是定義在n 維空間Rn的子集D上的 n 元實值函數，若存在X* D 及實數0，使得X N(X*, ) D(X X*) 都有f(X*) f(X)，則稱X* 為 f(X)的局部極小點；若f(X*) f(X)，則稱 X* 為 f ( X)的嚴格局部極小點。若 X D ， 都有 f ( X * ) f ( X ) ， 則稱 X * 為 f ( X ) 的全局極小點，若 f ( X * ) f ( X ) ，則稱 X* 為 f ( X)的全局嚴格極小點。find Xmin f (X) 對最優(yōu)化問題而言s.t. G(X ) 0H(X) 0滿足所有約束條件的向量X x1,x2,

5、,xnT 稱為上述最優(yōu)化問題的一個可行解，全體可行解組成的集合稱為可行解集。在可行解集中，滿足：f (X*) mi n f ( X)的解稱為優(yōu)化問題的最優(yōu)解。2.凸集和凸函數凸集： 設 D Rn， 若對所有的X1、 X2 D ， 及 0,1， 都有 X1 (1 )X2 D ，則稱 D 為凸集。凸函數： 設 f : D RnR1， D 是凸集， 如果對于所有的X1、 X2 D ， 及 0,1，都有 f X1 (1 )X2 f (X1) (1 )f(X2)，則稱 f(X)為 D 上的凸函數。 二、局部極小點的判別條件駐點：設f(X)是定義在n維空間 Rn的子集D上的n 元實值函數，X*是 D 的內

6、點，若 f(X*) 0，則稱 X*為 f(X)的駐點。局部極小點的判別：設f(X)是定義在n維空間Rn的子集D 上的 n 元實值函數，具有連續(xù)的二階偏導數。若 X*是 f (X)的駐點，且2f(X*)是正定矩陣，則 X* 是 f(X)的嚴格局部極小點。三、全局極小點的判別1.凸規(guī)劃對于優(yōu)化問題：min f(X)s.t. gi(X) 0 i 1,2, ,p若 f(X)、 g i ( X)都是凸函數，則稱該優(yōu)化問題為凸規(guī)劃。2.全局極小點的判別若優(yōu)化問題為凸規(guī)劃，則該優(yōu)化問題的可行集為凸集，其任何局部最優(yōu)解都是全局最優(yōu)解。 (能否證明)第 3 章 無約束優(yōu)化方法 3.1 3.1 下降迭代算法及終止

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

8、的梯度模充分小時，迭代終止。數學表達為：f (X k 1)三、算法的收斂速度對于某一確定的下降算法，其優(yōu)劣如何評價？人們通常采用收斂速度來評價。下面給出度量收斂速度的幾個概念。1 . P階收斂設序列 X k 收斂于解X* ，若存在常數P 0及L 、 k0，使當k k0時下式：Xk1 X* LXk X*p成立，則稱X k 為 P 階收斂。2 .線性收斂設序列 Xk 收斂于解X* ，若存在常數k0、L及 (0,1)，使當 k k0時下式：Xk 1 X* L k成立，則稱X k 為線性收斂。3 .超線性收斂設序列 X k 收斂于解X* ，若任給0都存在k0 0，使當 k k0時下式：Xk 1 X*

9、Xk X*成立，則稱X k 為超線性收斂。 3.2 一維最優(yōu)化方法一、確定初始區(qū)間的進退法任選一個初始點x0 和初始步長h ，由此可確定兩點x1 x0 和 x2x1h ，通過比較這兩點函數值f(x1)、f ( x2)的大小，來決定第三點x3的位置。比較這三點函數值是否呈“高低高”排列特征，若是則找到了單峰區(qū)間，否則向前或后退繼續(xù)尋求下一點。進退法依據的基本公式：x 2 x1 hx3 x2 h具體步驟為：任意選取初始點x0 和恰當的初始步長h ；令x1 x0，取x2x1h ，計算f (x1 ) 、f (x2 ) ；若f(x1)f (x2)，說明極小點在x2右側，應加大步長向前搜索。轉；若f (x

10、1)f (x2) ，說明極小點在x1左側，應以x1點為基準反向小步搜索。轉；大步向前搜索：令h 2h ，取x3x2 h ，計算 f (x3)；若f (x2)f(x3) ，則 f(x1)、f (x2 )、f (x3) 呈“高低高” 排列， 說明x1, x3即為所求的單峰區(qū)間；若f ( x2 ) f ( x3 ) ， 說明極小點在x3 右側，應加大步長向前搜索。此時要注意做變換：舍棄原x1點，以原x2點為新的x1點，原x3點為新的x2點。轉，直至出現“高低高”排列，則單峰區(qū)間可得；反向小步搜索(要注意做變換)：為了保證x3點計算公式的一致性，做變換：將1原 x2點記為新x1點，原x1點記為新x2點

11、，令 h h，取x3x2 h ，轉4例：用進退法確定函數f(x) x2 6x 9的單峰區(qū)間a， b，設初始點x0 0， h 1。解：x0 0 h 1 x1 x00x2x1 h 1 f (x1) 9 f (x2 ) 4 f ( x1 )f (x2 )說明極小點在x2 點右側，應加大步長向前搜索令 h 2h 2 1 2，取x3 x2 h 1 2 3 則 f (x3) 0f (x2 ) f (x3)說明極小點在x3點右側，應加大步長向前搜索舍棄原x10 的點，令x11x23 ，則f( x1 )4f ( x2 )0令 h 2h 2 2 4，取x3x2 h 3 4 7 則 f (x3 ) 16 f (x

12、2 ) 0f(x2)、 f (x3) 呈“高低高”排列x1,x3為單峰區(qū)間，即區(qū)間1 ， 7即為所求二、黃金分割法黃金分割法是基于區(qū)間消去思想的一維搜索方法，其搜索過程必須遵循以下的原則：對稱取點的原則：即所插入的兩點在區(qū)間內位置對稱；插入點繼承的原則：即插入的兩點中有一個是上次縮減區(qū)間時的插入點；等比收縮的原則：即每一次區(qū)間消去后，單峰區(qū)間的收縮率保持不變。設初始區(qū)間為a ， b ，則插入點的計算公式為：x1a 0.382(b a)x2a 0.618(b a)黃金分割法的計算步驟如下：給定初始區(qū)間a， b和收斂精度；給出中間插值點并計算其函數值：x1a 0.382(b a)f (x1)x2a

13、 0.618(b a)f (x2)；比較 f(x1)、f(x2)，確定保留區(qū)間得到新的單峰區(qū)間a， b；收斂性判別：計算區(qū)間a， b長度并與比較，若b a ，輸出x*1 (a b)2否則轉；在保留區(qū)間內繼承一點、插入一點，轉。例：使用黃金分割法求解優(yōu)化問題：min f (x) x2 2x，3 x 50.2。解： x1a0.382(ba)30.382(53)0.056f(x1)0.115 x2a0.618(ba)30.618(53)1.944f(x2)7.667f(x2)f(x1) 舍棄(1.944， 5 ，保留 -3 ， 1.9441.944 ( 3)；繼承原x1點，即x2 0.056 f (

14、x2) 0.115插入x1a 0.382(b a) 3 0.382 (1.944 3)1.111 f (x1)0.987f(x2)f (x1) 舍棄(0.056， 1.944 ，保留 -3 ， 0.0560.056 ( 3)；繼承原x1點，即x21.111 f (x2)0.987插入x1 a 0.382(b a) 3 0.382 (0.056 3)1.832 f (x1)0.306f(x2) f (x1) 保留 -1.832 ， 0.0560.056 ( 1.832)；繼承原x2點，即x11.111f (x1)0.987插入 x21.8320.618(0.056 1.832)0.665f (x

15、2)0.888f(x2) f (x1)保留-1.832 ， -0.665如此迭代，到第8 次，保留區(qū)為-1.111,-0.9400.940 ( 1.111) 0.171 x*1 ( 1.111 0.940)1.0255 f(x*)0.99923.3梯度法一、基本思想對于迭代式Xk 1 Xk kSk， 當取搜索方向Skf(X k)時構成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的梯度法。二、迭代步驟給定出發(fā)點Xk和收斂精度；計算 Xk點的梯度F(X k)，并構造搜索方向SkF(Xk) ；令 Xk 1 X k kSk，通過一維搜索確定步長k，即：min F(XkkSk)求得新點X k 1收斂判斷：若F(X

16、k 1) 成立，輸出X* Xk 1、 F(X*) F(X k 1)，尋優(yōu)結束；否則令k k 1 轉繼續(xù)迭代，直到滿足收斂精度要求。三、梯度法的特點梯度法尋優(yōu)效率受目標函數性態(tài)影響較大。若目標函數等值線為圓，則一輪搜索就可找到極致點；若當目標函數等值線為扁橢圓時，收斂速度則顯著下降。梯度法中相鄰兩輪搜索方向相互垂直。(是否會證明)3.4牛頓法牛頓法分為基本牛頓法和阻尼牛頓法兩種。對于迭代式Xk 1 XkkSk ， 當取 k 1 且搜索方向 Sk 2f (X k) 1 f(Xk)時構成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的基本牛頓法；對于迭代式Xk 1 XkkSk ， 取搜索方向Sk 2 f(Xk)

17、 1 f(X k)， k 為從 Xk出發(fā)、沿牛頓方向做一維搜索獲得的最優(yōu)步長，所構成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的阻尼牛頓法。搜索方向Sk 2f (Xk) 1 f (X k)稱為牛頓方向。這里需要注意的是會求海塞陣的逆矩陣。3.5 變尺度法我們把具有Xk 1 X kkAk f ( X k)迭代模式的尋優(yōu)算法稱為變尺度法。其搜索方向表達式為：SkAk f(X k)，稱為擬牛頓方向，其中Ak稱為變尺度矩陣。在迭代開始的時候，A0 I ；隨著迭代過程的繼續(xù)，Ak 2f(X k) 1 f(Xk)。因此，變尺度法從梯度法出發(fā)，隨著迭代過程的繼續(xù)最終趨向于牛頓法。3.6 共軛梯度法一、共軛方向的概念

18、設 H 為對稱正定矩陣，若有兩個n 維向量S1和 S2， 滿足S1T H S2 0， 則稱向量S1與 S2 關于矩陣H 共軛，共軛向量的方向稱為共軛方向。若有一組非零向量S1， S2，Sn滿足SiT H Sj 0 (i j) ，則稱這組向量關于矩陣 H 共軛。對于 n 元正定二次函數，依次沿著一組共軛方向進行一維搜索，最多n 次即可得到極值點。二、共軛方向的形成1對于函數f(X) f(x1,x2, ,xn) XT HX BTX C沿任意方向S 0在設計空間上任意做兩條平行線，分別與目標函數等值線切于點X1、X2，令 S1 X2 X1，則 S0、 S1關于矩陣H 共軛。 (能否給出證明)三、共軛

19、梯度法對于迭代式Xk 1 XkkSk ，取搜索方向Sk 1 f(X k 1) kSk其中： S0 f(X0)， k f(X )2f(Xk)共軛梯度法相鄰兩輪搜索方向是一對共軛方向。3.7鮑威爾法基本迭代公式仍舊是：X k 1 X k k Sk基本鮑威爾法每輪搜索分為兩步：一環(huán)的搜索+在該環(huán)搜索完畢后生成的新方向上對于基本鮑威爾法，相鄰兩輪搜索生成的搜索方向是共軛的。修正鮑威爾法與基本鮑威爾法類似，所不同的是每環(huán)搜索后生成的新方向要利用鮑威爾條件判別其可用性。注意掌握鮑威爾條件的表達式和應用！每環(huán)搜索方向組的生成：1 第一環(huán)的搜索方向組就是各坐標軸方向2 下一環(huán)的搜索方向組由本環(huán)搜索方向組和本環(huán)

20、生成的新方向共同確定，方法是：若本環(huán)的搜索結果滿足鮑威爾條件，則將本環(huán)搜索方向組中使目標函數下降量最大的方向去掉，并將本環(huán)生成的新方向遞補進去，就形成下一環(huán)的搜索方向組；若本環(huán)的搜索結果不滿足鮑威爾條件，則下一環(huán)的搜索方向組仍舊沿用本環(huán)搜索方向組不變。下一環(huán)搜索起點的確定：下一環(huán)搜索起點由本環(huán)搜索結果確定，方法是： 若本環(huán)的搜索結果滿足鮑威爾條件，則以本環(huán)搜索終點為起點，沿新生成的方向作一維搜索，得到的新點作為本輪的搜索終點，也是下一輪的搜索起點；若本環(huán)的搜索結果不滿足鮑威爾條件，則取本環(huán)搜索終點和反射點中目標函數值小的點作為本輪的搜索終點，也是下一輪的搜索起點。這里需要注意的是反射點的計算：

21、X nk 2 2Xnk X0k式中：Xnk 2是本環(huán)起點X 0k相對于本環(huán)終點X nk沿新生成方向的反射點。例：對于無約束目標函數minf (X ) x12 2x22 4x1 2x1x2 ，利用修正Powell 法從X011 出發(fā)求最優(yōu)解。1解：令X10X 0P0(e1 ,e2 )X11X 10011令 f (X 11 ) 0 得：2則：X 1131X1X103X2X111令 f (X21) 0 得：0.5 則：X2131.5該環(huán)生成的新搜索方向為：S1X21X 01312201.510.5對 S1 進行有效性判別：反射點X 142X21 X01 23154201.512f1f(X01)3f2

22、 f(X21)7.5 f3 f (X41)70.51f (X01)f (X11)3 ( 7)4，2 f (X11) f (X12)7 ( 7.5)故最大下降量m 14212故：f3f1和 ( f12f2f3)(f1f2m)2m(f1f3)2均成立2方向 S1 可用X 12 為起點，沿S 1方向作一維搜索：111X 31X 21S132321.50.51.5 0.5min f(X13) f(X21S1)得 2/5 0.438故，本輪尋優(yōu)的終點為：X 1X313.8做收斂性判別：X 1 X 02.820.72 ，應繼續(xù)搜索38下一輪尋優(yōu)過程的起點為：X 02X313.8031.7下一輪尋優(yōu)過程的搜

23、索方向組為：(e2, S1)繼續(xù)依樣搜索直至滿足收斂精度第 4 章 約束優(yōu)化方法約束優(yōu)化方法要求大家重點掌握懲罰函數法，包括內點法、外點法、混合法。構造懲罰函數：pqmin (X,rk) f(X) rk maxgu(X),0 2 rkhv(X)2u1v1外點法既可以處理不等式約束優(yōu)化問題，又可以處理等式約束優(yōu)化問題。需要注意的是：懲罰因子r k 隨迭代次數的增加是遞增的，當r k 時得到的解就是原問題的最優(yōu)解。例：用外點法求解22min f (X) x1 x2 2x1 1s.t. 3 x2 0解：構造懲罰函數(X , r k ) x12 x22 2x1 1 r k max 3 x2 ,0 22

24、2kx1 x2(X,rk)1222x1 x2k22x1 1 rk (3 x2)22x113 x20 時3 x20時令 2x1 2 0x1k2x2 2rk (x2 3)0x1X 為內點時無約束最優(yōu)解3r k故得：x1 1 x 2 k1r* x11 x2lim x2 3 f (x ) 9構造懲罰函數：p(X,rk) f(X) rku11gu(X)p或： (X,rk) f(X) rk ln gu(X)u1內點法只能處理不等式約束優(yōu)化問題，不能處理等式約束優(yōu)化問題。需要注意的是：懲罰因子r k 隨迭代次數的增加是遞減的，當r k 0 時得到的解就是原問題的最優(yōu)解。例：用內點法求解約束優(yōu)化問題mi nf

25、 (X ) x1 x22s.t.x1x20x10解：構造懲罰函數(X,rk) x1k2kx2 r ln x2x1 r ln x1令x1k 1r2 x1k2rx 2x110 x11 rk1得 x1構造懲罰函數：1 8r k 1( 1 8r k 1) x2160 時，得 x00f ( x* ) 0p1(X,rk) f(X) r1k1 u 1 gu(X)pqr2k hv(X)2 3v1或： (X,rk) f(X) r1kln gu(X) r2khv(X)2u1v1混合法的特點是：對于不等式約束按照內點法構造懲罰項，對于等式約束按照外點法構造懲罰項。混合法既可以處理不等式約束優(yōu)化問題，也可以處理等式約

26、束優(yōu)化問題。例：用混合懲罰函數法求解約束優(yōu)化問題22m i nf (X ) x1 3x2 x2s.t. 1x10x2解：構造懲罰函數(X , rk ) x12 3x2 x22 r k ln1 x1 2 x2令(X,rk)2x1 rk 13 2x21x12 x2 k r得：x12r k 0 時，得 xf(x*) 1第 5 章 遺傳算法本章要求重點掌握遺傳算法的5 個要素、遺傳算法的尋優(yōu)機制。5 個要素1. 編碼將優(yōu)化問題的解編碼，用以模擬生物個體的基因組成；2. 初始種群生成 將優(yōu)化問題多個隨機可行解匯成集合，用以模擬進化的生物種群；3. 個體適應度評估將優(yōu)化問題目標函數加以變換，生成適應度函數來評價種群個體的適應度，用以模擬生物個體對環(huán)境的適應能力；4. 遺傳操作包含選擇、交叉、變異選擇：一種使適應度函數值大的個體有更大的存活機會的