1、5.3.4 懲罰函數(shù)法,懲罰函數(shù)法簡介 內(nèi)點法 外點法 混合法 總結(jié),懲罰函數(shù)法簡介,懲罰函數(shù)法是一種使用很廣泛、很有效的間接法。,基本原理： 把約束優(yōu)化問題轉(zhuǎn)化成無約束優(yōu)化問題來求解。 兩個前提條件： 一是不破壞原約束的約束條件 二是最優(yōu)解必須歸結(jié)到原約束問題的最優(yōu)解上去,按照懲罰函數(shù)的構(gòu)成方式，懲罰函數(shù)法分為三種： 外點法、內(nèi)點法、混合法,懲罰項,r(k) 、m(k)-罰因子,懲罰函數(shù),5.3.4.1 內(nèi)點法,引例 設(shè)有一維不等式約束優(yōu)化問題的數(shù)學(xué)模型,S.T. :,由圖可見，目標函數(shù)的可行域為xb，在可行域內(nèi)目標函數(shù) 單調(diào)上升，它的最優(yōu)解顯然是,x*=b ，F(xiàn)*=ab,對引例的懲罰函數(shù)進

2、行分析，以對內(nèi)點法有初步認識：,本問題是不等式約束優(yōu)化問題，故只有一項懲罰項 ，一個罰因子,規(guī)定罰因子 為某一正數(shù)，當(dāng)?shù)c是在可行域內(nèi) 時，則懲罰項的值必為正值，因此必有,而且，當(dāng)x越趨近于約束邊界時，由于懲罰項,增大，所以罰函數(shù) 的值越大。當(dāng)xb時，罰函 數(shù)的值將趨近于+。因此，當(dāng)初始點取在可行域內(nèi)，求 函數(shù) 的極小值時，只要適當(dāng)控制搜索步長， 防止迭代點跨入非可行域，則所搜索到的無約束極小點 x*必可保持在可行域內(nèi)。,若對于罰因子的取值由初始的 逐漸變小 時，懲罰函數(shù) 愈逼近于原目標函數(shù)F（x），罰 函數(shù)曲線越來越接近于原F（x）=ax直線，如圖所示，對 應(yīng)罰函數(shù) 的最優(yōu)點列 不斷趨近于

3、原約 束優(yōu)化問題的最優(yōu)點x*=b,小結(jié),由以上可見，如果選擇一個可行點作初始點 ，令其罰因子 由大變小，通過求罰函數(shù) 的一系列最優(yōu)點， 顯見，無約束最優(yōu)點序列將逐漸趨近于原約束優(yōu)化問題的最優(yōu)點x*。,內(nèi)點罰數(shù)法的形式及特點,具有不等式約束的優(yōu)化問題的數(shù)學(xué)模型,u=1，2，p,構(gòu)造如下形式的內(nèi)點罰函數(shù),S.T. :,關(guān)于懲罰因子規(guī)定為正，即 。且在優(yōu)化過程中 是減小的，為確保為遞減數(shù)列，取常數(shù)C,0C1,稱系數(shù)C為罰因子降低系數(shù),=0,或,關(guān)于懲罰項 ，由于在可行域內(nèi)有 ， 且 永遠取正值，故在可行域內(nèi)懲罰項永為正。 的值越小則懲罰項的值越小。,由于在約束邊界上有 ，因此，當(dāng)設(shè)計點趨 于邊界時，

4、懲罰項的值將趨于無窮大。由此可知，在可 行域內(nèi)，始終有 。,當(dāng) 時 ，卻有 ，所以整個最 優(yōu)化的實質(zhì)就是用罰函數(shù) 去逼近原目標函數(shù)F(x); 當(dāng)設(shè)計點逐漸由內(nèi)部趨近于邊界時，由于懲罰項無窮 增大，則罰函數(shù)也將無窮增大。,從函數(shù)圖形上來看，猶如在可行域的邊界上筑起一 道陡峭的高墻，使迭代點自動保持在可行域內(nèi)，用此辦 法來保證搜索過程自始至終不離開可行域。所以，內(nèi)點法 也常稱為圍墻函數(shù)法。,內(nèi)點罰函數(shù)法的求解過程,為了用懲罰函數(shù) 去逼近原目標函數(shù)F(x)， 則要用F(x)及 構(gòu)造一個無約束優(yōu)化問題的數(shù)學(xué)模型,選取初始點（原約束優(yōu)化問題的內(nèi)點） ，初始罰 因子 ，罰因子降低系數(shù)C。用無約束優(yōu)化方法求

