第五章-懲罰函數(shù)法

5.3.4懲罰函數(shù)法懲罰函數(shù)法簡(jiǎn)介總結(jié)2021/6/271懲罰函數(shù)法簡(jiǎn)介

懲罰函數(shù)法是一種使用很廣泛、很有效的間接法?；驹恚喊鸭s束優(yōu)化問題轉(zhuǎn)化成無(wú)約束優(yōu)化問題來求解。兩個(gè)前提條件：一是不破壞原約束的約束條件二是最優(yōu)解必須歸結(jié)到原約束問題的最優(yōu)解上去按照懲罰函數(shù)的構(gòu)成方式，懲罰函數(shù)法分為三種：外點(diǎn)法、內(nèi)點(diǎn)法、混合法2021/6/272懲罰項(xiàng)r(k)、m(k)-----罰因子懲罰函數(shù)2021/6/2735.3.4.1內(nèi)點(diǎn)法㈠引例設(shè)有一維不等式約束優(yōu)化問題的數(shù)學(xué)模型S.T.:2021/6/274由圖可見，目標(biāo)函數(shù)的可行域?yàn)閤≥b，在可行域內(nèi)目標(biāo)函數(shù)單調(diào)上升，它的最優(yōu)解顯然是x*=b，F(xiàn)*=ab2021/6/275對(duì)引例的懲罰函數(shù)進(jìn)行分析，以對(duì)內(nèi)點(diǎn)法有初步認(rèn)識(shí)：⑴本問題是不等式約束優(yōu)化問題，故只有一項(xiàng)懲罰項(xiàng)，一個(gè)罰因子⑵規(guī)定罰因子為某一正數(shù)，當(dāng)?shù)c(diǎn)是在可行域內(nèi)時(shí)，則懲罰項(xiàng)的值必為正值，因此必有2021/6/276而且，當(dāng)x越趨近于約束邊界時(shí)，由于懲罰項(xiàng)增大，所以罰函數(shù)的值越大。當(dāng)x←b時(shí)，罰函數(shù)的值將趨近于+∞。因此，當(dāng)初始點(diǎn)取在可行域內(nèi)，求函數(shù)的極小值時(shí)，只要適當(dāng)控制搜索步長(zhǎng)，防止迭代點(diǎn)跨入非可行域，則所搜索到的無(wú)約束極小點(diǎn)x*必可保持在可行域內(nèi)。⑶若對(duì)于罰因子的取值由初始的逐漸變小時(shí)，懲罰函數(shù)愈逼近于原目標(biāo)函數(shù)F（x），罰函數(shù)曲線越來越接近于原F（x）=ax直線，如圖所示，對(duì)應(yīng)罰函數(shù)的最優(yōu)點(diǎn)列不斷趨近于原約束優(yōu)化問題的最優(yōu)點(diǎn)x*=b2021/6/277小結(jié)

由以上可見，如果選擇一個(gè)可行點(diǎn)作初始點(diǎn)，令其罰因子由大變小，通過求罰函數(shù)的一系列最優(yōu)點(diǎn)，顯見，無(wú)約束最優(yōu)點(diǎn)序列將逐漸趨近于原約束優(yōu)化問題的最優(yōu)點(diǎn)x*。2021/6/278㈡內(nèi)點(diǎn)罰數(shù)法的形式及特點(diǎn)⑴具有不等式約束的優(yōu)化問題的數(shù)學(xué)模型u=1，2……，p⑵構(gòu)造如下形式的內(nèi)點(diǎn)罰函數(shù)S.T.:2021/6/279關(guān)于懲罰因子規(guī)定為正，即。且在優(yōu)化過程中是減小的，為確保為遞減數(shù)列，取常數(shù)C0<C<1稱系數(shù)C為罰因子降低系數(shù)=0或關(guān)于懲罰項(xiàng)，由于在可行域內(nèi)有，且永遠(yuǎn)取正值，故在可行域內(nèi)懲罰項(xiàng)永為正。的值越小則懲罰項(xiàng)的值越小。2021/6/2710

由于在約束邊界上有，因此，當(dāng)設(shè)計(jì)點(diǎn)趨于邊界時(shí)，懲罰項(xiàng)的值將趨于無(wú)窮大。由此可知，在可行域內(nèi)，始終有。

