直接-間接法-罰函數(shù)法

約束優(yōu)化方法第二節(jié)復(fù)合型法2第三節(jié)懲罰函數(shù)法3約束優(yōu)化方法第一節(jié)概述2第一節(jié)概述概述1、數(shù)學(xué)模型求解上式的方法稱為約束優(yōu)化方法2、求解方法（1）直接解法：將迭代點(diǎn)限制在可行域內(nèi)（可行性），步步降低目標(biāo)函數(shù)值（下降性），直至到達(dá)最優(yōu)點(diǎn)。如隨機(jī)方向法、復(fù)合形法、可行方向法、廣義簡(jiǎn)約梯度法。

根據(jù)求解方式不同，約束優(yōu)化設(shè)計(jì)問題可分為直接解法和間接解法。（2）間接解法：通過變換，將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題求解。如懲罰函數(shù)法、增廣乘子法等。（1）直接解法適用于僅含不等式約束的問題，基本思路是：

在不等式確定的可行域內(nèi)選擇一個(gè)初始點(diǎn)，然后決定可行搜索方向，且以適當(dāng)?shù)牟介L進(jìn)行搜索，得到一個(gè)使目標(biāo)函數(shù)值下降的可行的新點(diǎn)，即完成一次迭代。再以新點(diǎn)為起點(diǎn)，重復(fù)上述搜索過程，滿足收斂條件后，迭代終止。----步長----可行搜索方向可行搜索方向：當(dāng)設(shè)計(jì)點(diǎn)沿該方向作微量移動(dòng)時(shí)，目標(biāo)函數(shù)值將下降，且不會(huì)越出可行域。直接解法的搜索路線①迭代計(jì)算無論何時(shí)終止，都可獲得一個(gè)比初始點(diǎn)好的設(shè)計(jì)點(diǎn)；②若目標(biāo)函數(shù)是凸函數(shù)，可行域是凸集，則可保證獲得全域最優(yōu)解。否則，將由于所選擇的初始點(diǎn)的不同，而探測(cè)到不同的局部最優(yōu)解上，在這種情況下，探索結(jié)果經(jīng)常與初始點(diǎn)的選擇有關(guān)系，為了能得到全局最優(yōu)解，在探索過程中最好能改變初始點(diǎn)，或選擇幾個(gè)差別較大的初始點(diǎn)分別計(jì)算，以便從多個(gè)局部最優(yōu)解中選擇更好的最優(yōu)解；③要求可行域?yàn)橛薪绲姆强占丛谟薪缈尚杏騼?nèi)存在滿足全部約束條件的點(diǎn)，且目標(biāo)函數(shù)有定義。2）直接解法的特點(diǎn)a)可行域是凸集；b)可行域是非凸集（2）間接解法1)基本思路將約束優(yōu)化問題中的約束函數(shù)進(jìn)行特殊的加權(quán)處理后，和目標(biāo)函數(shù)結(jié)合起來，構(gòu)成新的目標(biāo)函數(shù)，即將原約束優(yōu)化問題轉(zhuǎn)化成一個(gè)或一系列的無約束優(yōu)化問題。再對(duì)新的目標(biāo)函數(shù)進(jìn)行無約束優(yōu)化計(jì)算，從而間接地搜索到原約束問題的最優(yōu)解。新目標(biāo)函數(shù)加權(quán)因子2)間接解法的特點(diǎn)①計(jì)算效率和數(shù)值計(jì)算的穩(wěn)定性有較大提高；②可以有效地處理具有約束等式約束的約束優(yōu)化問題；③選擇加權(quán)因子困難，如果選擇不當(dāng)，不但影響收斂速度和計(jì)算精度，甚至?xí)?dǎo)致計(jì)算失敗。

由于間接解法可以選用已研究比較成熟的無約束優(yōu)化方法，并且容易處理同時(shí)具有不等式約束和等式約束的問題。因而在機(jī)械優(yōu)化設(shè)計(jì)得到廣泛的應(yīng)用。本節(jié)結(jié)束第三節(jié)懲罰函數(shù)法1、基本思想

通過構(gòu)造懲罰函數(shù)把約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題，進(jìn)而用無約束最優(yōu)化方法求解。

將約束優(yōu)化問題

中的不等式和等式約束函數(shù)經(jīng)過加權(quán)轉(zhuǎn)化后，和原目標(biāo)函數(shù)結(jié)合形成新的目標(biāo)函數(shù)——懲罰函數(shù)——加權(quán)轉(zhuǎn)化項(xiàng)——障礙項(xiàng)——懲罰項(xiàng)

