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

非線性規(guī)劃及其應(yīng)用——Kuhn-Tucker理論、罰函數(shù)法Kuhn-Tucker理論Kuhn-Tucker條件〔或稱Karush-Kuhn-Tucker條件〕是將等式約束的Lagrange乘子法推廣到不等式約束，不必參加剩余變量。Kuhn-Tucker條件是確定約束極值點(diǎn)的必要條件，對(duì)于凸規(guī)劃來說同時(shí)也是充分條件。二、不等式約束問題的Kuhn-Tucker條件：NLP問題minf(x)s.t.hi(x)=0i=1,2,.....,mgj(x)≤0j=1,2,…,p設(shè)x*∈S={x|gj(x)≤0j=1,2,…,p}令J={j|gj(x*)=0j=1,2,…,p}稱J為x*點(diǎn)處的起作用集〔緊約束集〕。如果x*是最優(yōu)值,對(duì)每一個(gè)約束函數(shù)來說，只有當(dāng)它是起作用約束時(shí)，才產(chǎn)生影響，如：(fg)g2(x)=0x*g1(x)=0g1(x*)=0,g1為起作用約束二、不等式約束問題的Kuhn-Tucker條件：

定理〔最優(yōu)性必要條件〕：〔K-T條件〕問題(fg),設(shè)S={x|gj(x)≤0},X*∈S,J為X*點(diǎn)處的起作用集，設(shè)f(x),hi(x),gj(x),j∈J在X*點(diǎn)可微,gj(x),hi(x)在X*點(diǎn)連續(xù)。向量組{▽hi(X*)},{▽gj(X*)}線性無關(guān)。如果X*是極小點(diǎn)且滿足正那么條件,那么必存在λ*=(λ1,λ2,...,λm)T,γ*=(γ1,γ2,...γP)T,使得以下各式成立：庫(kù)恩-塔克條件應(yīng)用舉例假設(shè)給定優(yōu)化問題的數(shù)學(xué)模型為K-T條件庫(kù)恩-塔克條件的幾何意義：在約束極小點(diǎn)處，函數(shù)的負(fù)梯度一定能表示成所有起作用約束在該點(diǎn)梯度的非負(fù)線性組合。下面以二維問題為例，說明K-T條件的幾何意義二、約束極值點(diǎn)的二階充分條件前面我們討論了兩類最優(yōu)化問題：約束極值問題及非線性規(guī)化問題，并且給出了求解兩類問題的拉格朗日方法和庫(kù)恩－塔克條件。不過，從求解的過程看，無論是前面梯度向量的角度，還是后面等式約束問題的拉格朗日方法、非線性規(guī)劃的庫(kù)恩－塔克條件，我們都只是分析了在最優(yōu)解處應(yīng)滿足的性質(zhì)，而并沒有保證滿足此性質(zhì)的點(diǎn)一定是最優(yōu)解，比方最大值問題和最小值問題的一階條件是相同的，或者說由拉格朗日方法推導(dǎo)出的一階條件和庫(kù)恩－塔克條件只是解的必要條件。為此，我們需要找到新的條件，以保證由一階必要條件所求得的解就是此最優(yōu)規(guī)劃問題的最優(yōu)解，這就是二階條件的討論。

對(duì)于凸規(guī)劃來說，Kuhn-Tucker點(diǎn)事其全局極小點(diǎn)，但是對(duì)目標(biāo)函數(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*,λ*,γ*)Y>0(d)即L(X,λ,γ)的黑塞矩陣

在子空間M上正定,式中A(X*)為X*出起作用的不等式約束的下標(biāo)集，J+,J0分別是A(X*)的滿足條件γj*>0,γj*=0的子集。罰函數(shù)法約束最優(yōu)化問題

根本思想無約束最優(yōu)化問題

利用問題的目標(biāo)函數(shù)和約束函數(shù)構(gòu)造新的目標(biāo)函數(shù)——罰函數(shù)〔penaltyfunction〕

P(X,R)=f(X)+Q(R,h(X),g(X))

式中Q是懲罰項(xiàng)，是懲罰參數(shù)R和約束的函數(shù)。一般形式Sequentialunconstrainedminimizationtechnique序列無約束最小化技術(shù)內(nèi)點(diǎn)罰函數(shù)法根本思想:迭代總是從內(nèi)點(diǎn)出發(fā),并保持在可行域內(nèi)部進(jìn)行搜索.罰(障礙)函數(shù)兩種最重要的形式:對(duì)數(shù)障礙函數(shù)障礙因子倒數(shù)障礙函數(shù)兩種障礙函數(shù)的比較兩種障礙函數(shù)的比較例:考慮約束優(yōu)化問題該問題的對(duì)數(shù)障礙函數(shù)為步驟:例:用內(nèi)點(diǎn)法求解以下問題x4x3x2x1求初始內(nèi)點(diǎn)的迭代步驟內(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ù)法引入罰項(xiàng)外點(diǎn)法迭代步驟:混合法

混合法是將內(nèi)點(diǎn)法和外點(diǎn)法的懲罰項(xiàng)形式結(jié)合在一起，用于解決同時(shí)包含等式約束和不等式約束的NLP問題。其中不等式約束的懲罰項(xiàng)采用內(nèi)點(diǎn)法的形