當(dāng)時(shí)，卻有，所以整個(gè)最優(yōu)化的實(shí)質(zhì)就是用罰函數(shù)去逼近原目標(biāo)函數(shù)F(x);

當(dāng)設(shè)計(jì)點(diǎn)逐漸由內(nèi)部趨近于邊界時(shí)，由于懲罰項(xiàng)無(wú)窮增大，則罰函數(shù)也將無(wú)窮增大。

從函數(shù)圖形上來看，猶如在可行域的邊界上筑起一道陡峭的高墻，使迭代點(diǎn)自動(dòng)保持在可行域內(nèi)，用此辦法來保證搜索過程自始至終不離開可行域。所以，內(nèi)點(diǎn)法也常稱為圍墻函數(shù)法。2021/6/2711⑶內(nèi)點(diǎn)罰函數(shù)法的求解過程

為了用懲罰函數(shù)去逼近原目標(biāo)函數(shù)F(x)，則要用F(x)及構(gòu)造一個(gè)無(wú)約束優(yōu)化問題的數(shù)學(xué)模型

選取初始點(diǎn)（原約束優(yōu)化問題的內(nèi)點(diǎn)），初始罰因子，罰因子降低系數(shù)C。用無(wú)約束優(yōu)化方法求上式無(wú)約束優(yōu)化問題的最優(yōu)解。2021/6/2712所得解為；當(dāng)k在增大的過程中，得到懲罰函數(shù)的無(wú)約束最優(yōu)點(diǎn)列為點(diǎn)列中各點(diǎn)均在可行域內(nèi)部，隨著k→∞的過程，點(diǎn)列將趨近于原約束問題的最優(yōu)解x*。即=x*由此可知，內(nèi)點(diǎn)法的序列無(wú)約束最優(yōu)點(diǎn)是在可行域內(nèi)部且趨近于約束最優(yōu)點(diǎn)x*的。內(nèi)點(diǎn)罰函數(shù)還可以按如下形式構(gòu)成2021/6/2713㈢初始點(diǎn)x(0)的選取

由于內(nèi)點(diǎn)法的搜索是在可行域內(nèi)進(jìn)行，顯然初始點(diǎn)必須是域內(nèi)可行點(diǎn)。須滿足確定初始點(diǎn)常用如下兩種方法⑴自定法即根據(jù)設(shè)計(jì)者的經(jīng)驗(yàn)或已有的計(jì)算資料自行決定某一可行點(diǎn)作為初始點(diǎn)。⑵搜索法任選一個(gè)設(shè)計(jì)點(diǎn)為初始點(diǎn)。通過對(duì)初始點(diǎn)約束函數(shù)值的檢驗(yàn)，按其對(duì)每個(gè)約束的不滿足程度加以調(diào)整，將點(diǎn)逐步引入到可行域內(nèi)，成為可行初始點(diǎn)，這就是搜索法。2021/6/2714㈣關(guān)于幾個(gè)參數(shù)的選擇⑴初始罰因子r(0)的選取

如果值選得太大，則在一開始罰函數(shù)的懲罰項(xiàng)的值將遠(yuǎn)遠(yuǎn)超出原目標(biāo)函數(shù)的值，因此，它的第一次無(wú)約束極小點(diǎn)將遠(yuǎn)離原問題的約束最優(yōu)點(diǎn)。在以后的迭代中，需要很長(zhǎng)時(shí)間的搜索才能使序列無(wú)約束極小點(diǎn)逐漸向約束最優(yōu)點(diǎn)逼近。

如果值選得太小，則在一開始懲罰項(xiàng)的作用甚小，而在可行域內(nèi)部懲罰函數(shù)與原目標(biāo)函數(shù)F(x)很相近，只在約束邊界附近罰函數(shù)值才突然增高。這樣，使其罰函數(shù)在在約束邊界附近出現(xiàn)深溝谷地，罰函數(shù)的性態(tài)變得惡劣。2021/6/2715如下圖，對(duì)于有深溝谷地性態(tài)差的函數(shù)，不僅搜索所需的時(shí)間長(zhǎng)，而且很難使迭代點(diǎn)進(jìn)入最優(yōu)的鄰域，以致極易使迭代點(diǎn)落入非可行域而導(dǎo)致計(jì)算的失敗。r（0）=1~50或2021/6/2716⑵遞減系數(shù)C的選擇

罰因子遞減系數(shù)C的選擇，一般認(rèn)為對(duì)算法的成敗影響不大。規(guī)定0<C<1。

