K-T條件與罰函數(shù)法

1、非線性規(guī)劃及其應(yīng)用非線性規(guī)劃及其應(yīng)用Kuhn-Tucker理論、 罰函數(shù)法Kuhn-Tucker理論理論Kuhn-Tucker條件（或稱Karush-Kuhn-Tucker條件）是將等式約束的Lagrange乘子法推廣到不等式約束，不必加入剩余變量。Kuhn-Tucker條件是確定約束極值點(diǎn)的必要條件，對(duì)于凸規(guī)劃來說同時(shí)也是充分條件。二、二、不等式約束問題的不等式約束問題的Kuhn-Tucker條件：條件： NLP問題問題 min f(x) s.t. hi(x)=0 i=1,2,.,m gj(x)0 j=1,2, ,p 設(shè)設(shè) x*S=x|gj(x) 0 j=1,2, ,p 令令 J=j| gj

2、(x*) =0 j=1,2, ,p 稱稱J為為 x*點(diǎn)處的起作用集（緊約束集）。點(diǎn)處的起作用集（緊約束集）。 如果如果x*是是最優(yōu)值最優(yōu)值,對(duì)每一個(gè)約束函數(shù)來說，只有當(dāng)它是起作用對(duì)每一個(gè)約束函數(shù)來說，只有當(dāng)它是起作用約束時(shí)，才產(chǎn)生影響，如：約束時(shí)，才產(chǎn)生影響，如：(fg)g2(x)=0 x*g1(x)=0g1(x*)=0, g1為起作用約束二、二、不等式約束問題的不等式約束問題的Kuhn-TuckerKuhn-Tucker條件：條件： 定理（最優(yōu)性必要條件）：定理（最優(yōu)性必要條件）： （K-TK-T條件）條件） 問題問題(fg), (fg), 設(shè)設(shè)S=x|gS=x|gj j(x)0,X(x)0

