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

第五章懲罰函數(shù)法第1頁，共49頁。懲罰函數(shù)法簡介懲罰函數(shù)法是一種使用很廣泛、很有效的間接法?；驹恚喊鸭s束優(yōu)化問題轉(zhuǎn)化成無約束優(yōu)化問題來求解。兩個前提條件：一是不破壞原約束的約束條件二是最優(yōu)解必須歸結(jié)到原約束問題的最優(yōu)解上去按照懲罰函數(shù)的構(gòu)成方式，懲罰函數(shù)法分為三種：外點法、內(nèi)點法、混合法第2頁，共49頁。懲罰項r(k)、m(k)-----罰因子懲罰函數(shù)第3頁，共49頁。5.3.4.1內(nèi)點法㈠引例設有一維不等式約束優(yōu)化問題的數(shù)學模型S.T.:第4頁，共49頁。由圖可見，目標函數(shù)的可行域為x≥b，在可行域內(nèi)目標函數(shù)單調(diào)上升，它的最優(yōu)解顯然是x*=b，F(xiàn)*=ab第5頁，共49頁。對引例的懲罰函數(shù)進行分析，以對內(nèi)點法有初步認識：⑴本問題是不等式約束優(yōu)化問題，故只有一項懲罰項，一個罰因子⑵規(guī)定罰因子為某一正數(shù)，當?shù)c是在可行域內(nèi)時，則懲罰項的值必為正值，因此必有第6頁，共49頁。而且，當x越趨近于約束邊界時，由于懲罰項增大，所以罰函數(shù)的值越大。當x←b時，罰函數(shù)的值將趨近于+∞。因此，當初始點取在可行域內(nèi)，求函數(shù)的極小值時，只要適當控制搜索步長，防止迭代點跨入非可行域，則所搜索到的無約束極小點x*必可保持在可行域內(nèi)。⑶若對于罰因子的取值由初始的逐漸變小時，懲罰函數(shù)愈逼近于原目標函數(shù)F（x），罰函數(shù)曲線越來越接近于原F（x）=ax直線，如圖所示，對應罰函數(shù)的最優(yōu)點列不斷趨近于原約束優(yōu)化問題的最優(yōu)點x*=b第7頁，共49頁。小結(jié)由以上可見，如果選擇一個可行點作初始點，令其罰因子由大變小，通過求罰函數(shù)的一系列最優(yōu)點，顯見，無約束最優(yōu)點序列將逐漸趨近于原約束優(yōu)化問題的最優(yōu)點x*。第8頁，共49頁。㈡內(nèi)點罰數(shù)法的形式及特點⑴具有不等式約束的優(yōu)化問題的數(shù)學模型u=1，2……，p⑵構(gòu)造如下形式的內(nèi)點罰函數(shù)S.T.:第9頁，共49頁。關于懲罰因子規(guī)定為正，即。且在優(yōu)化過程中是減小的，為確保為遞減數(shù)列，取常數(shù)C0<C<1稱系數(shù)C為罰因子降低系數(shù)=0或關于懲罰項，由于在可行域內(nèi)有，且永遠取正值，故在可行域內(nèi)懲罰項永為正。的值越小則懲罰項的值越小。第10頁，共49頁。由于在約束邊界上有，因此，當設計點趨于邊界時，懲罰項的值將趨于無窮大。由此可知，在可行域內(nèi)，始終有。當時，卻有，所以整個最優(yōu)化的實質(zhì)就是用罰函數(shù)去逼近原目標函數(shù)F(x);當設計點逐漸由內(nèi)部趨近于邊界時，由于懲罰項無窮增大，則罰函數(shù)也將無窮增大。從函數(shù)圖形上來看，猶如在可行域的邊界上筑起一道陡峭的高墻，使迭代點自動保持在可行域內(nèi)，用此辦法來保證搜索過程自始至終不離開可行域。所以，內(nèi)點法也常稱為圍墻函數(shù)法。第11頁，共49頁。⑶內(nèi)點罰函數(shù)法的求解過程為了用懲罰函數(shù)去逼近原目標函數(shù)F(x)，則要用F(x)及構(gòu)造一個無約束優(yōu)化問題的數(shù)學模型選取初始點（原約束優(yōu)化問題的內(nèi)點），初始罰因子，罰因子降低系數(shù)C。用無約束優(yōu)化方法求上式無約束優(yōu)化問題的最優(yōu)解。第12頁，共49頁。所得解為；當k在增大的過程中，得到懲罰函數(shù)的無約束最優(yōu)點列為點列中各點均在可行域內(nèi)部，隨著k→∞的過程，點列將趨近于原約束問題的最優(yōu)解x*。即=x*由此可知，內(nèi)點法的序列無約束最優(yōu)點是在可行域內(nèi)部且趨近于約束最優(yōu)點x*的。內(nèi)點罰函數(shù)還可以按如下形式構(gòu)成第13頁，共49頁。㈢初始點x(0)的選取由于內(nèi)點法的搜索是在可行域內(nèi)進行，顯然初始點必須是域內(nèi)可行點。須滿足確定初始點常用如下兩種方法⑴自定法即根據(jù)設計者的經(jīng)驗或已有的計算資料自行決定某一可行點作為初始點。⑵搜索法任選一個設計點為初始點。通過對初始點約束函數(shù)值的檢驗，按其對每個約束的不滿足程度加以調(diào)整，將點逐步引入到可行域內(nèi)，成為可行初始點，這就是搜索法。第14頁，共49頁。㈣關于幾個參數(shù)的選擇⑴初始罰因子r(0)的選取如果值選得太大，則在一開始罰函數(shù)的懲罰項的值將遠遠超出原目標函數(shù)的值，因此，它的第一次無約束極小點將遠離原問題的約束最優(yōu)點。在以后的迭代中，需要很長時間的搜索才能使序列無約束極小點逐漸向約束最優(yōu)點逼近。如果值選得太小，則在一開始懲罰項的作用甚小，而在可行域內(nèi)部懲罰函數(shù)與原目標函數(shù)F(x)很相近，只在約束邊界附近罰函數(shù)值才突然增高。這樣，使其罰函數(shù)在在約束邊界附近出現(xiàn)深溝谷地，罰函數(shù)的性態(tài)變得惡劣。第15頁，共49頁。如下圖，對于有深溝谷地性態(tài)差的函數(shù)，不僅搜索所需的時間長，而且很難使迭代點進入最優(yōu)的鄰域，以致極易使迭代點落入非可行域而導致計算的失敗。r（0）=1~50或第16頁，共49頁。⑵遞減系數(shù)C的選擇罰因子遞減系數(shù)C的選擇，一般認為對算法的成敗影響不大。規(guī)定0<C<1。若C值選得較小，罰因子下降快，可以減少無約束優(yōu)化的次數(shù)，但因前后兩次無約束最優(yōu)點之間的距離較遠，有可能使后一次無約束優(yōu)化本身的迭代次數(shù)增多，而且使序列最優(yōu)點的間隔加大，對約束最優(yōu)點的逼近不利。相反，若C值取得較大，則無約束優(yōu)化次數(shù)就要增多。通常建議取C=0.1--0.5第17頁，共49頁。㈤終止準則隨著罰因子的值不斷減小，罰函數(shù)的序列無約束最優(yōu)點將越來越趨近于原約束優(yōu)化問題的最優(yōu)點。設懲罰函數(shù)的無約束最優(yōu)點列為對應的罰函數(shù)值為第18頁，共49頁。終止準則可用下述兩者之一⑴相鄰兩次懲罰函數(shù)無約束最優(yōu)點之間的距離已足夠的小。設ε1為收斂精度，一般取ε1=10-4-10-5，則需要滿足⑵相鄰兩次懲罰函數(shù)值的相對變化量已足夠小。設ε2為收斂精度，一般取ε2=10-3-10-4，則需要滿足第19頁，共49頁。㈥算法步驟⑴構(gòu)造內(nèi)點懲罰函數(shù)⑵選擇可行初始點，初始罰因子，罰因子降低系數(shù)C，收斂精度與，置k←0⑶求無約束優(yōu)化問題，有最優(yōu)點。⑷當k=0時轉(zhuǎn)步驟⑸，否則轉(zhuǎn)步驟⑹⑸置k←k+1，，并轉(zhuǎn)步驟⑶⑹由終止準則，若滿足則轉(zhuǎn)步驟⑺，否則轉(zhuǎn)⑸⑺,輸出最優(yōu)解(x*,F*)第20頁，共49頁。內(nèi)點法流程圖給定：x(0)∈D,r(0),C,ε1,ε2k←0K=0?入口用無約束優(yōu)化方法求罰函數(shù)的優(yōu)化點出口++--第21頁，共49頁。㈦內(nèi)點罰函數(shù)的特點內(nèi)點法只適用于解不等式約束優(yōu)化問題。由于內(nèi)點法需要在可行域內(nèi)部進行搜索，所以初始點必須在可行域內(nèi)部選取可行設計點。內(nèi)點法的突出優(yōu)點在于每個迭代點都是可行點因此，當?shù)_到一定階段時，盡管尚沒有達到最優(yōu)點，但也可以被接受為一個較好的近似解。第22頁，共49頁。5.3.4.2外點法外點法可以解不等式約束優(yōu)化問題或等式約束優(yōu)化問題㈠引例設有一維不等式優(yōu)化問題的數(shù)學模型用外點法構(gòu)造懲罰函數(shù)，具體構(gòu)造形式如下x≥bx<bS.T.:第23頁，共49頁。寫成另一種形式第24頁，共49頁。如上圖，此處的懲罰函數(shù)也是由原目標函數(shù)F(x)與懲罰項而組成。懲罰項中包含有可調(diào)整的參數(shù)r(k)與約束函數(shù)。由懲罰項的構(gòu)造可知，若迭代點在可行域的內(nèi)部，懲罰項的值為0，懲罰函數(shù)值與原目標函數(shù)值相等；而若在非可行域（即可行域的外部），懲罰項是以約束函數(shù)的平方加大的，即迭代點違反約束越嚴重，懲罰項的值增加的越大。因此，在非可行域內(nèi)，必有且罰因子r（k）越大，懲罰作用越明顯。由圖，對于某r(k)值，求出懲罰函數(shù)的最優(yōu)點當取罰因子為遞增數(shù)列，隨k的增加，罰函數(shù)的無約束最優(yōu)點序列為第25頁，共49頁。該序列將趨近與原約束問題的最優(yōu)點x*，x*=b。值得注意的是，盡管增加直至趨于無窮大，但最終的近似最優(yōu)點x*仍在可行域的外部。