若C值選得較小，罰因子下降快，可以減少無(wú)約束優(yōu)化的次數(shù)，但因前后兩次無(wú)約束最優(yōu)點(diǎn)之間的距離較遠(yuǎn)，有可能使后一次無(wú)約束優(yōu)化本身的迭代次數(shù)增多，而且使序列最優(yōu)點(diǎn)的間隔加大，對(duì)約束最優(yōu)點(diǎn)的逼近不利。相反，若C值取得較大，則無(wú)約束優(yōu)化次數(shù)就要增多。通常建議取C=0.1--0.52021/6/2717㈤終止準(zhǔn)則

隨著罰因子的值不斷減小，罰函數(shù)的序列無(wú)約束最優(yōu)點(diǎn)將越來越趨近于原約束優(yōu)化問題的最優(yōu)點(diǎn)。

設(shè)懲罰函數(shù)的無(wú)約束最優(yōu)點(diǎn)列為對(duì)應(yīng)的罰函數(shù)值為2021/6/2718終止準(zhǔn)則可用下述兩者之一⑴相鄰兩次懲罰函數(shù)無(wú)約束最優(yōu)點(diǎn)之間的距離已足夠的小。設(shè)ε1為收斂精度，一般取ε1=10-4-10-5，則需要滿足⑵相鄰兩次懲罰函數(shù)值的相對(duì)變化量已足夠小。設(shè)ε2為收斂精度，一般取ε2=10-3-10-4，則需要滿足2021/6/2719㈥算法步驟⑴構(gòu)造內(nèi)點(diǎn)懲罰函數(shù)⑵選擇可行初始點(diǎn)，初始罰因子，罰因子降低系數(shù)C，收斂精度與，置k←0⑶求無(wú)約束優(yōu)化問題，有最優(yōu)點(diǎn)。⑷當(dāng)k=0時(shí)轉(zhuǎn)步驟⑸，否則轉(zhuǎn)步驟⑹⑸置k←k+1，，并轉(zhuǎn)步驟⑶⑹由終止準(zhǔn)則，若滿足則轉(zhuǎn)步驟⑺，否則轉(zhuǎn)⑸⑺,輸出最優(yōu)解(x*,F*)2021/6/2720內(nèi)點(diǎn)法流程圖給定：x(0)∈D,r(0),C,ε1,ε2k←0K=0?入口用無(wú)約束優(yōu)化方法求罰函數(shù)的優(yōu)化點(diǎn)出口++--2021/6/2721㈦內(nèi)點(diǎn)罰函數(shù)的特點(diǎn)

內(nèi)點(diǎn)法只適用于解不等式約束優(yōu)化問題。由于內(nèi)點(diǎn)法需要在可行域內(nèi)部進(jìn)行搜索，所以初始點(diǎn)必須在可行域內(nèi)部選取可行設(shè)計(jì)點(diǎn)。內(nèi)點(diǎn)法的突出優(yōu)點(diǎn)在于每個(gè)迭代點(diǎn)都是可行點(diǎn)因此，當(dāng)?shù)_(dá)到一定階段時(shí)，盡管尚沒有達(dá)到最優(yōu)點(diǎn)，但也可以被接受為一個(gè)較好的近似解。2021/6/27225.3.4.2外點(diǎn)法外點(diǎn)法可以解不等式約束優(yōu)化問題或等式約束優(yōu)化問題㈠引例設(shè)有一維不等式優(yōu)化問題的數(shù)學(xué)模型用外點(diǎn)法構(gòu)造懲罰函數(shù)，具體構(gòu)造形式如下x≥bx<bS.T.:2021/6/2723寫成另一種形式2021/6/2724

如上圖，此處的懲罰函數(shù)也是由原目標(biāo)函數(shù)F(x)與懲罰項(xiàng)而組成。懲罰項(xiàng)中包含有可調(diào)整的參數(shù)r(k)與約束函數(shù)。

由懲罰項(xiàng)的構(gòu)造可知，若迭代點(diǎn)在可行域的內(nèi)部，懲罰項(xiàng)的值為0，懲罰函數(shù)值與原目標(biāo)函數(shù)值相等；而若在非可行域（即可行域的外部），懲罰項(xiàng)是以約束函數(shù)的平方加大的，即迭代點(diǎn)違反約束越嚴(yán)重，懲罰項(xiàng)的值增加的越大。因此，在非可行域內(nèi)，必有且罰因子r（k）越大，懲罰作用越明顯。

