07第三章罰函數(shù)法及改進算法

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

2、inf(x)(3-1)s.tc(x)=0i=1,2,m;(3-2)ic(x)>0i=m+1,m+2,n;(3-3)i其中f:RnTR為線性連續(xù)函數(shù)。定義外罰函數(shù)為:L(x,b)=f(x)+P(x)=f(x)+bQ(x)(3-4)Q(x)=E|c(x)|卩+工|min0,c(x)|a(3-5)iii=1i=m+1通常取a=B=2，這樣定義的外罰函數(shù)法，當x為可行點是，Q(x)=0；當x不是可行點時，Q(x)>0。而且x離可行域越遠Q(x)的值越大，它優(yōu)點是允許從可行域的外部逐步逼近最優(yōu)點，但其明顯的缺點是它需要求解一系列無約束極小化問題，計算工作量很大，且由于其收斂速度僅是線性的，往

3、往需要較長的時間才能找到問題的近似解，再考慮到實際中所使用的終止準則，若實現(xiàn)不當，則算法很難找到約束問題的一個較好可行解，從而不適用于那些要求嚴格可行性的問題。內(nèi)罰函數(shù)法它是針對不等式約束(3-1)(3-3)提出的，基本思想是在約束區(qū)域的邊界筑起一道“墻”來，當?shù)c靠近邊界時，函數(shù)值陡然增大，于是最優(yōu)點被擋在可行域內(nèi)部，這樣產(chǎn)生的點列x每個點都是可行點。通常定義內(nèi)罰函數(shù)為：kB(xQ)=f(x)+B(x)(3-6)(3-7)B(x)=£i=1要減弱B(x)的影響，故令b逐漸增大。內(nèi)罰函數(shù)法的好處是每次迭代的點都是可行點，當?shù)揭欢A段時，可以被接受為一個較好的近似最優(yōu)解。但是內(nèi)點

4、罰函數(shù)法要求初始點位于可行域的內(nèi)部，除特殊情況外，確定這樣一個初始點并非易事。此外，由于內(nèi)點罰函數(shù)不是處處有定義或不一定存在全局極小，故無約束最優(yōu)化問題中的線性搜索方法不再適用，另外，當接近可行域邊界時，內(nèi)點罰函數(shù)法必須修正通常的線性搜索方法。由于內(nèi)點罰函數(shù)法不能處理等式約束，且尋求初始可行點的計算工作量往往太大。因此，在實際中，為了求解一般的非線性約束優(yōu)化問題，人們往往將內(nèi)點罰函數(shù)法與外點罰函數(shù)法結(jié)合起來適用?；旌狭P函數(shù)法混合罰函數(shù)法是針對問題(3-1)-(3-3)提出來的，當初始點x給定后，對0等式約束和不被x滿足的那些不等式約束用外罰函數(shù)法，而被x滿足的那00些不等式約束用內(nèi)罰函數(shù)法。通

5、常定義混合罰函數(shù)為：11P(xQ)=f(x)+£()+bP(x)(3-8)bc(x)比1iP(x)=Qc(x)|2+工|min0,c(x)2(3-9)iii=1沱I=ic(x)>0,i=m+1,m+2,n1 iI=ic(x)<0,i=m+1,m+2,n2 i精確罰函數(shù)法對于外點罰函數(shù)法和內(nèi)點罰函數(shù)法來說，其工作量很大，收斂慢的主要原因是它們需要求解一系列的無約束優(yōu)化問題，而導致相應(yīng)罰函數(shù)的無約束極小化運算越來越難于精確執(zhí)行效，率差則是因為需要罰因子趨于無窮大或零所帶來的罰函數(shù)呈病態(tài)問題。由此自然想到，能否設(shè)計出一種罰函數(shù)，使得只要令其中的罰參數(shù)取適當?shù)挠邢拗岛?，該罰函數(shù)的

