庫恩塔克定理

1、6-1最優(yōu)性條件現(xiàn)考慮一般形式的非線性規(guī)劃數(shù)學(xué)模型minf(X),XEnh(X)=0,(i=1,2,m)iLg(X)，0,(j=1,2,l)假設(shè)()、()和()均具有一階連續(xù)偏導(dǎo)f(X)h(X)g(X)數(shù)，是非線性規(guī)劃的一個可行解。現(xiàn)考慮某一X(0)不等式約束()0，滿足該不等式有兩種可g(X)，0X(0)能：(1)0，此時不在由該約束形成的g(X(0)0X(0)可行域邊界上，因此該約束對的微小變動不起X(0)限制作用，從而稱該約束為無效約束；(2)0，此時處在由該約束形成的可行域邊g(X(0)=0X(0)界上，因此該約束對的微小變動會起某種限制X(0)作用，從而稱該約束為有效約束。顯而易見，

2、所有等式約束都是有效約束。是非線性規(guī)劃的一個可行解，對于此點的X(0)某一方向，若存在實數(shù)00使任意“均D000,0有，就稱方向是點的一個可行方X(0)DRDX(0)向，此處代表非線性規(guī)劃的可行域。R若是(0)點的任一可行方向，則對該點所有DX(0)有效約束均有：g(X)，0jjJVg(X(0)TD,0j（6-18）其中代表在點所有有效約束下標(biāo)的集合，如JX（0）圖6-14所示。Dg（X）0、42圖6-14Vg（X（0）igi（X）0Vg（X（）丄2X（0）另一方面，由泰勒展開式九九（九）g（X（0）D），g（X（0）Vg（X（0）TD0可知對所有有效約束，當(dāng)兀足夠小時，只要0Vg（X（0）T

3、D0，j（6-19）就有九,g(X(0)D),0jGJ此外，對點所有的無效約束來講，由于約X(0)束函數(shù)的連續(xù)性，當(dāng)九足夠小時，上式依然成0立。從而，只要方向滿足式(6-19)，即可保證D是點的可行方向。DX(0)非線性規(guī)劃的某一可行點，對該點的任一X(0)方向來說，若存在實數(shù)心使任意九R均有00G0,0九，就稱方向是點的一個下降方f(X(0)D)f(X(0)DX(0)向。將目標(biāo)函數(shù)()在處作一階泰勒展開，若f(X)X(0)方向滿足DVf(X(0)TD0(6-20)則必是點的一個下降方向。DX(0)如果方向既是點的一個可行方向又是DX(0)一個下降方向，就稱是點的一個可行下降方DX(0)向。顯

4、然，如果某點存在可行下降方向，那么該點就不會是極小點；另一方面，如果某點是極小點，則該點不存在可行下降方向。定理3設(shè)是非線性規(guī)劃的一個局部極小X*點，目標(biāo)函數(shù)()在處可微，而且f(X)X*()在處可微，當(dāng)時g(X)X*jGJ()在處連續(xù)，當(dāng)時g(X)Xj纟JTOC o 1-5 h z(此處代表在處有效約束的下標(biāo)集合)則在JX點不存在可行下降方向，從而不存在向量同XD時滿足6-21)事實上，若在點存在向量滿足式(6-21)，XD則從點出發(fā)沿方向搜索可找到比點更好的XDX點，這與點是一個局部極小點的假設(shè)相矛盾；X所以這個定理是顯然成立的。式(6-21)的幾何意義是十分明顯的，即點X處滿足該條件的方

5、向與點目標(biāo)函數(shù)負(fù)梯度方DX向的夾角為銳角，與點所有有效約束梯度方向X的夾角也為銳角。假設(shè)是非線性規(guī)劃的極小點，該點可能處X于可行域的內(nèi)部，也可能處于可行域的邊緣上。若為前者，該規(guī)劃問題實質(zhì)是一個無約束極值問題，必滿足()0；若為后者，情況就復(fù)雜多XVf(X)0了，接下來我們就對這一復(fù)雜情況進(jìn)行分析。不失一般性，設(shè)位于第一個約束所形成的X可行域的邊緣上，即第一個約束是點處的有效X約束，()0。若是極小點，則()必與()g(X*)0X*,g(X*)-,f(X*)在同一直線上，且方向相反(這里假定()和，g(X*)()皆不為“0”)；否則，在點處就一定存在可f(X*)X*行下降方向，如圖6-15所示

6、。圖6-15中的點X*是滿足上述條件的極小點，角度表示非極小點處的可行下降方向的范圍。既然()與()在同一直線上，且方向相反，則必存在一-，f(X*)個實數(shù)，使。Y0,f(X*)-Y，g(X*)0若點處在兩個有效約束邊緣上，比如說X*。在這種情況下的夾角之內(nèi)；如若不然是極小點的相矛盾，如()0和()0。在這種情況下，()必處于g(X*)0g(X*)0,f(X*)12()和()的夾角之內(nèi)；如若不然，點必存在可行下降方向，這與X圖6-16所示。由此可見，如果是極小點，而且點的有XX效約束的梯度()和()線性獨立，則可以將vg(X)Vg(X)12()表示成為()和()的非負(fù)線性組合；也yf(X)vg

7、(X)Vg(X)就是說，存在實數(shù)和，使：Y,0y,012Vf(X*)yVg(X*)yVg(X*)01122如此類推，可以得到：Vf(X*)-工yVg(X*)0jj6-22)爬J為使所有無效約束也同上述有效約束一樣yg(x*)0；y0。如此即可得包含在式(6-22)中，增加約束條件到式(6-23)所示的庫恩-塔克條件(Kuhn-Tucker,當(dāng)g(X*)=0時y,0；當(dāng)g(X*)0時y0簡稱K-T條件，滿足這一條件的點稱為K-T點)。設(shè)是非線性規(guī)劃的極小X*minf(X),g(X)0,j1,2,n點，而且點各有效約束的梯度線性獨立，則存X*在向量(y,y,y)，使下述條件成立：r*(y*,y*,

8、y*)12nVf(X*)-為y*Vg(X*)0jjj1j1,2,n，6-23)y*g(X*)0jjy*0j1,2,n由于等式約束總是有效約束，所以一般形式的非線性規(guī)劃的庫恩-塔克條件可表達(dá)為：設(shè)是X*非線性規(guī)劃minf(X);h(X)0,i1,2,m;g(X)0,j1,2,nij的極小點，而且點的所有有效約束的梯度X和Vh(X*)(i，1,2,m)和*,(*,*,，*)12g(X)(jGJ)j線性獨立，則存在向量使下述條件成立：Vf(X*)一為Vh(X*)一為YVgiiji，1j，16-24)Y*g(X*)，0jjj，1,2,nY*0j，1,2,n式(6-24)中的的和稱為廣義拉格朗日乘子*Y*i