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

第五章懲罰函數(shù)法第1頁(yè)，共49頁(yè)。懲罰函數(shù)法簡(jiǎn)介懲罰函數(shù)法是一種使用很廣泛、很有效的間接法?；驹恚喊鸭s束優(yōu)化問(wèn)題轉(zhuǎn)化成無(wú)約束優(yōu)化問(wèn)題來(lái)求解。兩個(gè)前提條件：一是不破壞原約束的約束條件二是最優(yōu)解必須歸結(jié)到原約束問(wèn)題的最優(yōu)解上去按照懲罰函數(shù)的構(gòu)成方式，懲罰函數(shù)法分為三種：外點(diǎn)法、內(nèi)點(diǎn)法、混合法第2頁(yè)，共49頁(yè)。懲罰項(xiàng)r(k)、m(k)-----罰因子懲罰函數(shù)第3頁(yè)，共49頁(yè)。5.3.4.1內(nèi)點(diǎn)法㈠引例設(shè)有一維不等式約束優(yōu)化問(wèn)題的數(shù)學(xué)模型S.T.:第4頁(yè)，共49頁(yè)。由圖可見(jiàn)，目標(biāo)函數(shù)的可行域?yàn)閤≥b，在可行域內(nèi)目標(biāo)函數(shù)單調(diào)上升，它的最優(yōu)解顯然是x*=b，F(xiàn)*=ab第5頁(yè)，共49頁(yè)。對(duì)引例的懲罰函數(shù)進(jìn)行分析，以對(duì)內(nèi)點(diǎn)法有初步認(rèn)識(shí)：⑴本問(wèn)題是不等式約束優(yōu)化問(wèn)題，故只有一項(xiàng)懲罰項(xiàng)，一個(gè)罰因子⑵規(guī)定罰因子為某一正數(shù)，當(dāng)?shù)c(diǎn)是在可行域內(nèi)時(shí)，則懲罰項(xiàng)的值必為正值，因此必有第6頁(yè)，共49頁(yè)。而且，當(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ù)曲線越來(lái)越接近于原F（x）=ax直線，如圖所示，對(duì)應(yīng)罰函數(shù)的最優(yōu)點(diǎn)列不斷趨近于原約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)x*=b第7頁(yè)，共49頁(yè)。小結(jié)由以上可見(jiàn)，如果選擇一個(gè)可行點(diǎn)作初始點(diǎn)，令其罰因子由大變小，通過(guò)求罰函數(shù)的一系列最優(yōu)點(diǎn)，顯見(jiàn)，無(wú)約束最優(yōu)點(diǎn)序列將逐漸趨近于原約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)x*。第8頁(yè)，共49頁(yè)。㈡內(nèi)點(diǎn)罰數(shù)法的形式及特點(diǎn)⑴具有不等式約束的優(yōu)化問(wèn)題的數(shù)學(xué)模型u=1，2……，p⑵構(gòu)造如下形式的內(nèi)點(diǎn)罰函數(shù)S.T.:第9頁(yè)，共49頁(yè)。關(guān)于懲罰因子規(guī)定為正，即。且在優(yōu)化過(guò)程中是減小的，為確保為遞減數(shù)列，取常數(shù)C0<C<1稱(chēng)系數(shù)C為罰因子降低系數(shù)=0或關(guān)于懲罰項(xiàng)，由于在可行域內(nèi)有，且永遠(yuǎn)取正值，故在可行域內(nèi)懲罰項(xiàng)永為正。的值越小則懲罰項(xiàng)的值越小。第10頁(yè)，共49頁(yè)。由于在約束邊界上有，因此，當(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ù)圖形上來(lái)看，猶如在可行域的邊界上筑起一道陡峭的高墻，使迭代點(diǎn)自動(dòng)保持在可行域內(nèi)，用此辦法來(lái)保證搜索過(guò)程自始至終不離開(kāi)可行域。所以，內(nèi)點(diǎn)法也常稱(chēng)為圍墻函數(shù)法。第11頁(yè)，共49頁(yè)。⑶內(nèi)點(diǎn)罰函數(shù)法的求解過(guò)程為了用懲罰函數(shù)去逼近原目標(biāo)函數(shù)F(x)，則要用F(x)及構(gòu)造一個(gè)無(wú)約束優(yōu)化問(wèn)題的數(shù)學(xué)模型選取初始點(diǎn)（原約束優(yōu)化問(wèn)題的內(nèi)點(diǎn)），初始罰因子，罰因子降低系數(shù)C。用無(wú)約束優(yōu)化方法求上式無(wú)約束優(yōu)化問(wèn)題的最優(yōu)解。第12頁(yè)，共49頁(yè)。所得解為；當(dāng)k在增大的過(guò)程中，得到懲罰函數(shù)的無(wú)約束最優(yōu)點(diǎn)列為點(diǎn)列中各點(diǎn)均在可行域內(nèi)部，隨著k→∞的過(guò)程，點(diǎn)列將趨近于原約束問(wè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)成第13頁(yè)，共49頁(yè)。㈢初始點(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)。通過(guò)對(duì)初始點(diǎn)約束函數(shù)值的檢驗(yàn)，按其對(duì)每個(gè)約束的不滿足程度加以調(diào)整，將點(diǎn)逐步引入到可行域內(nèi)，成為可行初始點(diǎn)，這就是搜索法。第14頁(yè)，共49頁(yè)。㈣關(guān)于幾個(gè)參數(shù)的選擇⑴初始罰因子r(0)的選取如果值選得太大，則在一開(kāi)始罰函數(shù)的懲罰項(xiàng)的值將遠(yuǎn)遠(yuǎn)超出原目標(biāo)函數(shù)的值，因此，它的第一次無(wú)約束極小點(diǎn)將遠(yuǎn)離原問(wèn)題的約束最優(yōu)點(diǎn)。在以后的迭代中，需要很長(zhǎng)時(shí)間的搜索才能使序列無(wú)約束極小點(diǎn)逐漸向約束最優(yōu)點(diǎn)逼近。如果值選得太小，則在一開(kāi)始懲罰項(xiàng)的作用甚小，而在可行域內(nèi)部懲罰函數(shù)與原目標(biāo)函數(shù)F(x)很相近，只在約束邊界附近罰函數(shù)值才突然增高。這樣，使其罰函數(shù)在在約束邊界附近出現(xiàn)深溝谷地，罰函數(shù)的性態(tài)變得惡劣。第15頁(yè)，共49頁(yè)。如下圖，對(duì)于有深溝谷地性態(tài)差的函數(shù)，不僅搜索所需的時(shí)間長(zhǎng)，而且很難使迭代點(diǎn)進(jìn)入最優(yōu)的鄰域，以致極易使迭代點(diǎn)落入非可行域而導(dǎo)致計(jì)算的失敗。r（0）=1~50或第16頁(yè)，共49頁(yè)。⑵遞減系數(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.5第17頁(yè)，共49頁(yè)。㈤終止準(zhǔn)則隨著罰因子的值不斷減小，罰函數(shù)的序列無(wú)約束最優(yōu)點(diǎn)將越來(lái)越趨近于原約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)。設(shè)懲罰函數(shù)的無(wú)約束最優(yōu)點(diǎn)列為對(duì)應(yīng)的罰函數(shù)值為第18頁(yè)，共49頁(yè)。終止準(zhǔn)則可用下述兩者之一⑴相鄰兩次懲罰函數(shù)無(wú)約束最優(yōu)點(diǎn)之間的距離已足夠的小。設(shè)ε1為收斂精度，一般取ε1=10-4-10-5，則需要滿足⑵相鄰兩次懲罰函數(shù)值的相對(duì)變化量已足夠小。設(shè)ε2為收斂精度，一般取ε2=10-3-10-4，則需要滿足第19頁(yè)，共49頁(yè)。㈥算法步驟⑴構(gòu)造內(nèi)點(diǎn)懲罰函數(shù)⑵選擇可行初始點(diǎn)，初始罰因子，罰因子降低系數(shù)C，收斂精度與，置k←0⑶求無(wú)約束優(yōu)化問(wèn)題，有最優(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*)第20頁(yè)，共49頁(yè)。內(nèi)點(diǎn)法流程圖給定：x(0)∈D,r(0),C,ε1,ε2k←0K=0?入口用無(wú)約束優(yōu)化方法求罰函數(shù)的優(yōu)化點(diǎn)出口++--第21頁(yè)，共49頁(yè)。㈦內(nèi)點(diǎn)罰函數(shù)的特點(diǎn)內(nèi)點(diǎn)法只適用于解不等式約束優(yōu)化問(wèn)題。由于內(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í)，盡管尚沒(méi)有達(dá)到最優(yōu)點(diǎn)，但也可以被接受為一個(gè)較好的近似解。第22頁(yè)，共49頁(yè)。5.3.4.2外點(diǎn)法外點(diǎn)法可以解不等式約束優(yōu)化問(wèn)題或等式約束優(yōu)化問(wèn)題㈠引例設(shè)有一維不等式優(yōu)化問(wèn)題的數(shù)學(xué)模型用外點(diǎn)法構(gòu)造懲罰函數(shù)，具體構(gòu)造形式如下x≥bx<bS.T.:第23頁(yè)，共49頁(yè)。寫(xiě)成另一種形式第24頁(yè)，共49頁(yè)。如上圖，此處的懲罰函數(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)序列為第25頁(yè)，共49頁(yè)。該序列將趨近與原約束問(wèn)題的最優(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)法名稱(chēng)的由來(lái)。第26頁(yè)，共49頁(yè)。㈡外點(diǎn)罰函數(shù)法的形式及特點(diǎn)先討論解不等式約束優(yōu)化問(wèn)題設(shè)有不等式約束優(yōu)化問(wèn)題u=1，2……，p構(gòu)造外點(diǎn)法懲罰函數(shù)的常見(jiàn)形式取正遞增S.T.:第27頁(yè)，共49頁(yè)。引入罰因子遞增系數(shù)C>1，并令=∞懲罰項(xiàng)的含義可用另一形式表示當(dāng)gu(x)≥0（x∈D）當(dāng)gu(x)<0（x∈D）在可行域內(nèi)（包括邊界）在非可行域，為遞增函數(shù)第28頁(yè)，共49頁(yè)。外點(diǎn)罰函數(shù)的求解過(guò)程用外點(diǎn)罰函數(shù)去逼近原目標(biāo)函數(shù)F(x)，構(gòu)造一個(gè)無(wú)約束優(yōu)化問(wèn)題模型x∈Rn任選初始點(diǎn)x(0)，初始法罰因子r(0)>0,罰因子遞增系數(shù)C>1對(duì)于r(k)為某一值，同過(guò)對(duì)懲罰函數(shù)的無(wú)約束求優(yōu)，可得最優(yōu)點(diǎn)。隨著k的增大，得無(wú)約束最優(yōu)點(diǎn)列第29頁(yè)，共49頁(yè)。在k←∞的過(guò)程中，點(diǎn)列將趨近于原問(wèn)題的最優(yōu)點(diǎn)實(shí)線為原目標(biāo)函數(shù)等值線虛線為罰函數(shù)等值線第30頁(yè)，共49頁(yè)。總結(jié)由上圖可見(jiàn)，兩種等值線在可行域內(nèi)部及邊界上是重合的；而在非可行域中，罰函數(shù)的等值線升高了。即只有在可行域外部懲罰項(xiàng)才起到懲罰的作用。r(k)值越大，懲罰作用越大。由上b圖可知，在起作用約束邊界處罰函數(shù)等值線變得越密集和越陡峭。隨r(k)的增大，最優(yōu)點(diǎn)列將越接近于原約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)x*。但須注意，近似的最優(yōu)點(diǎn)是落在邊界處非可行域一側(cè)。第31頁(yè)，共49頁(yè)。㈢對(duì)幾個(gè)問(wèn)題的討論（1）初始點(diǎn)x(0)的選取在可行域及非可行域內(nèi)均可。（2）初始罰因子r(0)和遞增系數(shù)C的選取外點(diǎn)法中，這兩者的選擇對(duì)算法的成敗和計(jì)算速度有顯著的影響。第32頁(yè)，共49頁(yè)。選取過(guò)小，則序貫無(wú)約束求解的次數(shù)就增多，收斂速度慢；反之，則在非可行域中，發(fā)函數(shù)比原目標(biāo)函數(shù)要大得多，特別在起作用約束邊界處產(chǎn)生尖點(diǎn)，函數(shù)性態(tài)變壞，從而限制了某些無(wú)約束優(yōu)化方法的使用，致使計(jì)算失敗。C的選取影響不大，通常C=5-10第33頁(yè)，共49頁(yè)。（3）約束容差帶最優(yōu)點(diǎn)在非可行域內(nèi)，是一個(gè)非可行點(diǎn)，這對(duì)某些工程是不允許的。因此，可在約束邊界可行域一側(cè)加一條容差帶。相當(dāng)于將約束條件改為是容差量，通常第34頁(yè)，共49頁(yè)。㈣終止準(zhǔn)則隨著罰因子的值不斷增大，罰函數(shù)的序列無(wú)約束最優(yōu)點(diǎn)將越來(lái)越趨近于原約束優(yōu)化問(wèn)題的最優(yōu)點(diǎn)。設(shè)懲罰函數(shù)的無(wú)約束最優(yōu)點(diǎn)列為對(duì)應(yīng)的罰函數(shù)值為第35頁(yè)，共49頁(yè)。終止準(zhǔn)則可用下述兩者之一⑴相鄰兩次懲罰函數(shù)無(wú)約束最優(yōu)點(diǎn)之間的距離已足夠的小。設(shè)ε1為收斂精度，一般取ε1=10-4-10-5，則需要滿足⑵相鄰兩次懲罰函數(shù)值的相對(duì)變化量已足夠小。設(shè)ε2為收斂精度，一般取ε2=10-3-10-4，則需要滿足第36頁(yè)，共49頁(yè)。外點(diǎn)法流程圖給定：x(0)∈R,r(0),C,ε1,ε2k←0k=0?入口用無(wú)約束優(yōu)化方法求罰函數(shù)的優(yōu)化點(diǎn)出口++--㈣算法步驟與流程圖第37頁(yè)，共49頁(yè)。⑶求，得最優(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←0第38頁(yè)，共49頁(yè)。㈤用外點(diǎn)罰函數(shù)法解等式約束優(yōu)化問(wèn)題設(shè)有二維約束優(yōu)化問(wèn)題h1(x)=x1+x2-10=0如右圖，h1(x)為該約束問(wèn)題的可行域，這條直線以外的整個(gè)x1ox2平面為非可行域。目標(biāo)函數(shù)等值線與該直線的切點(diǎn)為最優(yōu)點(diǎn)最優(yōu)點(diǎn)S.T.:第39頁(yè)，共49頁(yè)。按外點(diǎn)法的基本思想，構(gòu)造懲罰函數(shù)x∈Dx∈D在可行域上，懲罰項(xiàng)的值為零，懲罰函數(shù)值與原目標(biāo)函數(shù)值相同；在非可行域上，懲罰函數(shù)的值恒為正，罰函數(shù)大于原目標(biāo)函數(shù)，即在可行域外懲罰項(xiàng)起到了懲罰作用。在k←∞的過(guò)程中，點(diǎn)列將趨近于原問(wèn)題的最優(yōu)點(diǎn)對(duì)于m(k)，隨著k的增大，得無(wú)約束最優(yōu)點(diǎn)列第40頁(yè)，共49頁(yè)。推廣到具有一般的等式約束優(yōu)化問(wèn)題首先構(gòu)造如下形式的外點(diǎn)懲罰函數(shù)懲罰因子m（k）規(guī)定取正，m(0)<m(1)<……。即罰因子遞增系數(shù)C>1在可行域上值為零，非可行域上，值恒大于零S.T.:第41頁(yè)，共49頁(yè)。5.3.4.3混合法用罰函數(shù)法解決有等式約束和不等式約束的一般約束（GP型）優(yōu)化問(wèn)題的方法，把它稱(chēng)為混合懲罰函數(shù)法，簡(jiǎn)稱(chēng)混合法。1混合法懲罰函數(shù)的形式及特點(diǎn)一般約束問(wèn)題的優(yōu)化模型S.T.:第42頁(yè)，共49頁(yè)。用懲罰函數(shù)法將其轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題懲罰函數(shù)是由原目標(biāo)函數(shù)及包含約束函數(shù)的懲罰項(xiàng)組成。由于該問(wèn)題的約束條件包