6、無約束極小點就恰好是原約束問題的最優(yōu)解，從而克服外、內(nèi)點罰函數(shù)法的缺點呢？通常稱這樣的罰函數(shù)為精確罰函數(shù)。對問題(3-1)-(3-3)，定義C(-)(x)=(c(-)(x),c(-)(x)t如下1mc(-)(x)=c(x)，i=1,2,:,mii.c(-)(x)=min0,c(x)，i=m+1,m+2,nii對于L罰函數(shù)1P(x)=f(x)+b|C(-)(x)|11其中b>0是罰因子。如果Q>則在二階充分條件dTW*d>0，Vd豐0，A*Td=0的假定下可證x*是L罰函數(shù)的局部嚴格極小點。所以L罰函數(shù)也常稱為L111精確罰函數(shù)。同理，L罰函數(shù)P(x)=f(x)+bg1IC(-

7、)(x)|也是精確罰函數(shù)。乘子罰函數(shù)法內(nèi)外罰函數(shù)法的缺點是需要罰因子趨于無窮大才能使求解罰函數(shù)的極小和求解原向題等價。乘子罰函數(shù)法具有不要求初始點為嚴格內(nèi)點，甚至不要求其為可行點的特點，它利用近似Lagrange乘子，求其近似解，并且逼近最優(yōu)解，而不需要無窮大的罰因子，因此對它的研究有重要的理論和實用價值。最早的乘子罰函數(shù)(又稱為增廣Lagrange函數(shù))是由Henstenes(1969)針對等式約束問題(3-1)(3-2)導出的，其形式為:P(x,九Q)=f(x)一九Tc(x)+2|c(x)|F(3-10)增廣Lagrange函數(shù)的另一種等價形式是在1969年由Powell提出的，它提出對c

8、(x)進行平移，即用c(x)-9代替c(x)，9是參數(shù)，這種平移的好處是iiiii不破壞Vc(x)的方向，由此Powell(1969)得到罰函數(shù)：iP(x,九q)=f(x)一九tc(x)+£(c(x)-9)2(3-11)2iii=1如果定義九"9，則知式(3-10)與(3-11)只相差與x無關(guān)的項-m92，ii2ii=1由于式(3-10)與(3-11)等價，故罰函數(shù)(3-10)也稱為Henstenes-Powell罰函數(shù)。我們看到通常都是用二次罰函數(shù)作為罰項，因此稱之為二次罰函數(shù)乘子法。然而，它的缺點是容易引起罰因子過大，造成罰函數(shù)的Hesse矩陣嚴重病態(tài)。許多非線性約束優(yōu)

9、化方法都要用某個罰函數(shù)作為評價函數(shù)來評價一個點的好壞，這在選擇新點確定步長等方面都起著重要的作用，因此對不同罰項的研究具有重要的理論和實際價值。近年來，許多研究者試圖通過改變罰項構(gòu)造出新的罰函數(shù)，有效地避免罰因子過大引起的罰函數(shù)的Hesse矩陣嚴重病態(tài)的情況。3.2優(yōu)化中的罰函數(shù)法對一般約束最優(yōu)化問題(3-12)minf(x)s.tc(x)=0i=1,2,m,;(3-13)ic(x)>0i=m+1,m+2,-n；(3-14)i定義1稱L(xQ)=f(x)+P(x)=f(x)+oQ(x)(3-15)kkk為問題(3-12)-(3-14)的優(yōu)化罰函數(shù)，a>0為罰因子，其中罰項Q(x)=

10、區(qū)q(c(x)+工q(min0,c(x)(3-16)iii=1i=m+1q(t)其中teR且滿足如下性質(zhì)：(1) q(t)在R中連續(xù)可微且為對稱凸函數(shù)；(2) 對VteR，q(t)>0；當且僅當t=0時，q(t)=0；(3)limq(t)=，limq(t)=一。tT+8tT8若定義ci(x)=i=1,2,m,i=m+1,m+2,n,c(x)imin0,c(x)i則x是可行點當且僅當c(x)=0。i我們通過L(x,a)的極小點(其中ak為一定值)，得到相應(yīng)無約束極小點,序列x來逼近約束問題(3-12)-(3-14)的極小點x*。k罰函數(shù)算法：步1選定初始點為x；選取初始懲罰因子a>0

11、(可取a=1),懲罰因011子的放大系數(shù)c>1(可取c=10)；置k=1。步2xk-1為初始點,求解無約束問題minL(x,axeRnk)其中L(x,a)=f(x)+P(x)=f(x)+aQ(x)，設(shè)其極小點為x。kGkkk步3若aQ(x)<£,則x就是所要求的最優(yōu)解，停止；否則轉(zhuǎn)下一步。kk步4置a=ca；k=k+1，轉(zhuǎn)步2。k+1k由罰項的特點，當k趨向于無窮時，隨著a的不斷增大，對每個不可行k點的懲罰aQ(x)也不斷增大并趨向于無窮。因此，在對應(yīng)于a的無約束極kk小化問題的最優(yōu)解x處，aQ(x)的值應(yīng)不斷減小，從而保證x逐步趨于可kkk行并最終達到問題(3-12)-

12、(3-14)的最優(yōu)解。由Q(x),L(x,a)的定義及極小k點的含義，我們很容易證明下列結(jié)論。引理1給定a>0,x是(3-15)的解，則x也是約束問題kkkminf(x)(3-17)xeRns.tIc(x)l<i=1,2,n,(3-18)ii的解，其中卩=IC.(x)1。iik證明由q(x)的性質(zhì)知在(0,+Q是增函數(shù)，且q(Ic(x)I)>q(IC.(x)l)，iki又因為q(x)為對稱函數(shù)，所以q(Ic.(x)I)=q(c.(x)，q(ICi(x)I)=q(Ci(x),由此可得q(c.(xk)>q(c.(x)對任何x滿足式(3-18)，由x的定義，我們有kf&quo

13、t;產(chǎn)q©)>f(xk)+ak工q(C.(xk)(3-19)39i=1i=1所以(3-20)f>fk工q(Ci(xk)-q(Ci(E>fblxki=1故知x是問題(3-17)-(3-18)的解。k證畢。由以上引理可知，若取£充分小，則當算法迭代結(jié)束時，x是問題(3-12)-k(3-14)的近似解。引理2對于由算法所產(chǎn)生的序列x總有，kL(x,a)>L(x,a)(3-21)k+1k+1kkQ(x)<Q(x)k+1k(3-22)f(x)>f(x)(3-23)k+1k其中k>1。證明由L(xq)=f(x)+cQ(x)和>c可知，k+

14、1kL(xQ)二f(x)+Q(x)>f(x)+Q(x)二L(xQ)k+1k+1k+1k+1k+1k+1kk+1k+1k又因為x是L(xQ)的極小點，所以對于任意x總有L(xq)>L(xq)，特kkkkk別有L(x,Q)>L(x,Q)。k+1kkk由此可證得(3-21)。因為x和x分別使L(x,Q)和L(x,Q)取極小，所以有kk+1kk+1f(x)+QQ(x)>f(x)+QQ(x)k+1kk+1kkkf(x)+QQ(x)>f(x)+QQ(x)kk+1kk+1k+1k+1由上式可得f(x)-f(x)>QQ(x)-Q(x)k+1kkkk+1QQ(x)-Q(x)&

15、gt;f(x)-f(x)k+1kk+1k+1k由此可得(Q-Q)Q(x)-Q(x)>0k+1kkk+1由于Q>Q>0，所以(3-22)成立。k+1k最后，由式(3-21)和(3-22)得式(3-23)成立。證畢。定理1設(shè)非線性約束問題(3-12)-(3-14)的最優(yōu)解存在，設(shè)xj由算法產(chǎn)生，且罰參數(shù)序列q單調(diào)遞增且趨于+-，則x的任何極限點都是問題kk(3-12)-(3-14)的可行域上的最優(yōu)解。證明設(shè)xtx*，又設(shè)x*是問題(3-12)-(3-14)的最優(yōu)解，由于x是無kk約束問題minL(x)xeRnQk的解，由于x*可行，即Q(x*)二0，故有L(x)<L(x*)

16、=f(x*)+qQ(x*)=f(x*)QkQkkk即L(x)=f(x)+QQ(x)<f(x*)Qkkkkk由此可得0<Q(x)<f(x)f(Xk)，由于xtx*,bfg。故得kbkkkf(x*)<f(x*)，且Q(x*)=0。即x*可行，且f(x*)<f(x*)，但x*是問題(3-12)-(3-14)的解，因此x*也是問題(3-12)-(3-14)的解。證畢。我們現(xiàn)在對于優(yōu)化中的罰函數(shù)法進行一般類型的概況，并證明其收斂性，但是需要說明的是其中不同種類的罰函數(shù)法在其收斂速度各有其不同。3.3改進的罰函數(shù)法及收斂性3.3.1改進的罰函數(shù)算法罰函數(shù)法是解決約束優(yōu)化問題的

17、重要方法，它的基本思想是把約束優(yōu)化問題轉(zhuǎn)化成求解一系列的無約束極小化問題。通過有關(guān)的無約束問題來研究約束極值問題，經(jīng)常采用的方法之一是在原來的目標函數(shù)上加上由約束函數(shù)組成的一個“懲罰項”來迫使迭代點逼近可行域，這種方法稱為罰函數(shù)法。如何選取罰函數(shù)，以加速迭代算法的收斂速度，一直是約束優(yōu)化問題研究的熱點問題。罰函數(shù)作為評價函數(shù)來評價一個點的好壞，這在選擇新點確定步長等方面都起著重要作用，不同罰項的選取，構(gòu)成不同的罰函數(shù)，必然會對算法產(chǎn)生不同的影響，因此對不同罰項的研究具有重要的理論和實用價值。對一般約束最優(yōu)化問題minf(x)(3-24)s.tc(x)=0ii=1,2,m;(3-25)c(x)&

18、gt;0ii=m+1,m+2，n;(3-26)通常使用的外函數(shù)形式為：L(x,Q)二f(x)+QQ(x)其中罰項為：Q(x)=Qc(x)F+刀|min0,c(x)卜,a>1,P>1。a為iii=1i=m+1參數(shù)，若取a=P=2，我們稱上述罰函數(shù)L(x,a)為二次罰函數(shù)。問題(3-24)-(3-26)的可行域R為R=xlc(x)=0,i=1,2,m;c(x)>0,i=m+1,m+2,n;ii顯然，當x為可行點時，Q(x)=0；當x不是可行點時，Q(x)>0，而且x離可行域越遠Q(x)的值越大。它的優(yōu)點是允許從可行域的外部逐步逼近逼近最優(yōu)點，但按上述定義的罰函數(shù)的缺點是：需

19、要罰因子趨于無窮大，才可能使求解罰函數(shù)的極小和求解原問題等價。為了有效的改善這種罰函數(shù)，我們試圖構(gòu)造一種能夠加速迭代算法收斂的外罰函數(shù)法。本文提出一種用雙曲正弦函數(shù)作罰項的罰函數(shù)，并由此構(gòu)建了雙曲正弦罰函數(shù)法，不僅證明了該罰函數(shù)和算法的合理性及迭代點列的收斂性，而且做了數(shù)值實驗。結(jié)果表明本文中所提出的罰函數(shù)及對應(yīng)的算法可以在罰因子與二次罰函數(shù)方法中的罰因子相同的情況下，有著更快的收斂速度。定義1稱L(x,a)=f(x)+Pa(x)=f(x)+aQ(x)(3-27)a為問題(3-24)-(3-26)的雙曲正弦罰函數(shù)，a>0為罰因子，其中罰項Q(x)=遲sinh2(c(x)+工sinh2(m

20、in0,c(x)(3-28)iiete-1、i=1i=m+1其中sinh(t)=,tgR；sinh2(t)=(2若定義i=1,2,m,i=m+1,m+2,n,ci(x)=<c(x)imin0,c(x)i則x是可行點當且僅當c(x)=0oi我們通過一系列雙曲正弦函數(shù)L(x,a七)的極小點，其中a七為一定值，得到相應(yīng)無約束極小點，序列x來逼近約束問題(3-24)-(3-26)的極小點x*ok雙曲正弦罰函數(shù)算法：步1選定初始點為X；選取初始懲罰因子b>0(可取b二1)，懲罰因011子的放大系數(shù)c>1(可取c二10)；置k二1。步2以x為初始點，求解無約束問題k-1minL(x,b)

21、kxeRnk其中L(x,b)二f(x)+P(x)二f(x)+bQ(x)kbkk設(shè)其極小點為x。k步3若bQ(x)<8，則x就是所要求的最優(yōu)解，停止；否則轉(zhuǎn)下一步。kk步4置b二cb；k二k+1，轉(zhuǎn)步2。k+1k3.3.2收斂性證明及數(shù)值試驗引理1設(shè)函數(shù)Q和p由定義1定義，x,由算法產(chǎn)生，且罰參數(shù)序列單調(diào)遞增，則&k(1)Q(x)<Q(x)kk-1(2)(3)證明f(x-)<f(x)k-1kL(x)<L(x)k+1bkkbk+1(1)由x的定義知kL(x)<L(x)<bkbk+1L(x)<L(x)bk-1k-1bk-1k上面的兩式相加，-bk-1

22、)(Q(xk)-Q(xk-1)<0(b-kk-1即(1)成立。(2)由L(x)<L(x)得b-1k-1b-1kkkf(x)<f(x)+b(Q(x)-Q(x)<f(x)k-1kk-1kk-1k因此Q(x)<Q(xkk-1)，即(2)成立。(3)由L以及x的定義得akL(x)<L(x)=f(x)+aQ(x)<f(x)+aQ(x)=L(x)akkakk+1k+1kk+1k+1k+1k+1%k+1即(3)成立。證畢。引理2設(shè)函數(shù)Q和P由定義1定義，x由算法產(chǎn)生，且罰參數(shù)序列a單調(diào)遞增，記5二Q(x)，則x也是約束問題kkkkminf(x)(3-29)s.tQ(

23、x)<5k的解。證明設(shè)x是問題(3-29)的可行點，我們有0<aQ(x)-Q(x)二L(x)-L(x)+f(x)-f(x)<f(x)-f(x)kkakakkkk因此x是問題(3-29)的解。k證畢。定理1設(shè)非線性約束問題(3-24)-(3-26)的最優(yōu)解存在，設(shè)x由算法產(chǎn)k生，且罰參數(shù)序列a單調(diào)遞增且趨于+8，則x的任何極限點都是問題kk(3-24)-(3-26)的可行域上的最優(yōu)解。證明設(shè)xtx*，又設(shè)x*是問題(3-24)-(3-26)的最優(yōu)解，由于x是無kk約束問題minL(x)，xeRn的解，由于x*可行，即Q(x*)=0，故有akL(x)<L(x*)=f(x*)+aQ(x*)=f(x*)akakkk即L(x)=f(x)+aQ(x)<f(x*)kkkkk由此可得0<Q(x)<f(x)f(x)，由于xtx*，aTX。故得kakkkf(X*)<f(x),且Q(x*)=0。即x*可行，且f(