最優(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,Xnminf(x,X2,Xn)s.t.gu(X1,X2,Xn)0u1,2,phv(X1,X2,Xn)0v1,2,q2 .最優(yōu)化問題的向量表達(dá)式findXminf(X)s.t.G(X)0H(X)0式中：XX1,X2,XnTG(X)gKX),g2(X),gp(X)TH(X)%(X),h2(X),hp(X)T3 .優(yōu)化模型的三要素設(shè)計(jì)變量、約束條件、目標(biāo)函數(shù)稱為優(yōu)化設(shè)計(jì)的三要素！

2、設(shè)計(jì)空間：由設(shè)計(jì)變量所確定的空間。設(shè)計(jì)空間中的每一個(gè)點(diǎn)都代表一個(gè)設(shè)計(jì)方案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ù)個(gè)數(shù)分為單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化問題4按照設(shè)計(jì)變量的性質(zhì)不同分為連續(xù)變量?jī)?yōu)化和離散變量?jī)?yōu)化問題第2章最優(yōu)化問題的數(shù)學(xué)基礎(chǔ)21n元函數(shù)的可微性與梯度、可微與梯度的定義1 .可微的定義設(shè)f(X)是定義在n維空間Rn的子集D上的n元實(shí)值函數(shù)，且X0D。若存在n維向量L,對(duì)于任意n維向量P,都有.f(X0P)f(X0)ltp.

3、lim0llP0p|則稱f(X)在X0處可微。2 .梯度設(shè)有函數(shù)F(X),XXi,X2,XnT,在其定義域連續(xù)可導(dǎo)。我們把F(X)在定義域某點(diǎn)X處的所有一階偏導(dǎo)數(shù)構(gòu)成的列向量，定義為F(X)在點(diǎn)X處的梯度。記為:X1X2TFXn梯度有3個(gè)性質(zhì)：函數(shù)在某點(diǎn)的梯度方向?yàn)楹瘮?shù)過該點(diǎn)的等值線的法線方向;函數(shù)值沿梯度方向增加最快，沿負(fù)梯度方向下降最快；梯度描述的只是函數(shù)某點(diǎn)鄰域的局部信息。22極小點(diǎn)及其判別條件一、相關(guān)概念1.極小點(diǎn)與最優(yōu)解設(shè)f(X)是定義在n維空間Rn的子集D上的n元實(shí)值函數(shù)，若存在X*D及實(shí)數(shù)0,使得XN(X,)D(XXWRtf(X)f(X),則稱X為f(X)的局部極小點(diǎn)；若則稱X若

4、f(X)f(X),則稱X為f(X)的嚴(yán)格局部極小點(diǎn)。XD,都有f(X)f(X),則稱X為f(X)的全局極小點(diǎn)，若f(X)f(X),為f(X)的全局嚴(yán)格極小點(diǎn)。findX對(duì)最優(yōu)化問題(X)st.G(X)H(X)而百00滿足所有約束條件的向量XXi，X2，,XnT稱為上述最優(yōu)化問題的一個(gè)可行解，全體可行解組成的集合稱為可行解集。在可行解集中，滿足:f(X)minf(X)的解稱為優(yōu)化問題的取優(yōu)解。2.凸集和凸函數(shù)凸集：設(shè)DRn,若對(duì)所有的X1、X2D,及0,1,都有X1(1)X2D,則稱D為凸集。凸函數(shù)：設(shè)f:DRnR1,D是凸集，如果對(duì)于所有的X1、X2D,及0,1,都有fX1(1)X2f(X1)

5、(1)f(X2),則稱f(X)為D上的凸函數(shù)。二、局部極小點(diǎn)的判別條件駐點(diǎn)：設(shè)f(X)是定義在n維空間Rn的子集D上的n元實(shí)值函數(shù)，X*是D的點(diǎn)，若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)，且2f(X*)是正定矩陣，則X*是f(X)的嚴(yán)格局部極小點(diǎn)。第3章無約束優(yōu)化方法3.1 下降迭代算法及終止準(zhǔn)則一、數(shù)值優(yōu)化方法的基本思想基本思想就是在設(shè)計(jì)空間選定一個(gè)初始點(diǎn)Xk,從該點(diǎn)出發(fā)，按照某一方向Sk(該方向的確定原則是使函數(shù)值下降)前進(jìn)一定的步長(zhǎng);得到一個(gè)使目標(biāo)函數(shù)值有所下降的新設(shè)計(jì)點(diǎn)X

