第三章罰函數(shù)法及改進(jìn)算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第3章 罰函數(shù)法及改進(jìn)算法3.1 引言罰函數(shù)法是解決約束優(yōu)化問題的重要方法，它的基本思想是用無約束問題代替約束問題，因而無約束問題的目標(biāo)函數(shù)必須是原來的目標(biāo)函數(shù)與約束函數(shù)的某種組合，類似線性規(guī)劃中的M法求初始可行解，在原來的目標(biāo)函數(shù)上加上由約束函數(shù)組成的一個(gè)“懲罰項(xiàng)”來迫使迭代點(diǎn)逼近可行域，所以稱為罰函數(shù)法。這樣把約束問題轉(zhuǎn)化成求解一系列的無約束極小點(diǎn)，通過有關(guān)的無約束問題來研究約束極值問題，從而使問題變的簡(jiǎn)單。許多非線性約束優(yōu)化方法都要用罰函數(shù)作為評(píng)價(jià)函數(shù)來評(píng)價(jià)一個(gè)點(diǎn)的好壞，這在選擇新點(diǎn)確定步長(zhǎng)等方面都起著重要的作用，不同的罰項(xiàng)對(duì)算法影響很大，根據(jù)罰項(xiàng)的不同可以分為

2、以下幾類：外罰函數(shù)法對(duì)于問題 (3-1) (3-2) (3-3)其中為線性連續(xù)函數(shù)。定義外罰函數(shù)為: (3-4) (3-5)通常取，這樣定義的外罰函數(shù)法，當(dāng)為可行點(diǎn)是，；當(dāng)不是可行點(diǎn)時(shí)，。而且離可行域越遠(yuǎn)的值越大，它優(yōu)點(diǎn)是允許從可行域的外部逐步逼近最優(yōu)點(diǎn)，但其明顯的缺點(diǎn)是它需要求解一系列無約束極小化問題，計(jì)算工作量很大，且由于其收斂速度僅是線性的，往往需要較長(zhǎng)的時(shí)間才能找到問題的近似解，再考慮到實(shí)際中所使用的終止準(zhǔn)則，若實(shí)現(xiàn)不當(dāng)，則算法很難找到約束問題的一個(gè)較好可行解，從而不適用于那些要求嚴(yán)格可行性的問題。內(nèi)罰函數(shù)法它是針對(duì)不等式約束(3-1)(3-3)提出的，基本思想是在約束區(qū)域的邊界筑起一

3、道“墻”來，當(dāng)?shù)c(diǎn)靠近邊界時(shí)，函數(shù)值陡然增大，于是最優(yōu)點(diǎn)被擋在可行域內(nèi)部，這樣產(chǎn)生的點(diǎn)列每個(gè)點(diǎn)都是可行點(diǎn)。通常定義內(nèi)罰函數(shù)為： (3-6) (3-7)要減弱的影響，故令逐漸增大。內(nèi)罰函數(shù)法的好處是每次迭代的點(diǎn)都是可行點(diǎn)，當(dāng)?shù)揭欢A段時(shí)，可以被接受為一個(gè)較好的近似最優(yōu)解。但是內(nèi)點(diǎn)罰函數(shù)法要求初始點(diǎn)位于可行域的內(nèi)部，除特殊情況外，確定這樣一個(gè)初始點(diǎn)并非易事。此外，由于內(nèi)點(diǎn)罰函數(shù)不是處處有定義或不一定存在全局極小，故無約束最優(yōu)化問題中的線性搜索方法不再適用，另外，當(dāng)接近可行域邊界時(shí)，內(nèi)點(diǎn)罰函數(shù)法必須修正通常的線性搜索方法。 由于內(nèi)點(diǎn)罰函數(shù)法不能處理等式約束，且尋求初始可行點(diǎn)的計(jì)算工作量往往太大