3、,X* *S,JS,J為為X X* *點(diǎn)處的起作用集，點(diǎn)處的起作用集，設(shè)設(shè)f(x),hf(x),hi i(x),g(x),gj j(x),jJ(x),jJ在在X X* *點(diǎn)可微點(diǎn)可微,g,gj j(x), h(x), hi i(x)(x)在在X X* *點(diǎn)連點(diǎn)連續(xù)。續(xù)。 向量組向量組 h hi i(X(X* *),),g gj j(X(X* *)線性無關(guān)。線性無關(guān)。 如果如果X X* *是極小點(diǎn)且滿足正則條件是極小點(diǎn)且滿足正則條件, ,則必存在則必存在* *=(=(1 1,2 2,.,.,m m) )T, ,* *=(=(1 1,2 2,.,.P) )T,使得以下各式成立：使得以下各式成立：J

4、j庫恩-塔克條件應(yīng)用舉例若給定優(yōu)化問題的數(shù)學(xué)模型為 22122minf xxx. .st 211210gxxx 223100gxxgxx *01,2,.,00jjj Jiijjdf xdgxindxdxgxjJjJK-T條件庫恩-塔克條件的幾何意義：在約束極小點(diǎn)處，函數(shù)的負(fù)梯度一定能表示成所有起作用約束在該點(diǎn)梯度的非負(fù)線性組合。下面以二維問題為例，說明K-T條件的幾何意義二、約束極值點(diǎn)的二階充分條件二、約束極值點(diǎn)的二階充分條件 前面我們討論了兩類最優(yōu)化問題：約束極值問題及非線性規(guī)化問題，并且給出了求解兩類問題的拉格朗日方法和庫恩塔克條件。 不過，從求解的過程看，無論是前面梯度向量的角度，還是后

5、面等式約束問題的拉格朗日方法、非線性規(guī)劃的庫恩塔克條件，我們都只是分析了在最優(yōu)解處應(yīng)滿分析了在最優(yōu)解處應(yīng)滿足的性質(zhì)，而并沒有保證滿足此性質(zhì)的點(diǎn)一定是最優(yōu)解足的性質(zhì)，而并沒有保證滿足此性質(zhì)的點(diǎn)一定是最優(yōu)解，比如最大值問題和最小值問題的一階條件是相同的，或者說由拉格朗日方法推導(dǎo)出的一階條件和庫恩塔克條件只是解的必要條件。為此，我們需要找到新的條件，以保證為此，我們需要找到新的條件，以保證由一階必要條件所求得的解就是此最優(yōu)規(guī)劃問題的最優(yōu)解，由一階必要條件所求得的解就是此最優(yōu)規(guī)劃問題的最優(yōu)解，這就是二階條件的討論這就是二階條件的討論。 對(duì)于凸規(guī)劃來說，Kuhn-Tucker點(diǎn)事其全局極小點(diǎn)，但是對(duì)目標(biāo)

6、函數(shù)、約束函數(shù)的要求比較嚴(yán)格，實(shí)際情況難以滿足，這可以用二階充分條件來進(jìn)行檢驗(yàn)Kuhn-Tucker點(diǎn)是否是局部極小點(diǎn)。 對(duì)于前述NLP問題，如果目標(biāo)函數(shù)、約束函數(shù)均二階連續(xù)可微，可行點(diǎn)X*是嚴(yán)格局部極小點(diǎn)的二階充分條件為： （1）存在(*,*),使(X*,*,*)是一個(gè)Kuhn-Tucker點(diǎn)，既滿足Kuhn-Tucker條件。對(duì)于滿足條件 的非0向量Y所形成的子空間M上,有 YTHL (X*,*,*)Y0 (d)即L(X,)的黑塞矩陣 在子空間M上正定,式中A(X*)為X*出起作用的不等式約束的下標(biāo)集，J+,J0分別是A(X*)的滿足條件j*0,j*=0的子集。)(Xg-)(Xh-)f(X

7、=*)*,(X*, H*j2p1j*i2m1i*i*2Lj罰函數(shù)法罰函數(shù)法約束最優(yōu)化問題約束最優(yōu)化問題 基本思想基本思想 無約束最優(yōu)化問題無約束最優(yōu)化問題 利用問題的目標(biāo)函數(shù)和約束函數(shù)構(gòu)造新的目標(biāo)函數(shù)利用問題的目標(biāo)函數(shù)和約束函數(shù)構(gòu)造新的目標(biāo)函數(shù) 罰函數(shù)罰函數(shù)（penalty function） P(X,R)=f(X)+Q(R,h(X),g(X) 式中式中Q是懲罰項(xiàng)，是懲罰參數(shù)是懲罰項(xiàng)，是懲罰參數(shù)R和約束的函數(shù)和約束的函數(shù)。一般形式一般形式Sequential unconstrained minimization technique序列無約束最小化技術(shù)混合罰函數(shù)法外點(diǎn)罰函數(shù)法內(nèi)點(diǎn)罰函數(shù)法罰函數(shù)法

8、內(nèi)點(diǎn)罰函數(shù)法mixgtsxfi, 2 , 10)(. .)(min是連續(xù)函數(shù)。其中), 2 , 1)(),(mixgxfi基本思想: 迭代總是從內(nèi)點(diǎn)出發(fā),并保持在可行域內(nèi)部進(jìn)行搜索. niExmixgxS, 2 , 1, 0)(|int|( )0,1,2,niSx g xim xE罰(障礙)函數(shù))()(),(xrBxfrxG。趨向可行域邊界時(shí)，當(dāng)點(diǎn)是連續(xù)函數(shù)；它滿足兩個(gè)條件：定義在可行域內(nèi)部，是很小的正數(shù)，其中)()2()() 1 ()(xBxxBxBr兩種最重要的形式:miimiixgxBxgxB11)(ln)()(1)(對(duì)數(shù)障礙函數(shù)障礙因子倒數(shù)障礙函數(shù)min. .10 xs tx1( ),

9、1( , )1B xxrG x rxx 取則 內(nèi) 罰 函 數(shù) 為210(1)( )10( )1*.Grxxxx rrrx rx 令得到當(dāng)時(shí)，有兩種障礙函數(shù)的比較min. .10 xs tx ( )ln1 ,( , )ln1B xxG x rxrx 取則內(nèi)罰函數(shù)為101( )10( )1*.Grxxxx rrrx rx 令得到當(dāng)時(shí)，有兩種障礙函數(shù)的比較例:考慮約束優(yōu)化問題1. .2minxtsx) 1ln(2),(xrxrxG該問題的對(duì)數(shù)障礙函數(shù)為( , ):121(0)11(, )ln2(0)22rrG x rxrrG x rrrrr 的最小點(diǎn)為mixgtsxfi, 2 , 10)(. .)(

10、minSxtsxrBxfrxGint. .)()(),(minSxtsxBrxfrxGkkint. .)()(),(min 的障礙因子數(shù)列。為嚴(yán)格單調(diào)減且趨于其中0kr步驟:。置縮小系數(shù)，初始參數(shù)，允許誤差給定初始點(diǎn)1),1, 0(,0int. 11)0(krSx。設(shè)其極小點(diǎn)為題為初始點(diǎn)，求解下列問以)()1(int. .)()(min. 2kkkxSxtsxBrxfx。，返回，置令；否則，則停止計(jì)算，得到點(diǎn)若21:)(. 31)()(kkrrxxBrkkkkk例:用內(nèi)點(diǎn)法求解下列問題00. .min122121xxxtsxx212121122112121212( , )lnln210,103

11、11118,1184280*(0,0)kkkkkkkkTkG x rxxrxxrxx rrrGGxxxxxxxrxrxrrx 解：定義障礙函數(shù)令當(dāng)時(shí)，1213111 8,11 8428kkrxrxr 12( )( )110.51.2520.50.3090.5953 0.250.1830.28340.10.0850.1075 0.000100kkkrx rx rx4x3x2x1求初始內(nèi)點(diǎn)的迭代步驟。置如取任取0:),1(0,. 100)0(krrExn.1, 0)(|,1, 0)(|. 2)()(mixgiTmixgiSkikkik令。，停止計(jì)算；否則，轉(zhuǎn)若4. 3kSkikkTiikSiikT

12、ixgxRrxgrxgrxPkk0)(|)0()(1)(),(. 4記構(gòu)造函數(shù)。，轉(zhuǎn)得的極小點(diǎn)域內(nèi)，求障礙函數(shù)為初始點(diǎn)，在以6. .),(min:),(. 5)1()(kkkkkkxRxtsrxPrxPRx。轉(zhuǎn)，置如取令21:,1010. 611kkrrrrkkkk內(nèi)點(diǎn)罰函數(shù)法優(yōu)點(diǎn)內(nèi)點(diǎn)罰函數(shù)法缺點(diǎn) 迭代總在可行域內(nèi)進(jìn)行，每一個(gè)中間結(jié)果都是可行解，可以作為近似解。 選取初始可行點(diǎn)較困難，且只適用于含不等式約束的非性性規(guī)劃問題。 外點(diǎn)罰函數(shù)法ljxhmixgtsxfAji, 2 , 10)(, 2 , 10)(. .)(min)(), 2 , 1(0)(), 2 , 1(0)(|), 2 , 1)