5、上式無 約束優(yōu)化問題的最優(yōu)解。,所得解為 ；當(dāng)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)成,初始點x(0)的選取,由于內(nèi)點法的搜索是在可行域內(nèi)進行，顯然初始點必須 是域內(nèi)可行點。須滿足,確定初始點常用如下兩種方法,自定法 即根據(jù)設(shè)計者的經(jīng)驗或已有的計算資料自行決 定某一可行點作為初始點。,搜索法 任選一個設(shè)計點 為初始點。通過對初始點 約束函數(shù)值的檢驗，按其對每個約束的不滿足程度加以調(diào) 整

6、，將 點逐步引入到可行域內(nèi)，成為可行初始點， 這就是搜索法。,關(guān)于幾個參數(shù)的選擇,初始罰因子r(0)的選取,如果 值選得太大，則在一開始罰函數(shù)的懲罰項的 值將遠遠超出原目標函數(shù)的值，因此，它的第一次無約束極 小點將遠離原問題的約束最優(yōu)點。在以后的迭代中，需要很 長時間的搜索才能使序列無約束極小點逐漸向約束最優(yōu)點逼近。,如果 值選得太小，則在一開始懲罰項的作用甚小， 而在可行域內(nèi)部懲罰函數(shù) 與原目標函數(shù)F(x)很相近， 只在約束邊界附近罰函數(shù)值才突然增高。這樣，使其罰函數(shù) 在在約束邊界附近出現(xiàn)深溝谷地，罰函數(shù)的性態(tài)變得惡劣。,如下圖，對于有深溝谷地性態(tài)差的函數(shù)，不僅搜索所需的 時間長，而且很難使

7、迭代點進入最優(yōu)的鄰域，以致極易使 迭代點落入非可行域而導(dǎo)致計算的失敗。,r（0）=150,或,遞減系數(shù)C的選擇,罰因子遞減系數(shù)C的選擇，一般認為對算法的成敗影響 不大。規(guī)定0C1。,若C值選得較小，罰因子下降快，可以減少無約束優(yōu)化 的次數(shù)，但因前后兩次無約束最優(yōu)點之間的距離較遠，有 可能使后一次無約束優(yōu)化本身的迭代次數(shù)增多，而且使序 列最優(yōu)點的間隔加大，對約束最優(yōu)點的逼近不利。,相反，若C值取得較大，則無約束優(yōu)化次數(shù)就要增多。,通常建議取C=0.1-0.5,終止準則,隨著罰因子 的值不斷減小，罰函數(shù)的序列無約 束最優(yōu)點將越來越趨近于原約束優(yōu)化問題的最優(yōu)點。,設(shè)懲罰函數(shù) 的無約束最優(yōu)點列為,對應(yīng)

8、的罰函數(shù)值為,終止準則可用下述兩者之一,相鄰兩次懲罰函數(shù)無約束最優(yōu)點之間的距離已足夠的小。,設(shè)1為收斂精度，一般取1=10-4-10-5，則需要滿足,相鄰兩次懲罰函數(shù)值的相對變化量已足夠小。,設(shè)2為收斂精度，一般取2=10-3-10-4，則需要滿足,算法步驟,構(gòu)造內(nèi)點懲罰函數(shù),選擇可行初始點 ，初始罰因子 ，罰因子降低系 數(shù)C，收斂精度 與 ，置k0,求無約束優(yōu)化問題， 有最優(yōu)點 。,當(dāng)k=0時轉(zhuǎn)步驟，否則轉(zhuǎn)步驟,置kk+1， ，并轉(zhuǎn)步驟,由終止準則，若滿足則轉(zhuǎn)步驟，否則轉(zhuǎn), , 輸出最優(yōu)解(x*,F*),內(nèi)點法流程圖,給定：x(0) D,r(0),C,1,2,k0,K=0?,入口,用無約束優(yōu)

9、化方法求罰函數(shù) 的優(yōu)化點,出口,+,+,-,-,內(nèi)點罰函數(shù)的特點,內(nèi)點法只適用于解不等式約束優(yōu)化問題。由于內(nèi)點法 需要在可行域內(nèi)部進行搜索，所以初始點必須在可行域 內(nèi)部選取可行設(shè)計點。,內(nèi)點法的突出優(yōu)點在于每個迭代點都是可行點,因此，當(dāng)?shù)_到一定階段時，盡管尚沒有達到最優(yōu)點， 但也可以被接受為一個較好的近似解。,5.3.4.2 外點法,外點法可以解不等式約束優(yōu)化問題或等式約束優(yōu)化問題,引例 設(shè)有一維不等式優(yōu)化問題的數(shù)學(xué)模型,用外點法構(gòu)造懲罰函數(shù)，具體構(gòu)造形式如下,xb,xb,S.T. :,寫成另一種形式,如上圖，此處的懲罰函數(shù)也是由原目標函數(shù)F(x)與懲罰 項而組成。懲罰項中包含有可調(diào)整的參

