最優(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)化問題的一般形式 2.最優(yōu)化問題的向量表達(dá)式 式中：3.優(yōu)化模型的三要素設(shè)計(jì)變量、約束條件、目標(biāo)函數(shù)稱為優(yōu)化設(shè)計(jì)的三要素！ 設(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)化

2、和非線性優(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ǔ)§2.1 元函數(shù)的可微性與梯度一、可微與梯度的定義1.可微的定義設(shè)是定義在維空間的子集上的元實(shí)值函數(shù)，且。若存在維向量，對(duì)于任意維向量，都有則稱在處可微。2.梯度設(shè)有函數(shù)，在其定義域內(nèi)連續(xù)可導(dǎo)。我們把在定義域內(nèi)某點(diǎn)處的所有一階偏導(dǎo)數(shù)構(gòu)成的列向量，定義為在點(diǎn)處的梯度。記為：梯度有3個(gè)性質(zhì)：函數(shù)在某點(diǎn)的梯度方向?yàn)楹瘮?shù)過該點(diǎn)的等值線的法線方向；函數(shù)值沿梯度方向增加最快，沿負(fù)梯度方向下降最快；梯度描述的只是函數(shù)某點(diǎn)鄰域內(nèi)的局部信息。§

3、2.2極小點(diǎn)及其判別條件一、相關(guān)概念1.極小點(diǎn)與最優(yōu)解設(shè)是定義在維空間的子集上的元實(shí)值函數(shù)，若存在及實(shí)數(shù)，使得都有，則稱為的局部極小點(diǎn)；若，則稱為的嚴(yán)格局部極小點(diǎn)。若，都有，則稱為的全局極小點(diǎn)，若，則稱為的全局嚴(yán)格極小點(diǎn)。對(duì)最優(yōu)化問題而言 滿足所有約束條件的向量稱為上述最優(yōu)化問題的一個(gè)可行解，全體可行解組成的集合稱為可行解集。在可行解集中，滿足： 的解稱為優(yōu)化問題的最優(yōu)解。 2.凸集和凸函數(shù) 凸集：設(shè)，若對(duì)所有的，及，都有，則稱為凸集。 凸函數(shù)：設(shè)，是凸集，如果對(duì)于所有的，及，都有，則稱為上的凸函數(shù)。二、局部極小點(diǎn)的判別條件駐點(diǎn)：設(shè)是定義在維空間的子集上的元實(shí)值函數(shù)，是的內(nèi)點(diǎn)，若，則稱為的駐點(diǎn)

4、。局部極小點(diǎn)的判別：設(shè)是定義在維空間的子集上的元實(shí)值函數(shù)，具有連續(xù)的二階偏導(dǎo)數(shù)。若是的駐點(diǎn)，且是正定矩陣，則是的嚴(yán)格局部極小點(diǎn)。三、全局極小點(diǎn)的判別 1.凸規(guī)劃 對(duì)于優(yōu)化問題：若、都是凸函數(shù)，則稱該優(yōu)化問題為凸規(guī)劃。2.全局極小點(diǎn)的判別若優(yōu)化問題為凸規(guī)劃，則該優(yōu)化問題的可行集為凸集，其任何局部最優(yōu)解都是全局最優(yōu)解。（能否證明）第3章 無約束優(yōu)化方法§3.1下降迭代算法及終止準(zhǔn)則一、數(shù)值優(yōu)化方法的基本思想基本思想就是在設(shè)計(jì)空間內(nèi)選定一個(gè)初始點(diǎn)，從該點(diǎn)出發(fā)，按照某一方向（該方向的確定原則是使函數(shù)值下降）前進(jìn)一定的步長(zhǎng)，得到一個(gè)使目標(biāo)函數(shù)值有所下降的新設(shè)計(jì)點(diǎn)，然后以該點(diǎn)為新的初始點(diǎn)，重復(fù)上

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

6、.超線性收斂設(shè)序列收斂于解，若任給都存在，使當(dāng)時(shí)下式：成立，則稱為超線性收斂。§3.2一維最優(yōu)化方法一、確定初始區(qū)間的進(jìn)退法任選一個(gè)初始點(diǎn)和初始步長(zhǎng)，由此可確定兩點(diǎn)和，通過比較這兩點(diǎn)函數(shù)值、的大小，來決定第三點(diǎn)的位置。比較這三點(diǎn)函數(shù)值是否呈“高低高”排列特征，若是則找到了單峰區(qū)間，否則向前或后退繼續(xù)尋求下一點(diǎn)。進(jìn)退法依據(jù)的基本公式：具體步驟為：任意選取初始點(diǎn)和恰當(dāng)?shù)某跏疾介L(zhǎng)；令，取，計(jì)算、；若，說明極小點(diǎn)在右側(cè)，應(yīng)加大步長(zhǎng)向前搜索。轉(zhuǎn)；若，說明極小點(diǎn)在左側(cè)，應(yīng)以點(diǎn)為基準(zhǔn)反向小步搜索。轉(zhuǎn)；大步向前搜索：令，取，計(jì)算；若，則、呈“高低高”排列，說明即為所求的單峰區(qū)間；若，說明極小點(diǎn)在右側(cè)