13、(), 2 , 1)(),(ljxhmixgxSEljxhmixgxfjinji上連續(xù)。在其中引入罰項(xiàng)00)(00)(00)(00)()(),()()()(11yyyyyyyyyyxhxgxpljjmii當(dāng)當(dāng)當(dāng)當(dāng)是連續(xù)函數(shù)，且滿足其中。均為給定常數(shù)，通常取其中的典型取法：和函數(shù)21, 1)()()(, 0max)(xhxhxgxgjjiiljxhmixgtsxfji, 2 , 10)(, 2 , 10)(. .)(min)()(),(minxpxfxFmiljjixhxgxfxF11)()()(),(min是很大的正數(shù)。其中01)(. .) 1()(min22221xxgtsxxxf1) 1() 1(1) 1() 1(, 0max) 1(),(222222122221222221xxxxxxxxxxxF解：定義罰函數(shù)12120011()11FFxxxxx 令得1) 1(2212) 1(222222211xxxxxxFxxF外點(diǎn)法迭代步驟:。，置，允許誤差系數(shù)，放大，初始罰因子給定初始點(diǎn)101) 1(0. 111)0(kcx。設(shè)其極小點(diǎn)為問題為初始點(diǎn)，求解無約束以)()1()()(min. 2kkkxxpxfx。，返回，置令；否則，則停止計(jì)算，得到點(diǎn)若21:)(. 31)()(kkcxxpkkkkk混合法混合法 混合法是將內(nèi)點(diǎn)法和外點(diǎn)法的懲罰項(xiàng)形式結(jié)合在一