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

1、 懲懲 罰罰 函函 數(shù)數(shù) 法法 （Penalty Function Penalty Function MehthodMehthod）南京郵電大學(xué)南京郵電大學(xué) 理學(xué)院理學(xué)院 信息與計(jì)算科學(xué)系信息與計(jì)算科學(xué)系 min f(x) s.t. s1(x) 0 sm(x) 0 h1(x)=0 hn(x)=0數(shù)學(xué)模型數(shù)學(xué)模型 將這種約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題（罰函數(shù)法罰函數(shù)法等）求解約束問(wèn)題的方法分類求解約束問(wèn)題的方法分類 直接從這種約束問(wèn)題出發(fā)來(lái)求解。 因無(wú)約束問(wèn)題已有較好的求解方法比如BFGS,DFP 將約束條件對(duì)問(wèn)題的限制作用按一定的規(guī)則轉(zhuǎn)換到目標(biāo)函數(shù)上，然后對(duì)轉(zhuǎn)換后得到的新的無(wú)約束問(wèn)題求解,然后將求解

2、的結(jié)果反映到原問(wèn)題. 仿照無(wú)約束優(yōu)化問(wèn)題的求解思想，構(gòu)造構(gòu)造“下降迭代算法”但是構(gòu)造的方向滿足下降要求前，首先要滿足可行域！所以這類方法我們稱為可行下降方向法。min x12+x22s.t. x1+x2-2=0由圖解法易見(jiàn)最優(yōu)解為(1,1)T直觀引例直觀引例將這個(gè)問(wèn)題改造改造為一個(gè)無(wú)約束問(wèn)題如下：min (x12+x22)+ (x1+x2-2)2 (*)分析：分析： 任意點(diǎn)x若不滿足原問(wèn)題的約束，則(*)第二項(xiàng)就會(huì)非常大那么該點(diǎn)x就不會(huì)是(*)的最優(yōu)解。這樣的存在迫使最優(yōu)解在可行域內(nèi)取得。隨著的增大或更特殊地取 為為+，則問(wèn)題，則問(wèn)題( (* *) )就成為就成為：min min (x(x12

3、+x+x22) ) 當(dāng)當(dāng)( (x x1+x+x2-2-2)=0.)=0.這恰為所要求解的原問(wèn)題.min x12+x22s.t. x1+x2-2=0 為一個(gè)充分大的正的參數(shù)為一個(gè)充分大的正的參數(shù)引例求解思想的理論支持引例求解思想的理論支持問(wèn)題問(wèn)題 min (x12+x22)+ (x1+x2-2)2最優(yōu)解的解析式為：最優(yōu)解的解析式為：12221)()(xxTTxx),(),()()(1121時(shí)，當(dāng)問(wèn)題問(wèn)題“粗放粗放”想法的進(jìn)一步深入分想法的進(jìn)一步深入分析析的最優(yōu)解即是原問(wèn)題的最優(yōu)解，但是為+在計(jì)算機(jī)上無(wú)法實(shí)現(xiàn)。理論上特殊地取為+，則min (x12+x22)+ (x1+x2-2)2 (*) 為一個(gè)

4、較大的正的參數(shù)為一個(gè)較大的正的參數(shù) 實(shí)際上充分大時(shí)，(*)的最優(yōu)解即可為原問(wèn)題的最優(yōu)解。 先給定給定，求解問(wèn)題 min (x12+x22)+ (x1+x2-2)2. 判斷判斷得到的點(diǎn)是否是原問(wèn)題的解，若還不是，則增大增大再求上述問(wèn)題，若還不是，繼續(xù)繼續(xù)。比如本例：取為0,1,10,100,1000時(shí)的解如圖,趨于趨于(1,1)(1,1)T T. .引例的計(jì)算機(jī)處理方法引例的計(jì)算機(jī)處理方法引例的計(jì)算機(jī)處理方法引例的計(jì)算機(jī)處理方法為一個(gè)大正數(shù)其中, )(min nx1j2jhf(x)F(x, 一般地，對(duì)于等式約束問(wèn)題， min f(x) s.t. hj(x)=0, j=1:n將此問(wèn)題改造成一個(gè)新問(wèn)

5、題(*)：xx這個(gè)新問(wèn)題的最優(yōu)解 必定使得hj( )接近于0引例求解思想推廣到一般的等式約束問(wèn)題引例求解思想推廣到一般的等式約束問(wèn)題因?yàn)槭沟胔j(x)=0的那些x就能使得F(x,)的值比F( ,）小x現(xiàn)在的這個(gè)點(diǎn) 就不會(huì)是這個(gè)無(wú)約束問(wèn)題的極小點(diǎn)x否則的話式子中的第二項(xiàng)就會(huì)是一個(gè)很大的正數(shù)新目標(biāo)函數(shù)的特征：在任意原問(wèn)題的可行點(diǎn)x處：F(x, )=f(x);在任意原問(wèn)題的不可行點(diǎn)x”處： F(x”, )=f(x”)+大正數(shù)。為一個(gè)大正數(shù)其中, )(min nx1j2jhf(x)F(x, ）（222)(.)()(minxxxm21max0,-smax0,-smax0,-sf(x)F(x, 根據(jù)這樣的

6、原則，對(duì)不等式約束問(wèn)題可以類似構(gòu)造：min f(x)s.t. si(x) 0,i=1;m轉(zhuǎn)化為(易驗(yàn)證滿足上述原則) m1iimax0,-s2)()(xxf 不等式約束問(wèn)題改造為相應(yīng)無(wú)約束優(yōu)化問(wèn)題的方法不等式約束問(wèn)題改造為相應(yīng)無(wú)約束優(yōu)化問(wèn)題的方法 m1i2i2m2221max0,-s max0,-smax0,-smax0,-sf(x)F(x, )()()(.)()(minxxfxxx）（x0轉(zhuǎn)換原則的解釋轉(zhuǎn)換原則的解釋在極小化新無(wú)約束問(wèn)題時(shí)所考慮的是整個(gè)空間上的點(diǎn)，而這些點(diǎn)其實(shí)是兩大塊：原可行域D和Rn-D當(dāng)任取一點(diǎn)當(dāng)任取一點(diǎn)x0 x0時(shí)時(shí)F(xF(x0, , ) )顯然是要比顯然是要比F(x

7、, F(x, )()( x x D)D)大的，大的，所以所以min F(x, min F(x, ) )時(shí)總體上就是從時(shí)總體上就是從D D外邊向外邊向D D里邊里邊( (或是邊界或是邊界) )“跑跑”！比如一個(gè)具體的例子比如一個(gè)具體的例子：min (x-1)2 2 s.t. x-20構(gòu)造構(gòu)造F(x, )=(x-1)2 2+ max(0,-(x-2)2 2取0,1,10時(shí)F的極小點(diǎn)如圖總體上就是從總體上就是從D D外邊向外邊向D D里邊里邊( (或是邊界或是邊界) )“跑跑”?。?(.)()()(.)()(min22221222xhxhxhxxxl m21max0,-smax0,-smax0,-

8、sf(x)F(x, 對(duì)于混合約束問(wèn)題對(duì)于混合約束問(wèn)題 min f(x) s.t. si(x) 0,i=1:m hj(x)=0,j=1:n.也可以轉(zhuǎn)化轉(zhuǎn)化為 ) )()()( njxxxf12jm1i2ih max0,-s混合約束問(wèn)題改造為相應(yīng)無(wú)約束優(yōu)化問(wèn)題的方法混合約束問(wèn)題改造為相應(yīng)無(wú)約束優(yōu)化問(wèn)題的方法P(x)-懲罰函數(shù)（懲罰項(xiàng)）懲罰函數(shù)（懲罰項(xiàng)）-罰因子罰因子F(x, )-增廣目標(biāo)函數(shù)增廣目標(biāo)函數(shù)）（)(.)()()(.)()(minxhxhxhxxxn222212m2221max0,-smax0,-smax0,-sf(x)F(x, ) )()()( njxxxf12jm1i2ih max0

9、,-s)(xP給定初始點(diǎn)x(0)，初始懲罰因子1，放大系數(shù)c1,置k=1STEP 1STEP 1: :以x(k-1)為初始點(diǎn)求解 min F(x,min F(x, k k),),得極小點(diǎn)x(k)STEP 2STEP 2: :若x(k) 符合原問(wèn)題的最優(yōu)解要求，stopSTEP 3STEP 3: : k+1= ck,置k=k+1轉(zhuǎn)(i)外部罰函數(shù)法初步框架外部罰函數(shù)法初步框架ProofProof(必要性必要性) 顯然 (充分性充分性)若x是原問(wèn)題的極小點(diǎn),則對(duì)于原問(wèn)題的任意容許點(diǎn)x,總有f(x)=F(x, )(在x處罰項(xiàng)=0)F(x, )(x是F的極小點(diǎn))=f(x)(在x處罰項(xiàng)=0)這就說(shuō)明x是

10、原約束問(wèn)題的最優(yōu)解。定理定理(外部罰函數(shù)法的終止準(zhǔn)則終止準(zhǔn)則) 無(wú)約束問(wèn)題F(x,)的極小點(diǎn)x恰是原約束問(wèn)題的極小點(diǎn)的充要條件是x是原約束問(wèn)題的可行點(diǎn)。 解min F(x, k)=f(x)+罰項(xiàng)，得解x(k),要看它是否是容許點(diǎn),而這只要看是否罰項(xiàng)1, 0,置k：=1STEP 1STEP 1:以x(k-1)為初始點(diǎn)求解 min F(x,k) 得極小點(diǎn)x(k)STEP 2STEP 2: 若KP (x(k) 0, 0, c c1,0,k1,0,k：=1=1以以x x(k-1)為初始點(diǎn)，解為初始點(diǎn)，解min f(x)+ min f(x)+ KP P(x)(x)得得x x(k) kP(xP(x(k)

11、k,外部罰函數(shù)法產(chǎn)生的點(diǎn)列x(k)(k)的任意聚點(diǎn)均為(I)的最優(yōu)解。）（)(.)()()(.)()(minxhxhxhxxxn222212m2221max0,-smax0,-smax0,-sf(x)F(x, 外點(diǎn)法的一個(gè)重要性質(zhì)外點(diǎn)法的一個(gè)重要性質(zhì)0k0 稱為懲罰因子。4.4.內(nèi)點(diǎn)法內(nèi)點(diǎn)法已知f(x),si(x),取(x)=1/s12(x) + 1/s22 (x) + + 1/sm2 (x)取一初始容許點(diǎn)x0，初始懲罰因子10,懲罰因子 的 縮小系數(shù)縮小系數(shù)c1,置k=1(i)以x(k-1)為初始點(diǎn)，求解min f(x)+ k(x)得極小點(diǎn)x(k)；(ii)若k(x(k),stop;(iii)置k+1=c k,置k=k+1，轉(zhuǎn)(ii)內(nèi)點(diǎn)法的一個(gè)性質(zhì)內(nèi)點(diǎn)法的一個(gè)性質(zhì)0 k+1 k,