即外點法構(gòu)造的罰函數(shù)是使迭代點從可行域的外部逐漸逼近約束最優(yōu)點，這正是外點法名稱的由來。第26頁，共49頁。㈡外點罰函數(shù)法的形式及特點先討論解不等式約束優(yōu)化問題設有不等式約束優(yōu)化問題u=1，2……，p構(gòu)造外點法懲罰函數(shù)的常見形式取正遞增S.T.:第27頁，共49頁。引入罰因子遞增系數(shù)C>1，并令=∞懲罰項的含義可用另一形式表示當gu(x)≥0（x∈D）當gu(x)<0（x∈D）在可行域內(nèi)（包括邊界）在非可行域，為遞增函數(shù)第28頁，共49頁。外點罰函數(shù)的求解過程用外點罰函數(shù)去逼近原目標函數(shù)F(x)，構(gòu)造一個無約束優(yōu)化問題模型x∈Rn任選初始點x(0)，初始法罰因子r(0)>0,罰因子遞增系數(shù)C>1對于r(k)為某一值，同過對懲罰函數(shù)的無約束求優(yōu)，可得最優(yōu)點。隨著k的增大，得無約束最優(yōu)點列第29頁，共49頁。在k←∞的過程中，點列將趨近于原問題的最優(yōu)點實線為原目標函數(shù)等值線虛線為罰函數(shù)等值線第30頁，共49頁?？偨Y(jié)由上圖可見，兩種等值線在可行域內(nèi)部及邊界上是重合的；而在非可行域中，罰函數(shù)的等值線升高了。即只有在可行域外部懲罰項才起到懲罰的作用。r(k)值越大，懲罰作用越大。由上b圖可知，在起作用約束邊界處罰函數(shù)等值線變得越密集和越陡峭。隨r(k)的增大，最優(yōu)點列將越接近于原約束優(yōu)化問題的最優(yōu)點x*。但須注意，近似的最優(yōu)點是落在邊界處非可行域一側(cè)。第31頁，共49頁。㈢對幾個問題的討論（1）初始點x(0)的選取在可行域及非可行域內(nèi)均可。（2）初始罰因子r(0)和遞增系數(shù)C的選取外點法中，這兩者的選擇對算法的成敗和計算速度有顯著的影響。第32頁，共49頁。選取過小，則序貫無約束求解的次數(shù)就增多，收斂速度慢；反之，則在非可行域中，發(fā)函數(shù)比原目標函數(shù)要大得多，特別在起作用約束邊界處產(chǎn)生尖點，函數(shù)性態(tài)變壞，從而限制了某些無約束優(yōu)化方法的使用，致使計算失敗。C的選取影響不大，通常C=5-10第33頁，共49頁。（3）約束容差帶最優(yōu)點在非可行域內(nèi)，是一個非可行點，這對某些工程是不允許的。因此，可在約束邊界可行域一側(cè)加一條容差帶。相當于將約束條件改為是容差量，通常第34頁，共49頁。㈣終止準則隨著罰因子的值不斷增大，罰函數(shù)的序列無約束最優(yōu)點將越來越趨近于原約束優(yōu)化問題的最優(yōu)點。設懲罰函數(shù)的無約束最優(yōu)點列為對應的罰函數(shù)值為第35頁，共49頁。終止準則可用下述兩者之一⑴相鄰兩次懲罰函數(shù)無約束最優(yōu)點之間的距離已足夠的小。設ε1為收斂精度，一般取ε1=10-4-10-5，則需要滿足⑵相鄰兩次懲罰函數(shù)值的相對變化量已足夠小。設ε2為收斂精度，一般取ε2=10-3-10-4，則需要滿足第36頁，共49頁。外點法流程圖給定：x(0)∈R,r(0),C,ε1,ε2k←0k=0?入口用無約束優(yōu)化方法求罰函數(shù)的優(yōu)化點出口++--㈣算法步驟與流程圖第37頁，共49頁。⑶求，得最優(yōu)點⑷當k=0時轉(zhuǎn)步驟⑸，否則轉(zhuǎn)步驟⑹⑸置k←k+1，，并轉(zhuǎn)步驟⑶⑹由終止準則，若滿足則轉(zhuǎn)步驟⑺，否則轉(zhuǎn)⑸⑺,輸出最優(yōu)解(x*,F*)，停止計算。算法步驟⑴在n維空間任取初始點x（0）⑵選取初始罰因子r(0),遞增系數(shù)C，并置k←0第38頁，共49頁。㈤用外點罰函數(shù)法解等式約束優(yōu)化問題設有二維約束優(yōu)化問題h1(x)=x1+x2-10=0如右圖，h1(x)為該約束問題的可行域，這條直線以外的整個x1ox2平面為非可行域。目標函數(shù)等值線與該直線的切點為最優(yōu)點最優(yōu)點S.T.:第39頁，共49頁。按外點法的基本思想，構(gòu)造懲罰函數(shù)x∈Dx∈D在可行域上，懲罰項的值為零，懲罰函數(shù)值與原目標函數(shù)值相同；在非可行域上，懲罰函數(shù)的值恒為正，罰函數(shù)大于原目標函數(shù)，即在可行域外懲罰項起到了懲罰作用。在k←∞的過程中，點列將趨近于原問題的最優(yōu)點對于m(k)，隨著k的增大，得無約束最優(yōu)點列第40頁，共49頁。推廣到具有一般的等式約束優(yōu)化問題首先構(gòu)造如下形式的外點懲罰函數(shù)懲罰因子m（k）規(guī)定取正，m(0)<m(1)<……。即罰因子遞增系數(shù)C>1在可行域上值為零，非可行域上，值恒大于零S.T.:第41頁，共49頁。5.3.4.3混合法用罰函數(shù)法解決有等式約束和不等式約束的一般約束（GP型）優(yōu)化問題的方法，把它稱為混合懲罰函數(shù)法，簡稱混合法。1混合法懲罰函數(shù)的形式及特點一般約束問題的優(yōu)化模型S.T.:第42頁，共49頁。用懲罰函數(shù)法將其轉(zhuǎn)化為無約束優(yōu)化問題懲罰函數(shù)是由原目標函數(shù)及包含約束函數(shù)的懲罰項組成。由于該問題的約束條件包