7、，應(yīng)加大步長(zhǎng)向前搜索。此時(shí)要注意做變換：舍棄原點(diǎn)，以原點(diǎn)為新的點(diǎn)，原點(diǎn)為新的點(diǎn)。轉(zhuǎn)，直至出現(xiàn)“高低高”排列，則單峰區(qū)間可得；反向小步搜索（要注意做變換）：為了保證點(diǎn)計(jì)算公式的一致性，做變換：將原點(diǎn)記為新點(diǎn)，原點(diǎn)記為新點(diǎn)，令，取，轉(zhuǎn)例：用進(jìn)退法確定函數(shù)的單峰區(qū)間a，b，設(shè)初始點(diǎn)，。解：說明極小點(diǎn)在點(diǎn)右側(cè)，應(yīng)加大步長(zhǎng)向前搜索令，取 則說明極小點(diǎn)在點(diǎn)右側(cè)，應(yīng)加大步長(zhǎng)向前搜索舍棄原的點(diǎn)，令，則令，取 則、呈“高低高”排列為單峰區(qū)間，即區(qū)間1，7即為所求二、黃金分割法 黃金分割法是基于區(qū)間消去思想的一維搜索方法，其搜索過程必須遵循以下的原則：對(duì)稱取點(diǎn)的原則：即所插入的兩點(diǎn)在區(qū)間內(nèi)位置對(duì)稱；插入點(diǎn)繼承的原

8、則：即插入的兩點(diǎn)中有一個(gè)是上次縮減區(qū)間時(shí)的插入點(diǎn)；等比收縮的原則：即每一次區(qū)間消去后，單峰區(qū)間的收縮率保持不變。設(shè)初始區(qū)間為a，b，則插入點(diǎn)的計(jì)算公式為：黃金分割法的計(jì)算步驟如下：給定初始區(qū)間a，b和收斂精度；給出中間插值點(diǎn)并計(jì)算其函數(shù)值： ；比較、，確定保留區(qū)間得到新的單峰區(qū)間a，b；收斂性判別：計(jì)算區(qū)間a，b長(zhǎng)度并與比較，若，輸出否則轉(zhuǎn)；在保留區(qū)間內(nèi)繼承一點(diǎn)、插入一點(diǎn)，轉(zhuǎn)。例：使用黃金分割法求解優(yōu)化問題：。解： 舍棄（1.944，5，保留-3，1.944 ；繼承原點(diǎn)，即插入 舍棄（0.056，1.944，保留-3，0.056 ；繼承原點(diǎn)，即 插入 保留-1.832，0.056 ；繼承原點(diǎn)，

9、即插入 保留-1.832，-0.665如此迭代，到第8次，保留區(qū)為-1.111,-0.940 §3.3梯度法一、基本思想 對(duì)于迭代式，當(dāng)取搜索方向時(shí)構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的梯度法。二、迭代步驟給定出發(fā)點(diǎn)和收斂精度；計(jì)算點(diǎn)的梯度，并構(gòu)造搜索方向；令，通過一維搜索確定步長(zhǎng)，即： 求得新點(diǎn)收斂判斷：若成立，輸出、，尋優(yōu)結(jié)束；否則令轉(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

10、.4牛頓法 牛頓法分為基本牛頓法和阻尼牛頓法兩種。對(duì)于迭代式，當(dāng)取且搜索方向時(shí)構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的基本牛頓法；對(duì)于迭代式，取搜索方向，為從出發(fā)、沿牛頓方向做一維搜索獲得的最優(yōu)步長(zhǎng)，所構(gòu)成的尋優(yōu)算法，稱為求解無約束優(yōu)化問題的阻尼牛頓法。搜索方向稱為牛頓方向。這里需要注意的是會(huì)求海塞陣的逆矩陣。§3.5變尺度法我們把具有迭代模式的尋優(yōu)算法稱為變尺度法。其搜索方向表達(dá)式為：，稱為擬牛頓方向，其中稱為變尺度矩陣。 在迭代開始的時(shí)候，；隨著迭代過程的繼續(xù)，。 因此，變尺度法從梯度法出發(fā)，隨著迭代過程的繼續(xù)最終趨向于牛頓法。§3.6共軛梯度法一、共軛方向的概念 設(shè)為

11、對(duì)稱正定矩陣，若有兩個(gè)維向量和，滿足，則稱向量與關(guān)于矩陣共軛，共軛向量的方向稱為共軛方向。 若有一組非零向量，滿足，則稱這組向量關(guān)于矩陣共軛。 對(duì)于元正定二次函數(shù)，依次沿著一組共軛方向進(jìn)行一維搜索，最多次即可得到極值點(diǎn)。二、共軛方向的形成 對(duì)于函數(shù)沿任意方向在設(shè)計(jì)空間上任意做兩條平行線，分別與目標(biāo)函數(shù)等值線切于點(diǎn)、，令，則、關(guān)于矩陣共軛。（能否給出證明）三、共軛梯度法 對(duì)于迭代式，取搜索方向 其中：， 共軛梯度法相鄰兩輪搜索方向是一對(duì)共軛方向。§3.7鮑威爾法 基本迭代公式仍舊是： 基本鮑威爾法每輪搜索分為兩步：一環(huán)的搜索+在該環(huán)搜索完畢后生成的新方向上的一維搜索。 對(duì)于基本鮑威爾法

12、，相鄰兩輪搜索生成的搜索方向是共軛的。 修正鮑威爾法與基本鮑威爾法類似，所不同的是每環(huán)搜索后生成的新方向要利用鮑威爾條件判別其可用性。 注意掌握鮑威爾條件的表達(dá)式和應(yīng)用！ 每環(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é)果確定，方法是：若本

13、環(huán)的搜索結(jié)果滿足鮑威爾條件，則以本環(huán)搜索終點(diǎn)為起點(diǎn)，沿新生成的方向作一維搜索，得到的新點(diǎn)作為本輪的搜索終點(diǎn)，也是下一輪的搜索起點(diǎn)；若本環(huán)的搜索結(jié)果不滿足鮑威爾條件，則取本環(huán)搜索終點(diǎn)和反射點(diǎn)中目標(biāo)函數(shù)值小的點(diǎn)作為本輪的搜索終點(diǎn)，也是下一輪的搜索起點(diǎn)。 這里需要注意的是反射點(diǎn)的計(jì)算： 式中：是本環(huán)起點(diǎn)相對(duì)于本環(huán)終點(diǎn)沿新生成方向的反射點(diǎn)。例：對(duì)于無約束目標(biāo)函數(shù)，利用修正Powell法從出發(fā)求最優(yōu)解。解：令 令 得： 則： 令 得： 則：該環(huán)生成的新搜索方向?yàn)椋?對(duì)進(jìn)行有效性判別： 反射點(diǎn) ， 故最大下降量故：和均成立方向可用以為起點(diǎn)，沿方向作一維搜索：由得故，本輪尋優(yōu)的終點(diǎn)為：做收斂性判別：，應(yīng)繼續(xù)