4、。因此，在實(shí)際中，為了求解一般的非線性約束優(yōu)化問題，人們往往將內(nèi)點(diǎn)罰函數(shù)法與外點(diǎn)罰函數(shù)法結(jié)合起來適用?；旌狭P函數(shù)法混合罰函數(shù)法是針對(duì)問題(3-1)-(3-3)提出來的，當(dāng)初始點(diǎn)給定后，對(duì)等式約束和不被滿足的那些不等式約束用外罰函數(shù)法，而被滿足的那些不等式約束用內(nèi)罰函數(shù)法。通常定義混合罰函數(shù)為：(3-8) (3-9)精確罰函數(shù)法對(duì)于外點(diǎn)罰函數(shù)法和內(nèi)點(diǎn)罰函數(shù)法來說，其工作量很大，收斂慢的主要原因是它們需要求解一系列的無約束優(yōu)化問題，而導(dǎo)致相應(yīng)罰函數(shù)的無約束極小化運(yùn)算越來越難于精確執(zhí)行，效率差則是因?yàn)樾枰P因子趨于無窮大或零所帶來的罰函數(shù)呈病態(tài)問題。由此自然想到，能否設(shè)計(jì)出一種罰函數(shù)，使得只要令其中

5、的罰參數(shù)取適當(dāng)?shù)挠邢拗岛?，該罰函數(shù)的無約束極小點(diǎn)就恰好是原約束問題的最優(yōu)解，從而克服外、內(nèi)點(diǎn)罰函數(shù)法的缺點(diǎn)呢？通常稱這樣的罰函數(shù)為精確罰函數(shù)。對(duì)問題(3-1)-(3-3)，定義如下，對(duì)于罰函數(shù)其中是罰因子。如果則在二階充分條件，的假定下可證是罰函數(shù)的局部嚴(yán)格極小點(diǎn)。所以罰函數(shù)也常稱為精確罰函數(shù)。同理，罰函數(shù)也是精確罰函數(shù)。乘子罰函數(shù)法內(nèi)外罰函數(shù)法的缺點(diǎn)是需要罰因子趨于無窮大才能使求解罰函數(shù)的極小和求解原向題等價(jià)。乘子罰函數(shù)法具有不要求初始點(diǎn)為嚴(yán)格內(nèi)點(diǎn)，甚至不要求其為可行點(diǎn)的特點(diǎn)，它利用近似Lagrange乘子，求其近似解，并且逼近最優(yōu)解，而不需要無窮大的罰因子，因此對(duì)它的研究有重要的理論和實(shí)用

6、價(jià)值。最早的乘子罰函數(shù)(又稱為增廣Lagrange函數(shù))是由Henstenes(1969)針對(duì)等式約束問題(3-1)(3-2)導(dǎo)出的，其形式為: (3-10)增廣Lagrange函數(shù)的另一種等價(jià)形式是在1969年由Powell提出的，它提出對(duì)進(jìn)行平移，即用代替，是參數(shù)，這種平移的好處是不破壞的方向，由此Powell(1969)得到罰函數(shù): (3-11)如果定義，則知式(3-10)與(3-11)只相差與無關(guān)的項(xiàng)，由于式(3-10)與(3-11)等價(jià)，故罰函數(shù)(3-10)也稱為Henstenes-Powell罰函數(shù)。我們看到通常都是用二次罰函數(shù)作為罰項(xiàng)，因此稱之為二次罰函數(shù)乘子法。然而，它的缺點(diǎn)是

7、容易引起罰因子過大，造成罰函數(shù)的Hesse矩陣嚴(yán)重病態(tài)。許多非線性約束優(yōu)化方法都要用某個(gè)罰函數(shù)作為評(píng)價(jià)函數(shù)來評(píng)價(jià)一個(gè)點(diǎn)的好壞，這在選擇新點(diǎn)確定步長(zhǎng)等方面都起著重要的作用，因此對(duì)不同罰項(xiàng)的研究具有重要的理論和實(shí)際價(jià)值。近年來，許多研究者試圖通過改變罰項(xiàng)構(gòu)造出新的罰函數(shù)，有效地避免罰因子過大引起的罰函數(shù)的Hesse矩陣嚴(yán)重病態(tài)的情況。3.2 優(yōu)化中的罰函數(shù)法對(duì)一般約束最優(yōu)化問題 (3-12) (3-13) (3-14)定義1 稱 (3-15)為問題(3-12)-(3-14)的優(yōu)化罰函數(shù)，為罰因子，其中罰項(xiàng) (3-16)其中且滿足如下性質(zhì)：(1) 在中連續(xù)可微且為對(duì)稱凸函數(shù)；(2) 對(duì)，；當(dāng)且僅當(dāng)時(shí)

