庫(kù)恩-塔克條件課件

庫(kù)恩—塔克條件數(shù)學(xué)規(guī)劃設(shè)如下的數(shù)學(xué)模型稱為數(shù)學(xué)規(guī)劃(MathematicalProgramming,MP)：約束集或可行域向量化表達(dá)令

其中，那么(MP)可簡(jiǎn)記為

或者

當(dāng)p=0,q=0時(shí)，稱為無(wú)約束非線性規(guī)劃或者無(wú)約束最優(yōu)化問(wèn)題。否則，稱為約束非線性規(guī)劃或者約束最優(yōu)化問(wèn)題。有效約束

是非線性規(guī)劃的一個(gè)可行解?，F(xiàn)考慮某一不等式約束，滿足該不等式有兩種可能：（1）此時(shí)不在由該約束形成的可行域邊界上，因此該約束對(duì)的微小變動(dòng)不起限制作用，從而稱該約束為無(wú)效約束；（2）此時(shí)處在由該約束形成的可行域邊界上，因此該約束對(duì)的微小變動(dòng)會(huì)起某種限制作用，從而稱該約束為有效約束。顯而易見(jiàn)，所有等式約束都是有效約束。

可行方向的有效約束若是點(diǎn)的任一可行方向，則對(duì)該點(diǎn)所有有效約束均有：

(1)

其中j代表在點(diǎn)所有有效約束下標(biāo)的集合可行方向的有效約束另一方面，由泰勒展開(kāi)式

(2)

可知對(duì)所有有效約束，當(dāng)足夠小時(shí)，只要滿足（1）式，則有此外，對(duì)點(diǎn)所有的無(wú)效約束來(lái)講，由于約束函數(shù)的連續(xù)性，當(dāng)足夠小時(shí)，上式依然成立。從而，只要方向滿足式（1），即可保證是點(diǎn)的可行方向?？尚邢陆捣较?qū)⒛繕?biāo)函數(shù)在處作一階泰勒展開(kāi)，若方向D滿足（3）則D必是點(diǎn)的一個(gè)下降方向。如果Ｄ方向既是點(diǎn)的一個(gè)可行方向又是一個(gè)下降方向，就稱Ｄ是點(diǎn)的一個(gè)可行下降方向。顯然，如果某點(diǎn)存在可行下降方向，那么該點(diǎn)就不會(huì)是極小點(diǎn)；另一方面，如果某點(diǎn)是極小點(diǎn)，則該點(diǎn)不存在可行下降方向。兩種情況假設(shè)X*是非線性規(guī)劃的極小點(diǎn)，該點(diǎn)可能處于可行域的內(nèi)部，也可能處于可行域的邊緣上。若為前者，該規(guī)劃問(wèn)題實(shí)質(zhì)是一個(gè)無(wú)約束極值問(wèn)題，X*必滿足；若為后者，情況就復(fù)雜多了，接下來(lái)我們就對(duì)這一復(fù)雜情況進(jìn)行分析。

兩個(gè)有效約束邊界的情況及推廣由此可見(jiàn)，如果X*是極小點(diǎn)，而且X*點(diǎn)的有效約束的梯度和線性獨(dú)立，則可以將表示成為和的非負(fù)線性組合；也就是說(shuō)，存在實(shí)數(shù)和，使：（6）如此類推，可以得到（J是所有有效約束的集合）（7）可能的無(wú)效約束處理為使所有無(wú)效約束也同上述有效約束一樣包含在式（7）中，增加約束條件

庫(kù)恩—塔克條件設(shè)X*是非線性規(guī)劃的極小點(diǎn)，而且X*點(diǎn)各有效約束的梯度線性獨(dú)立，則存在向量，使下述條件成立：（8）

一般形式的庫(kù)恩-塔克條件

由于等式約束總是有效約束，所以一般形式的非線性規(guī)劃的庫(kù)恩-塔克條件可表達(dá)為：設(shè)X*是非線性規(guī)劃的極小點(diǎn)，而且X*點(diǎn)的所有有效約束的梯度

和