14、搜索下一輪尋優(yōu)過程的起點(diǎn)為：下一輪尋優(yōu)過程的搜索方向組為：繼續(xù)依樣搜索直至滿足收斂精度第4章 約束優(yōu)化方法 約束優(yōu)化方法要求大家重點(diǎn)掌握懲罰函數(shù)法，包括內(nèi)點(diǎn)法、外點(diǎn)法、混合法。一、外點(diǎn)法 構(gòu)造懲罰函數(shù)：外點(diǎn)法既可以處理不等式約束優(yōu)化問題，又可以處理等式約束優(yōu)化問題。需要注意的是：懲罰因子隨迭代次數(shù)的增加是遞增的，當(dāng)時(shí)得到的解就是原問題的最優(yōu)解。例：用外點(diǎn)法求解解：構(gòu)造懲罰函數(shù)令 為內(nèi)點(diǎn)時(shí)無約束最優(yōu)解故得： 二、內(nèi)點(diǎn)法 構(gòu)造懲罰函數(shù)： 或：內(nèi)點(diǎn)法只能處理不等式約束優(yōu)化問題，不能處理等式約束優(yōu)化問題。需要注意的是：懲罰因子隨迭代次數(shù)的增加是遞減的，當(dāng)時(shí)得到的解就是原問題的最優(yōu)解。例：用內(nèi)點(diǎn)法求解約

15、束優(yōu)化問題 解：構(gòu)造懲罰函數(shù)令 得， 當(dāng)時(shí)，得 三、混合法構(gòu)造懲罰函數(shù)：或：混合法的特點(diǎn)是：對(duì)于不等式約束按照內(nèi)點(diǎn)法構(gòu)造懲罰項(xiàng)，對(duì)于等式約束按照外點(diǎn)法構(gòu)造懲罰項(xiàng)。混合法既可以處理不等式約束優(yōu)化問題，也可以處理等式約束優(yōu)化問題。例：用混合懲罰函數(shù)法求解約束優(yōu)化問題 解：構(gòu)造懲罰函數(shù) 令 得：， 當(dāng)時(shí)，得 第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è)體有更大的存活機(jī)會(huì)的機(jī)制，用以模擬環(huán)境對(duì)生物個(gè)體的自然選擇；遺傳操作否是編 碼初始群體的生成群體中個(gè)體適應(yīng)度函數(shù)的評(píng)估選 擇交 叉變 異收斂？結(jié) 束基本遺傳算法流程圖交叉：不同個(gè)體間相互交換信息，用以模擬高級(jí)生物有性繁殖過程中的基因重組過程；變異：模擬生物在遺傳過程中基因復(fù)制差錯(cuò)而產(chǎn)生新個(gè)體的現(xiàn)象。 5.控制參數(shù)的設(shè)定 種群規(guī)模：； 交叉概率：變異概率： 最大進(jìn)化代數(shù)：二、