——障礙項(xiàng)的作用是當(dāng)?shù)c(diǎn)在可行域內(nèi)時(shí)，在迭代過程中將阻止迭代點(diǎn)越出可行域；——懲罰項(xiàng)的作用是當(dāng)?shù)c(diǎn)在非可行域或不滿足等式約束條件時(shí)，在迭代過程將迫使迭代點(diǎn)逼近約束邊界或等式約束曲面。①懲罰項(xiàng)和障礙項(xiàng)用約束條件構(gòu)造;②到達(dá)最優(yōu)點(diǎn)時(shí),懲罰項(xiàng)和障礙項(xiàng)的值為0;③當(dāng)約束不滿足或未到達(dá)最優(yōu)點(diǎn)時(shí),懲罰項(xiàng)和障礙項(xiàng)的值大于0.構(gòu)造懲罰函數(shù)的基本要求:

求解該新目標(biāo)函數(shù)的無約束極小值，以期得到原問題的約束最優(yōu)解。為此，按一定的法則改變加權(quán)因子的值，構(gòu)成一系列無約束優(yōu)化問題,求得一系列無約束最優(yōu)解，并不斷的逼近原約束優(yōu)化問題的最優(yōu)解。因此懲罰函數(shù)法又稱為序列無約束極小化方法，常稱SUMT法，即(SequentialUnconstrainedMinimizationTechnique)。障礙項(xiàng)和懲罰項(xiàng)必須具有以下極限性質(zhì)：從而有2．懲罰函數(shù)方法

內(nèi)點(diǎn)懲罰函數(shù)法外點(diǎn)懲罰函數(shù)法混合懲罰函數(shù)法

根據(jù)約束形式以及懲罰因子的遞推方法的不同，懲罰函數(shù)方法可分為：（1）內(nèi)點(diǎn)懲罰函數(shù)法（內(nèi)點(diǎn)法）基本思想：內(nèi)點(diǎn)法將新目標(biāo)函數(shù)定義于可行域內(nèi)，這樣它的初始點(diǎn)及后面的迭代點(diǎn)序列必定在可行域內(nèi)，并逐步逼近最優(yōu)點(diǎn)。

采用內(nèi)點(diǎn)法只能求解具有不等式約束的優(yōu)化問題。轉(zhuǎn)化后的懲罰函數(shù)形式為或或——障礙項(xiàng)。對(duì)于只具有不等式約束的優(yōu)化問題是懲罰因子，它是由大到小，且趨近于0的數(shù)列，即

由于內(nèi)點(diǎn)法的迭代過程在可行域內(nèi)進(jìn)行，障礙項(xiàng)的作用是阻止迭代點(diǎn)越出可行域。由障礙項(xiàng)的函數(shù)形式可知，當(dāng)?shù)c(diǎn)靠近某一約束邊界時(shí)，其值趨近0，而障礙項(xiàng)的值陡然增加，并趨近于無窮大，好像在可行域的邊界上筑起了一道“高墻”，使迭代點(diǎn)始終不能越出可行域，顯然，只有當(dāng)懲罰因子趨于0時(shí)，才能求得在約束邊界上的最優(yōu)解。懲罰因子的作用：由于內(nèi)點(diǎn)法只能在可行域內(nèi)迭代，而最優(yōu)解很可能在可行域內(nèi)靠邊界處或就在邊界上，此時(shí)盡管泛函的值很大，但由于懲罰因子是不斷遞減的正值，經(jīng)過多次迭代，接近最優(yōu)解時(shí)，懲罰項(xiàng)已是很小的正值。例2-1

試用內(nèi)點(diǎn)罰函數(shù)法求解如下優(yōu)化問題：解：此題的標(biāo)準(zhǔn)解為：。根據(jù)內(nèi)點(diǎn)法的基本思想，首先構(gòu)造罰函數(shù)，按式（2-71）可寫出：可以看出由兩部分組成，即，其中：內(nèi)點(diǎn)法例題即：是原目標(biāo)函數(shù)，為一直線；

是一族倒數(shù)曲線，當(dāng)。對(duì)求導(dǎo)并令其一階導(dǎo)數(shù)為零，即可求得其無約束極值點(diǎn)：：懲罰函數(shù)值為：當(dāng)選用不同的懲罰因子時(shí)，可得到不同的極值點(diǎn)及Φ曲線。取遞減數(shù)列，由上式可得序列如下：

上圖表示出取值不同時(shí)所得到的約束最優(yōu)點(diǎn)逐步逼近原問題最優(yōu)點(diǎn)的情形。例:用內(nèi)點(diǎn)法求問題約束最優(yōu)解。解:用內(nèi)點(diǎn)法求該問題，首先構(gòu)造內(nèi)點(diǎn)懲罰函數(shù)：用解析法求函數(shù)的極小值，運(yùn)用極值條件：聯(lián)立求得：當(dāng)