6、k1,然后以該點(diǎn)為新的初始點(diǎn)，重復(fù)上面過程，直至得到滿足精度要求的最優(yōu)點(diǎn)X。該思想可用下式表示：Xk1XkkSk二、迭代計(jì)算的終止準(zhǔn)則工程中常用的迭代終止準(zhǔn)則有3種：點(diǎn)距準(zhǔn)則相鄰兩次迭代點(diǎn)之間的距離充分小時(shí)，迭代終止。數(shù)學(xué)表達(dá)為：Xk1Xk函數(shù)下降量準(zhǔn)則(值差準(zhǔn)則)相鄰兩次迭代點(diǎn)的函數(shù)值之差充分小，迭代終止。數(shù)學(xué)表達(dá)為：|f(Xk1)f(Xk)|梯度準(zhǔn)則目標(biāo)函數(shù)在迭代點(diǎn)處的梯度模充分小時(shí)，迭代終止數(shù)學(xué)表達(dá)為：|f（Xk1）|、算法的收斂速度對(duì)于某一確定的下降算法，其優(yōu)劣如何評(píng)價(jià)？人們通常采用收斂速度來評(píng)價(jià)。下面給出度量收斂速度的幾個(gè)概念。1 .P階收斂設(shè)序列Xk收斂于解X*,若存在常數(shù)P0及L

7、、ko,使當(dāng)kko時(shí)下式:成立，則稱Xk為P階收斂。2 .線性收斂設(shè)序列Xk收斂于解X*,若存在常數(shù)ko、L及（0,1）,使當(dāng)kko時(shí)下式：Xk1X*Lk成立，則稱Xk為線性收斂。3 .超線性收斂設(shè)序列Xk收斂于解X*,若任給0都存在ko0,使當(dāng)kko時(shí)下式：Xk1X*XkX*成立，則稱Xk為超線性收斂。3.2 一維最優(yōu)化方法一、確定初始區(qū)間的進(jìn)退法任選一個(gè)初始點(diǎn)Xo和初始步長(zhǎng)h,由此可確定兩點(diǎn)X1Xo和X2X1h,通過比較這兩點(diǎn)函數(shù)值f（X1）、f（X2）的大小，來決定第三點(diǎn)X3的位置。比較這三點(diǎn)函數(shù)值是否呈“高一一低一一高”排列特征，若是則找到了單峰區(qū)問，否則向前或后退繼續(xù)尋求下進(jìn)退法依據(jù)

8、的基本公式:X2X3具體步驟為：任意選取初始點(diǎn)Xo和恰當(dāng)?shù)某跏疾介L(zhǎng)h；令X1Xo,取x2X1h,計(jì)算f（X1）、f（X2）;若f（X1）f（X2）,說明極小點(diǎn)在X2右側(cè)，應(yīng)加大步長(zhǎng)向前搜索。轉(zhuǎn)；若f（X1）f（X2）,說明極小點(diǎn)在X1左側(cè)，應(yīng)以X1點(diǎn)為基準(zhǔn)反向小步搜索。轉(zhuǎn);大步向前搜索：令h2h,取X3x2h,計(jì)算fd);若f(X2)f(X3)，則f(X1)、f(X2)、f(X3)呈“高低高”排列，說明X1,X3即為所求的單峰區(qū)間；若f(X2)f(X3),說明極小點(diǎn)在X3右側(cè)，應(yīng)加大步長(zhǎng)向前搜索。此時(shí)要注意做變換：舍棄原X1點(diǎn)，以原X2點(diǎn)為新的X1點(diǎn)，原X3點(diǎn)為新的X2點(diǎn)。轉(zhuǎn)，直至出現(xiàn)“高一一