8、，；(3) ，。若定義 則是可行點(diǎn)當(dāng)且僅當(dāng)。我們通過的極小點(diǎn)(其中為一定值)，得到相應(yīng)無約束極小點(diǎn)，序列來逼近約束問題(3-12)-(3-14)的極小點(diǎn)。罰函數(shù)算法：步1 選定初始點(diǎn)為；選取初始懲罰因子(可取)，懲罰因子的放大系數(shù)(可取)；置。步2 以為初始點(diǎn)，求解無約束問題，其中，設(shè)其極小點(diǎn)為。步3 若，則就是所要求的最優(yōu)解，停止；否則轉(zhuǎn)下一步。步4 置；，轉(zhuǎn)步2。由罰項(xiàng)的特點(diǎn)，當(dāng)趨向于無窮時(shí)，隨著的不斷增大，對(duì)每個(gè)不可行點(diǎn)的懲罰也不斷增大并趨向于無窮。因此，在對(duì)應(yīng)于的無約束極小化問題的最優(yōu)解處，的值應(yīng)不斷減小，從而保證逐步趨于可行并最終達(dá)到問題(3-12)-(3-14)的最優(yōu)解。由，的定義

9、及極小點(diǎn)的含義，我們很容易證明下列結(jié)論。引理1 給定，是(3-15)的解，則也是約束問題 (3-17) (3-18)的解，其中。證明 由的性質(zhì)知在是增函數(shù)，且 ，又因?yàn)闉閷?duì)稱函數(shù)，所以，由此可得對(duì)任何滿足式(3-18)，由的定義，我們有 (3-19)所以 (3-20)故知是問題(3-17)-(3-18)的解。證畢。 由以上引理可知，若取充分小，則當(dāng)算法迭代結(jié)束時(shí)，是問題(3-12)- (3-14)的近似解。引理2 對(duì)于由算法所產(chǎn)生的序列總有， (3-21) (3-22) (3-23)其中。證明 由和可知，又因?yàn)槭堑臉O小點(diǎn)，所以對(duì)于任意總有，特別有。由此可證得(3-21)。因?yàn)楹头謩e使和取極小，

10、所以有由上式可得由此可得由于，所以(3-22)成立。最后，由式(3-21)和(3-22)得式(3-23)成立。證畢。定理1 設(shè)非線性約束問題(3-12)-(3-14)的最優(yōu)解存在，設(shè)由算法產(chǎn)生，且罰參數(shù)序列單調(diào)遞增且趨于，則的任何極限點(diǎn)都是問題(3-12)-(3-14)的可行域上的最優(yōu)解。證明 設(shè)，又設(shè)是問題(3-12)-(3-14)的最優(yōu)解，由于是無約束問題 的解，由于可行，即，故有即由此可得，由于，。故得，且。即可行，且，但是問題(3-12)-(3-14)的解，因此也是問題(3-12)-(3-14)的解。 證畢。 我們現(xiàn)在對(duì)于優(yōu)化中的罰函數(shù)法進(jìn)行一般類型的概況，并證明其收斂性，但是需要說明

11、的是其中不同種類的罰函數(shù)法在其收斂速度各有其不同。3.3 改進(jìn)的罰函數(shù)法及收斂性3.3.1 改進(jìn)的罰函數(shù)算法罰函數(shù)法是解決約束優(yōu)化問題的重要方法，它的基本思想是把約束優(yōu)化問題轉(zhuǎn)化成求解一系列的無約束極小化問題。通過有關(guān)的無約束問題來研究約束極值問題，經(jīng)常采用的方法之一是在原來的目標(biāo)函數(shù)上加上由約束函數(shù)組成的一個(gè)“懲罰項(xiàng)”來迫使迭代點(diǎn)逼近可行域，這種方法稱為罰函數(shù)法。如何選取罰函數(shù)，以加速迭代算法的收斂速度，一直是約束優(yōu)化問題研究的熱點(diǎn)問題。罰函數(shù)作為評(píng)價(jià)函數(shù)來評(píng)價(jià)一個(gè)點(diǎn)的好壞，這在選擇新點(diǎn)確定步長(zhǎng)等方面都起著重要作用，不同罰項(xiàng)的選取，構(gòu)成不同的罰函數(shù)，必然會(huì)對(duì)算法產(chǎn)生不同的影響，因此對(duì)不同罰項(xiàng)