由圖，對(duì)于某r(k)值，求出懲罰函數(shù)的最優(yōu)點(diǎn)當(dāng)取罰因子為遞增數(shù)列，隨k的增加，罰函數(shù)的無(wú)約束最優(yōu)點(diǎn)序列為2021/6/2725

該序列將趨近與原約束問題的最優(yōu)點(diǎn)x*，x*=b。值得注意的是，盡管增加直至趨于無(wú)窮大，但最終的近似最優(yōu)點(diǎn)x*仍在可行域的外部。

即外點(diǎn)法構(gòu)造的罰函數(shù)是使迭代點(diǎn)從可行域的外部逐漸逼近約束最優(yōu)點(diǎn)，這正是外點(diǎn)法名稱的由來。2021/6/2726㈡外點(diǎn)罰函數(shù)法的形式及特點(diǎn)先討論解不等式約束優(yōu)化問題設(shè)有不等式約束優(yōu)化問題u=1，2……，p構(gòu)造外點(diǎn)法懲罰函數(shù)的常見形式取正遞增S.T.:2021/6/2727引入罰因子遞增系數(shù)C>1，并令=∞懲罰項(xiàng)的含義可用另一形式表示當(dāng)gu(x)≥0（x∈D）當(dāng)gu(x)<0（x∈D）在可行域內(nèi)（包括邊界）在非可行域，為遞增函數(shù)2021/6/2728外點(diǎn)罰函數(shù)的求解過程

用外點(diǎn)罰函數(shù)去逼近原目標(biāo)函數(shù)F(x)，構(gòu)造一個(gè)無(wú)約束優(yōu)化問題模型x∈Rn任選初始點(diǎn)x(0)，初始法罰因子r(0)>0,罰因子遞增系數(shù)C>1

對(duì)于r(k)為某一值，同過對(duì)懲罰函數(shù)的無(wú)約束求優(yōu)，可得最優(yōu)點(diǎn)。隨著k的增大，得無(wú)約束最優(yōu)點(diǎn)列2021/6/2729在k←∞的過程中，點(diǎn)列將趨近于原問題的最優(yōu)點(diǎn)實(shí)線為原目標(biāo)函數(shù)等值線虛線為罰函數(shù)等值線2021/6/2730總結(jié)

由上圖可見，兩種等值線在可行域內(nèi)部及邊界上是重合的；而在非可行域中，罰函數(shù)的等值線升高了。即只有在可行域外部懲罰項(xiàng)才起到懲罰的作用。r(k)值越大，懲罰作用越大。

由上b圖可知，在起作用約束邊界處罰函數(shù)等值線變得越密集和越陡峭。隨r(k)的增大，最優(yōu)點(diǎn)列將越接近于原約束優(yōu)化問題的最優(yōu)點(diǎn)x*。但須注意，近似的最優(yōu)點(diǎn)是落在邊界處非可行域一側(cè)。2021/6/2731㈢對(duì)幾個(gè)問題的討論（1）初始點(diǎn)x(0)的選取在可行域及非可行域內(nèi)均可。（2）初始罰因子r(0)和遞增系數(shù)C的選取外點(diǎn)法中，這兩者的選擇對(duì)算法的成敗和計(jì)算速度有顯著的影響。2021/6/2732

選取過小，則序貫無(wú)約束求解的次數(shù)就增多，收斂速度慢；反之，則在非可行域中，發(fā)函數(shù)比原目標(biāo)函數(shù)要大得多，特別在起作用約束邊界處產(chǎn)生尖點(diǎn)，函數(shù)性態(tài)變壞，從而限制了某些無(wú)約束優(yōu)化方法的使用，致使計(jì)算失敗。C的選取影響不大，通常C=5-102021/6/2733（3）約束容差帶

最優(yōu)點(diǎn)在非可行域內(nèi)，是一個(gè)非可行點(diǎn)，這對(duì)某些工程是不允許的。因此，可在約束邊界可行域一側(cè)加一條容差帶。相當(dāng)于將約束條件改為是容差量，通常2021/6/2734㈣終止準(zhǔn)則

隨著罰因子的值不斷增大，罰函數(shù)的序列無(wú)約束最優(yōu)點(diǎn)將越來越趨近于原約束優(yōu)化問題的最優(yōu)點(diǎn)。