時(shí)不滿足約束條件，應(yīng)舍去則無約束極值點(diǎn)為初始點(diǎn)的選取

應(yīng)選擇一個(gè)離約束邊界較遠(yuǎn)的可行點(diǎn)。如太靠近某一約束邊界，構(gòu)造的懲罰函數(shù)可能由于障礙項(xiàng)的值很大而變得畸形，使求解無約束優(yōu)化問題發(fā)生困難。計(jì)算機(jī)自動(dòng)生成可行初始點(diǎn)的常用方法是利用隨機(jī)數(shù)生成設(shè)計(jì)點(diǎn)。懲罰因子初值的選取

懲罰因子的初值應(yīng)適當(dāng)，否則會(huì)影響迭代計(jì)算的正常進(jìn)行。一般而言，太大，將增加迭代次數(shù)；太小，會(huì)使懲罰函數(shù)的性態(tài)變壞，甚至難以收斂到極值點(diǎn)。無一般有效方法，對(duì)于不同問題，都要經(jīng)過多次試算，才能決定一個(gè)適當(dāng)?shù)某踔怠．取

，根據(jù)計(jì)算結(jié)果再?zèng)Q定增加或減小

的值。

B．按經(jīng)驗(yàn)公式參考方法：懲罰因子的縮減系數(shù)的選取相鄰兩次迭代的懲罰因子的關(guān)系為為懲罰因子的縮減系數(shù)，其為小于1的正數(shù)，通常取值范圍在之間。收斂條件內(nèi)點(diǎn)法的計(jì)算步驟①選取可行的初始點(diǎn)

，懲罰因子的初始值

，縮減系數(shù)以及收斂精度

。令迭代次數(shù)

②構(gòu)造懲罰函數(shù)

，選擇適當(dāng)?shù)臒o約束優(yōu)化方法，求函數(shù)

的無約束極值，得

點(diǎn)。③用收斂條件判別迭代是否收斂，若滿足收斂條件，迭代終止。約束最優(yōu)解為；否則令，轉(zhuǎn)步驟2。

內(nèi)點(diǎn)法程序框圖（2）外點(diǎn)懲罰函數(shù)法（外點(diǎn)法）基本思想：與內(nèi)點(diǎn)法將懲罰函數(shù)定義于可行域內(nèi)不同，外點(diǎn)法是將懲罰函數(shù)定義于可行區(qū)域的外部。序列迭代點(diǎn)從可行域外部逐漸逼近約束邊界上的最優(yōu)點(diǎn)。

外點(diǎn)法可以用來求解含不等式和等式約束的優(yōu)化問題。外點(diǎn)罰函數(shù)中的罰因子是一遞增數(shù)列，即

對(duì)于等式約束的優(yōu)化問題，取外點(diǎn)罰函數(shù)的形式為對(duì)于同時(shí)具有不等式和等式約束問題，其罰函數(shù)的表達(dá)式為(2-75)

(2-74)

在外點(diǎn)罰函數(shù)法中，為保證罰因子

為遞增數(shù)列，取式中:c'為遞增系數(shù)，c'>1。

對(duì)于約束優(yōu)化問題轉(zhuǎn)化后的外點(diǎn)懲罰函數(shù)的形式為式中：

——懲罰因子，它是由小到大，且趨近于

外點(diǎn)法的迭代過程在可行域之外進(jìn)行，懲罰項(xiàng)的作用是迫使迭代點(diǎn)逼近約束邊界或等式約束曲面。由懲罰項(xiàng)的形式可知，當(dāng)?shù)c(diǎn)不可行時(shí)，懲罰項(xiàng)的值大于0。遞增系數(shù)c的選取可按經(jīng)驗(yàn)公式選取（r0=1,c=10）例:用外點(diǎn)法求解下列有約束優(yōu)化問題解:懲罰函數(shù)為：用解析法求函數(shù)的極小值，運(yùn)用極值條件：注意：應(yīng)舍去在可行域的點(diǎn)。則無約束極值點(diǎn)為當(dāng)懲罰因子漸增時(shí)，由下表可看出收斂情況。外點(diǎn)罰函數(shù)的程序計(jì)算框圖，見圖2-37。

外點(diǎn)罰函數(shù)法的迭代步驟與內(nèi)點(diǎn)法基本相同。圖2-37外點(diǎn)法的程序框圖

外點(diǎn)法的特點(diǎn)：

1．初始點(diǎn)可以任選，但應(yīng)使各函數(shù)有定義；2．對(duì)等式約束和不等式約束均可適用；3．僅最優(yōu)解為可行設(shè)計(jì)方案；4．一般收斂較快；5．初始罰因子要選擇得當(dāng)；6．懲罰因子為遞增，遞增率