12、的研究具有重要的理論和實(shí)用價(jià)值。對(duì)一般約束最優(yōu)化問題 (3-24) (3-25) (3-26)通常使用的外函數(shù)形式為：其中罰項(xiàng)為：，。為參數(shù)，若取，我們稱上述罰函數(shù)為二次罰函數(shù)。問題(3-24)-(3-26)的可行域?yàn)轱@然，當(dāng)為可行點(diǎn)時(shí)，；當(dāng)不是可行點(diǎn)時(shí)，而且離可行域越遠(yuǎn)的值越大。它的優(yōu)點(diǎn)是允許從可行域的外部逐步逼近逼近最優(yōu)點(diǎn)，但按上述定義的罰函數(shù)的缺點(diǎn)是：需要罰因子趨于無窮大，才可能使求解罰函數(shù)的極小和求解原問題等價(jià)。為了有效的改善這種罰函數(shù)，我們?cè)噲D構(gòu)造一種能夠加速迭代算法收斂的外罰函數(shù)法。本文提出一種用雙曲正弦函數(shù)作罰項(xiàng)的罰函數(shù)，并由此構(gòu)建了雙曲正弦罰函數(shù)法，不僅證明了該罰函數(shù)和算法的合

13、理性及迭代點(diǎn)列的收斂性，而且做了數(shù)值實(shí)驗(yàn)。結(jié)果表明本文中所提出的罰函數(shù)及對(duì)應(yīng)的算法可以在罰因子與二次罰函數(shù)方法中的罰因子相同的情況下，有著更快的收斂速度。定義1 稱 (3-27)為問題(3-24)-(3-26)的雙曲正弦罰函數(shù)，為罰因子，其中罰項(xiàng) (3-28)其中，；，。若定義 則是可行點(diǎn)當(dāng)且僅當(dāng)。我們通過一系列雙曲正弦函數(shù)的極小點(diǎn)，其中為一定值，得到相應(yīng)無約束極小點(diǎn)，序列來逼近約束問題(3-24)-(3-26)的極小點(diǎn)。雙曲正弦罰函數(shù)算法：步1 選定初始點(diǎn)為；選取初始懲罰因子(可取)，懲罰因子的放大系數(shù)(可取)；置。步2 以為初始點(diǎn)，求解無約束問題其中設(shè)其極小點(diǎn)為。步3 若，則就是所要求的最

14、優(yōu)解，停止；否則轉(zhuǎn)下一步。步4 置；，轉(zhuǎn)步2。3.3.2 收斂性證明及數(shù)值試驗(yàn)引理1 設(shè)函數(shù)和由定義1定義，由算法產(chǎn)生，且罰參數(shù)序列單調(diào)遞增，則 證明 由的定義知上面的兩式相加，得因此，即成立。 由得即成立。 由以及的定義得即成立。 證畢。引理2 設(shè)函數(shù)和由定義1定義，由算法產(chǎn)生，且罰參數(shù)序列單調(diào)遞增，記，則也是約束問題 (3-29) 的解。證明 設(shè)是問題(3-29)的可行點(diǎn)，我們有因此是問題(3-29)的解。 證畢。定理1 設(shè)非線性約束問題(3-24)-(3-26)的最優(yōu)解存在，設(shè)由算法產(chǎn)生，且罰參數(shù)序列單調(diào)遞增且趨于，則的任何極限點(diǎn)都是問題(3-24)-(3-26)的可行域上的最優(yōu)解。證明

15、 設(shè)，又設(shè)是問題(3-24)-(3-26)的最優(yōu)解，由于是無約束問題，的解，由于可行，即，故有即由此可得，由于，。故得，且。即可行，且，但是問題(3-24)-(3-26)的解，因此也是問題(3-24)-(3-26)的解。證畢。我們通過數(shù)值實(shí)驗(yàn)來檢驗(yàn)本算法的有效性 在以下“次數(shù)”的是求解相應(yīng)無約束問題的次數(shù)，“”和“”分別表示雙曲正弦罰函數(shù)法和二次罰函數(shù)法。是程序結(jié)束時(shí)所取罰因子，用matlab編程實(shí)現(xiàn)。表3-1 兩種方法的數(shù)值比較：Table 3-1 the numerical comparison of the two methods方法初始點(diǎn)算法中罰因子次數(shù)最優(yōu)解(-1,1)201(0.2500,0.7500)36(0.2499,0.7501)(-5,10)203(0.2500,0.7500)34(0.2500,0.7500)(10,1,-5)247(-0.4999,-0.5004,-0.4999)244(-0.5000,-0.5001,-0.5001)(0,0,-1