設(shè)懲罰函數(shù)的無(wú)約束最優(yōu)點(diǎn)列為對(duì)應(yīng)的罰函數(shù)值為2021/6/2735終止準(zhǔn)則可用下述兩者之一⑴相鄰兩次懲罰函數(shù)無(wú)約束最優(yōu)點(diǎn)之間的距離已足夠的小。設(shè)ε1為收斂精度，一般取ε1=10-4-10-5，則需要滿足⑵相鄰兩次懲罰函數(shù)值的相對(duì)變化量已足夠小。設(shè)ε2為收斂精度，一般取ε2=10-3-10-4，則需要滿足2021/6/2736外點(diǎn)法流程圖給定：x(0)∈R,r(0),C,ε1,ε2k←0k=0?入口用無(wú)約束優(yōu)化方法求罰函數(shù)的優(yōu)化點(diǎn)出口++--㈣算法步驟與流程圖2021/6/2737⑶求，得最優(yōu)點(diǎn)⑷當(dāng)k=0時(shí)轉(zhuǎn)步驟⑸，否則轉(zhuǎn)步驟⑹⑸置k←k+1，，并轉(zhuǎn)步驟⑶⑹由終止準(zhǔn)則，若滿足則轉(zhuǎn)步驟⑺，否則轉(zhuǎn)⑸⑺,輸出最優(yōu)解(x*,F*)，停止計(jì)算。算法步驟⑴在n維空間任取初始點(diǎn)x（0）⑵選取初始罰因子r(0),遞增系數(shù)C，并置k←02021/6/2738㈤用外點(diǎn)罰函數(shù)法解等式約束優(yōu)化問題設(shè)有二維約束優(yōu)化問題h1(x)=x1+x2-10=0如右圖，h1(x)為該約束問題的可行域，這條直線以外的整個(gè)x1ox2平面為非可行域。目標(biāo)函數(shù)等值線與該直線的切點(diǎn)為最優(yōu)點(diǎn)最優(yōu)點(diǎn)S.T.:2021/6/2739按外點(diǎn)法的基本思想，構(gòu)造懲罰函數(shù)x∈Dx∈D

在可行域上，懲罰項(xiàng)的值為零，懲罰函數(shù)值與原目標(biāo)函數(shù)值相同；在非可行域上，懲罰函數(shù)的值恒為正，罰函數(shù)大于原目標(biāo)函數(shù)，即在可行域外懲罰項(xiàng)起到了懲罰作用。在k←∞的過程中，點(diǎn)列將趨近于原問題的最優(yōu)點(diǎn)

對(duì)于m(k)，隨著k的增大，得無(wú)約束最優(yōu)點(diǎn)列2021/6/2740推廣到具有一般的等式約束優(yōu)化問題首先構(gòu)造如下形式的外點(diǎn)懲罰函數(shù)懲罰因子m（k）規(guī)定取正，m(0)<m(1)<……。即罰因子遞增系數(shù)C>1在可行域上值為零，非可行域上，值恒大于零S.T.:2021/6/27415.3.4.3混合法

用罰函數(shù)法解決有等式約束和不等式約束的一般約束（GP型）優(yōu)化問題的方法，把它稱為混合懲罰函數(shù)法，簡(jiǎn)稱混合法。1混合法懲罰函數(shù)的形式及特點(diǎn)一般約束問題的優(yōu)化模型S.T.:2021/6/2742用懲罰函數(shù)法將其轉(zhuǎn)化為無(wú)約束優(yōu)化問題

懲罰函數(shù)是由原目標(biāo)函數(shù)及包含約束函數(shù)的懲罰項(xiàng)組成。由于該問題的約束條件包含不等式約束與等式約束兩部分。因此，懲罰項(xiàng)也應(yīng)由對(duì)應(yīng)的兩部分組成。對(duì)應(yīng)等式約束部分的只有外點(diǎn)法一種形式，而對(duì)應(yīng)不等式的約束部分有內(nèi)點(diǎn)法或外點(diǎn)法兩種形式。因此按照對(duì)不等式約束處理的方法不同，混合法懲罰函數(shù)也具有兩種形式。2021/6/2743⑴內(nèi)點(diǎn)形式的混合法

不等式約束部分按內(nèi)點(diǎn)法形式處理