10、數(shù)r(k)與約束函數(shù)。,由懲罰項的構(gòu)造可知，若迭代點在可行域的內(nèi)部，懲罰 項的值為0，懲罰函數(shù)值與原目標函數(shù)值相等；而若在非可 行域（即可行域的外部），懲罰項是以約束函數(shù)的平方加 大的，即迭代點違反約束越嚴重，懲罰項的值增加的越大。 因此，在非可行域內(nèi)，必有 且罰因子r（k）越 大，懲罰作用越明顯。,由圖，對于某r(k)值，求出懲罰函數(shù) 的最優(yōu)點 當(dāng)取罰因子 為遞增數(shù)列，隨k的增加，罰函數(shù)的無約束最 優(yōu)點序列為,該序列將趨近與原約束問題的最優(yōu)點x*，x*=b。 值得注意的是，盡管 增加直至趨于無窮大，但最終 的近似最優(yōu)點x*仍在可行域的外部。 即外點法構(gòu)造的罰函數(shù)是使迭代點從可行域的外部逐 漸

11、逼近約束最優(yōu)點，這正是外點法名稱的由來。,外點罰函數(shù)法的形式及特點,先討論解不等式約束優(yōu)化問題,設(shè)有不等式約束優(yōu)化問題,u=1，2，p,構(gòu)造外點法懲罰函數(shù)的常見形式,取正遞增,S.T. :,引入罰因子遞增系數(shù)C1，并令,=,懲罰項,的含義可用另一形式表示,當(dāng)gu(x) 0 （xD）,當(dāng)gu(x) 0 （xD）,在可行域內(nèi) （包括邊界）,在非可行域， 為遞增函數(shù),外點罰函數(shù)的求解過程,用外點罰函數(shù)去逼近原目標函數(shù)F(x)，構(gòu)造一個無約束 優(yōu)化問題模型,xRn,任選初始點x(0)，初始法罰因子r(0)0,罰因子遞增系數(shù)C1,對于r(k)為某一值，同過對懲罰函數(shù)的無約束求優(yōu)，可 得最優(yōu)點 。隨著k的

12、增大，得無約束最優(yōu)點列,在k的過程中，點列將趨近于原問題的最優(yōu)點,實線為原目標 函數(shù)等值線,虛線為罰函數(shù) 等值線,總結(jié),由上圖可見，兩種等值線在可行域內(nèi)部及邊界上是重合 的；而在非可行域中，罰函數(shù)的等值線升高了。即只有在 可行域外部懲罰項才起到懲罰的作用。r(k)值越大，懲罰作 用越大。,由上b圖可知，在起作用約束邊界處罰函數(shù)等值線變得越 密集和越陡峭。隨r(k)的增大，最優(yōu)點列將越接近于原約束 優(yōu)化問題的最優(yōu)點x*。但須注意，近似的最優(yōu)點是落在邊 界處非可行域一側(cè)。,對幾個問題的討論,（1）初始點x(0)的選取,在可行域及非可行域內(nèi)均可。,（2）初始罰因子r(0)和遞增系數(shù)C的選取,外點法中

13、，這兩者的選擇對算法的成敗和計算速度有顯著 的影響。,選取過小，則序貫無約束求解的次數(shù)就增多，收斂速度慢；反之，則在非可行域中，發(fā)函數(shù)比原目標函數(shù)要大得多，特別在起作用約束邊界處產(chǎn)生尖點，函數(shù)性態(tài)變壞，從而限制了某些無約束優(yōu)化方法的使用，致使計算失 敗。,C的選取影響不大，通 常C=5-10,（3）約束容差帶,最優(yōu)點在非可行域內(nèi)，是一個非可行點，這對某些工 程是不允許的。因此，可在約束邊界可行域一側(cè)加一條容 差帶。,相當(dāng)于將約束條件改為,是容差量，通常,終止準則,隨著罰因子 的值不斷增大，罰函數(shù)的序列無約束最 優(yōu)點將越來越趨近于原約束優(yōu)化問題的最優(yōu)點。,設(shè)懲罰函數(shù) 的無約束最優(yōu)點列為,對應(yīng)的罰