9、低一一高”排列，則單峰區(qū)間可得；反向小步搜索(要注意做變換)：為了保證X3點(diǎn)計(jì)算公式的一致性，做變換：將1原X2點(diǎn)記為新X1點(diǎn)，原Xi點(diǎn)記為新X2點(diǎn)，令hh,取X3X2h,轉(zhuǎn)4例：用進(jìn)退法確定函數(shù)f(x)X26x9的單峰區(qū)間a,b,設(shè)初始點(diǎn)x00,h1。解：Xo0h1x1xo0x2x1h1f(x1)9f(x2)4“xjf(X2)說明極小點(diǎn)在X2點(diǎn)右側(cè)，應(yīng)加大步長(zhǎng)向前搜索令h2h212,取x3x2h123則f(x3)0f(X2)f(X3)說明極小點(diǎn)在X3點(diǎn)右側(cè)，應(yīng)加大步長(zhǎng)向前搜索舍棄原X1o的點(diǎn)，令X11X23,則f(X1)4f(X2)o令h2h224,取X3X2h347則f(x3)16f(X2

10、)0f(x1)、f(X2)f%)呈“高低高”排列X1,X3為單峰區(qū)間,即區(qū)間1,7即為所求二、黃金分割法黃金分割法是基于區(qū)間消去思想的一維搜索方法，其搜索過程必須遵循以下的原則：對(duì)稱取點(diǎn)的原則：即所插入的兩點(diǎn)在區(qū)間位置對(duì)稱；插入點(diǎn)繼承的原則：即插入的兩點(diǎn)中有一個(gè)是上次縮減區(qū)間時(shí)的插入點(diǎn)；等比收縮的原則：即每一次區(qū)間消去后，單峰區(qū)間的收縮率保持不變。設(shè)初始區(qū)間為a,b,則插入點(diǎn)的計(jì)算公式為:xia0.382(ba)x2a0.618(ba)黃金分割法的計(jì)算步驟如下：給定初始區(qū)間a,b和收斂精度；給出中間插值點(diǎn)并計(jì)算其函數(shù)值：x1a0.382(ba)f(x1)x2a0.618(ba)f(x2).比較

11、f(xj、f(xz),確定保留區(qū)間得到新的單峰區(qū)間a,b;收斂性判別：計(jì)算區(qū)間a,b長(zhǎng)度并與比較，若*1，、x(ab)2否則轉(zhuǎn);在保留區(qū)間繼承一點(diǎn)、插入一點(diǎn)，轉(zhuǎn)例：使用黃金分割法求解優(yōu)化問題：minf(x)2x2x,0.2。解：x1a0.382(ba)30.382(53)0.056f(xi)0.1152)x2a0.618(ba)30.618(53)1.944f(x2)7.667f(x2)f(x1)舍棄(1.944,5,保留-31.9441.944繼承原木點(diǎn)，即x20.056f(x2)0.115插入xa0.382(ba)30.382(1.9443)1.111f(x1)0.987vf(x2)f(x

12、1).舍棄(0.056,1.944,保留-3,0.0560.056(3)繼承原木點(diǎn)，即x21.111f(x2)0.987插入x1a0.382(ba)30.382(0.0563)1.832f(x1)0.306:f(x2)f(x1).保留-1.832,0.0560.056(1.832);繼承原x2點(diǎn)，即x11.111f(x1)0.987f(x2)0.888插入x21.8320.618(0.0561.832)0.665f(X2)f(Xi).保留-1.832,-0.665如此迭代，到第8次,保留區(qū)為-1.111,-0.9400.940(1.111)0.171d.x1(1.1110.940)1.0255

13、f(x)0.99923.3 梯度法一、基本思想對(duì)于迭代式Xk1xkkSk,當(dāng)取搜索方向Skf(Xk)時(shí)構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的梯度法。二、迭代步驟給定出發(fā)點(diǎn)xk和收斂精度；計(jì)算xk點(diǎn)的梯度F(Xk),并構(gòu)造搜索方向SkF(Xk);令Xk1Xkksk,通過一維搜索確定步長(zhǎng)k，即：minF(XkkSk)求得新點(diǎn)Xk1收斂判斷：若JF(Xk1)|成立，輸出X*Xk1、F(X*)F(Xk1),尋優(yōu)結(jié)束；否則令kk1轉(zhuǎn)繼續(xù)迭代，直到滿足收斂精度要求。三、梯度法的特點(diǎn)梯度法尋優(yōu)效率受目標(biāo)函數(shù)性態(tài)影響較大。若目標(biāo)函數(shù)等值線為圓，則一輪搜索就可找到極致點(diǎn)；若當(dāng)目標(biāo)函數(shù)等值線為扁橢圓時(shí)，收斂速度

14、則顯著下降。梯度法中相鄰兩輪搜索方向相互垂直。3.4 牛頓法牛頓法分為基本牛頓法和阻尼牛頓法兩種。對(duì)于迭代式Xk1XkkSk，當(dāng)取k1且搜索方向Sk2f(Xk)1f(Xk)時(shí)構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的基本牛頓法；對(duì)于迭代式Xk1XkkSk，取搜索方向Sk2f(Xk)1f(Xk),k為從Xk出發(fā)、沿牛頓方向做一維搜索獲得的最優(yōu)步長(zhǎng)，所構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的阻尼牛頓法。搜索方向Sk2f(Xk)1f(Xk)稱為牛頓方向。這里需要注意的是會(huì)求海塞陣的逆矩陣3.5 變尺度法我們把具有Xk1XkkAkf(Xk)迭代模式的尋優(yōu)算法稱為變尺度法。其搜索方向表達(dá)式為：SkAkf(

15、Xk),稱為擬牛頓方向，其中Ak稱為變尺度矩庫(kù)。在迭代開始的時(shí)候，A0I；隨著迭代過程的繼續(xù)，Ak2f(Xk)1f(Xk),因此，變尺度法從梯度法出發(fā)，隨著迭代過程的繼續(xù)最終趨向于牛頓法。3.6 共腕梯度法一、共腕方向的概念設(shè)H為對(duì)稱正定矩陣，若有兩個(gè)n維向量Si和S2,滿足S1THS20,則稱向量Si與&關(guān)于矩陣H共腕，共腕向量的方向稱為共腕方向。若有一組非零向量S,S2,Sn滿足STHSj0(ij),則稱這組向量關(guān)于矩陣H共腕。對(duì)于n元正定二次函數(shù)，依次沿著一組共腕方向進(jìn)行一維搜索，最多n次即可得到極值點(diǎn)。二、共腕方向的形成1對(duì)于函數(shù)f(X)f(X1,X2,Xn)-XtHXBtXC2沿任意

16、方向S0在設(shè)計(jì)空間上任意做兩條平行線，分別與目標(biāo)函數(shù)等值線切于點(diǎn)X1、X2,令S1X2X1,則S0、S1關(guān)于矩陣H共腕。三、共腕梯度法對(duì)于迭代式Xk1XkkSk，取搜索方向Sk1f(Xk1)kSk其中：S0f(X),kf(Xk1)f(Xk)|2共腕梯度法相鄰兩輪搜索方向是一對(duì)共腕方向。3.7鮑威爾法基本迭代公式仍舊是：Xk1XkkSk基本鮑威爾法每輪搜索分為兩步：一環(huán)的搜索+在該環(huán)搜索完畢后生成的新方向上的一維搜索。對(duì)于基本鮑威爾法，相鄰兩輪搜索生成的搜索方向是共腕的。修正鮑威爾法與基本鮑威爾法類似，所不同的是每環(huán)搜索后生成的新方向要利用鮑威爾條件判別其可用性。注意掌握鮑威爾條件的表達(dá)式和應(yīng)用

17、!每環(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é)果不滿足鮑威爾條件，則取本

18、環(huán)搜索終點(diǎn)和反射點(diǎn)中目標(biāo)函數(shù)值小的點(diǎn)作為本輪的搜索終點(diǎn)，也是下一輪的搜索起點(diǎn)。這里需要注意的是反射點(diǎn)的計(jì)算：x，2x；x0k式中：xk2是本環(huán)起點(diǎn)x0k相對(duì)于本環(huán)終點(diǎn)xk沿新生成方向的反射點(diǎn)。例:對(duì)于無約束目標(biāo)函數(shù)minf(X)X122x24x12x1x2,利用修正Powell法從x01 ，出發(fā)求最優(yōu)解解:令x0x0P1P0(72)x；x0(x；)自：則：x1x2X11令f（x2）行：0.5則：x231.5該環(huán)生成的新搜索方向?yàn)椋簊1x2x01.50.51對(duì)S1進(jìn)行有效性判別:反射點(diǎn)x42X2X0321.5f1f(X0)f2_1f(X2)7.5f3f(X4)71f(X0)f(X；)3(7)4,

19、2f(X11)f(X2)7(7.5)0.5故最大下降量m故：f3%和(f12f2f3)(f1f2m(f1f3)2均成立方向S1可用以x2為起點(diǎn)，沿s1方向作一維搜索:x3x2s131.520.531.520.5由minf(X3)f(x2S1)得2/50.4故，本輪尋優(yōu)的終點(diǎn)為:X113.8x31.7做收斂性判別:IV2.820.72,應(yīng)繼續(xù)搜索下一輪尋優(yōu)過程的起點(diǎn)為：x213.8x31.7下一輪尋優(yōu)過程的搜索方向組為:(e2，S1)約束優(yōu)化方法約束優(yōu)化方法要求大家重點(diǎn)掌握懲罰函數(shù)法，包括點(diǎn)法、外點(diǎn)法、混合法。、外點(diǎn)法構(gòu)造懲罰函數(shù)：pqk_k2k2min(X,r)f(X)rma)(gu(X),0

20、rhv(X)u1v1外點(diǎn)法既可以處理不等式約束優(yōu)化問題，又可以處理等式約束優(yōu)化問題。需要注意的是:懲罰因子隨迭代次數(shù)的增加是遞增的，當(dāng)時(shí)得到的解就是原問題的最優(yōu)解。例:用外點(diǎn)法求解minf(X)x；s.t.3x20x22xi解:構(gòu)造懲罰函數(shù)(X,rk)2x12x2行：(X,rk)2x1x1x1x11、點(diǎn)法2x2x2一12x12x122222x12x12rk(x23)03rkkr*x1構(gòu)造懲罰函數(shù):(X,rk)f(X)11gu(X)2x1rk(3x2)22max3x2,0X2又2*乂2limx2k或：（X點(diǎn)法只能處理不等式約束優(yōu)化問題,需要注意的是：懲罰因子是原問題的最優(yōu)解。例：用點(diǎn)法求解約束優(yōu)

21、化問題minf(X)x1X2_*3f(x)prk)f(X)rklnu1不能處理等式約束優(yōu)化問題。隨迭代次數(shù)的增加是遞減的，當(dāng)rkgu(X)0時(shí)得到的解就2s.t.x1x2x10解：構(gòu)造懲罰函數(shù)(X,rk)x1x2k._2_k.rlnx2x1rlnx1一1x12x12x2x1一1x212x2x14日彳可x1,18rk14X2(18rk1)2rk16當(dāng)rk0時(shí)，得_*f(x)0三、混合法構(gòu)造懲罰函數(shù):(X,rk)f(X)krik或：(X,r)f(X)1gu(X)pk._rlnu1q2hv(X)21qk2gu(X)r2hv(X)v1混合法的特點(diǎn)是：對(duì)于不等式約束按照點(diǎn)法構(gòu)造懲罰項(xiàng)，對(duì)于等式約束按照外

22、點(diǎn)法構(gòu)造懲罰項(xiàng)?；旌戏瓤梢蕴幚聿坏仁郊s束優(yōu)化問題，也可以處理等式約束優(yōu)化問題。例：用混合懲罰函數(shù)法求解約束優(yōu)化問題-2minf(X)x123x2x2s.t.1x10x20解：構(gòu)造懲罰函數(shù)(X,rk)x123x22X2k12rln1xjx2r2x1令(X,rk)2x2X2x2r得：x1k2rX2312(1)r_*f(x)10時(shí)，得x第5章遺傳算法本章要求重點(diǎn)掌握遺傳算法的5個(gè)要素、遺傳算法的尋優(yōu)機(jī)制、遺傳算法的5個(gè)要素1.編碼將優(yōu)化問題的解編碼，用以模擬生物個(gè)體的基因組成；2 .初始種群生成將優(yōu)化問題多個(gè)隨機(jī)可行解匯成集合，用以模擬進(jìn)化的生物種群；3 .個(gè)體適應(yīng)度評(píng)估將優(yōu)化問題目標(biāo)函數(shù)加以變換，生成適應(yīng)度函數(shù)來評(píng)價(jià)種群個(gè)體的適應(yīng)度，用以模擬生物個(gè)體對(duì)環(huán)境的適應(yīng)能力；4 .遺傳操作包含選擇、交叉、變異選擇：一種使適應(yīng)度函數(shù)值大的個(gè)體有更大的存活