14、函數(shù)值為,終止準則可用下述兩者之一,相鄰兩次懲罰函數(shù)無約束最優(yōu)點之間的距離已足夠的小。,設(shè)1為收斂精度，一般取1=10-4-10-5，則需要滿足,相鄰兩次懲罰函數(shù)值的相對變化量已足夠小。,設(shè)2為收斂精度，一般取2=10-3-10-4，則需要滿足,外點法流程圖,給定：x(0) R ,r(0),C,1,2,k0,k=0?,入口,用無約束優(yōu)化方法求罰函數(shù) 的優(yōu)化點,出口,+,+,-,-,算法步驟與流程圖,求 ，得最優(yōu)點,當(dāng)k=0時轉(zhuǎn)步驟，否則轉(zhuǎn)步驟,置kk+1， ，并轉(zhuǎn)步驟,由終止準則，若滿足則轉(zhuǎn)步驟，否則轉(zhuǎn), , 輸出最優(yōu)解(x*,F*)，停止計算。,算法步驟,在n維空間任取初始點x（0）,選取初

15、始罰因子r(0),遞增系數(shù)C，并置k0,用外點罰函數(shù)法解等式約束優(yōu)化問題,設(shè)有二維約束優(yōu)化問題,h1(x)=x1+x2-10=0,如右圖，h1(x)為該約束 問題的可行域，這條直線以 外的整個x1ox2平面為非可 行域。目標函數(shù)等值線與該 直線的切點為最優(yōu)點,最優(yōu)點,S.T. :,按外點法的基本思想，構(gòu)造懲罰函數(shù),xD,xD,在可行域上，懲罰項的值為零，懲罰函數(shù)值與原目標函數(shù) 值相同；在非可行域上，懲罰函數(shù)的值恒為正，罰函數(shù)大于 原目標函數(shù)，即在可行域外懲罰項起到了懲罰作用。,在k的過程中，點列將趨近于原問題的最優(yōu)點,對于m(k)，隨著k的增大，得無約束最優(yōu)點列,推廣到具有一般的等式約束優(yōu)化問

16、題,首先構(gòu)造如下形式的外點懲罰函數(shù),懲罰因子m（k）規(guī)定取正，m(0)1,在可行域上值為零，非可行域上，值恒大于零,S.T. :,5.3.4.3 混合法,用罰函數(shù)法解決有等式約束和不等式約束的一般約束 （GP型）優(yōu)化問題的方法，把它稱為混合懲罰函數(shù)法， 簡稱混合法。,1 混合法懲罰函數(shù)的形式及特點,一般約束問題的優(yōu)化模型,S.T. :,用懲罰函數(shù)法將其轉(zhuǎn)化為無約束優(yōu)化問題,懲罰函數(shù)是由原目標函數(shù)及包含約束函數(shù)的懲罰項組 成。由于該問題的約束條件包含不等式約束與等式約束 兩部分。因此，懲罰項也應(yīng)由對應(yīng)的兩部分組成。對應(yīng) 等式約束部分的只有外點法一種形式，而對應(yīng)不等式 的約束部分有內(nèi)點法或外點法兩

17、種形式。因此按照對不 等式約束處理的方法不同，混合法懲罰函數(shù)也具有兩種 形式。,內(nèi)點形式的混合法,不等式約束部分按內(nèi)點法形式處理的混合法，懲罰函數(shù) 形式為,是遞增序列,為了統(tǒng)一用一個罰因子r（k），且又按內(nèi)點法形式，即,0C1,上式可寫為,外點形式的混合法,不等式約束部分按外點法形式處理的混合法，懲罰函數(shù) 形式為,其中，罰因子r(k)恒為正，且為遞增序列，即,遞增系數(shù)C1,初始點可在Rn空間內(nèi)任選，初始罰因子及遞增系數(shù)參照 外點法選取。,2 算法步驟及流程圖,參照內(nèi)點法與外點法。（外點法，內(nèi)點法）,例題,設(shè)有二維一般約束優(yōu)化問題，數(shù)學(xué)模型為,S.T. :,目標函數(shù)等值線及約束曲線見下圖。,最優(yōu)點x*既要在不等式 約束包括的范圍內(nèi)，同時 又必須在等式約束 h(x)=0 的直線上，試求該約束優(yōu)化