非線性規(guī)劃-KT條件

第三講非線性規(guī)劃§4約束極值問(wèn)題(1)問(wèn)題Jminf(X), [iR二｛x1gj(x)、0,j二⑵ <1>思路:有約束T無(wú)約束；非線性T線性；復(fù)雜T簡(jiǎn)；一、最優(yōu)性條件1.可行下降方向(有用約束，可行方向，下降方向)有用(效)約束設(shè)＜1＞式的f(X),g.(X)有一階連續(xù)偏導(dǎo)j設(shè)X(0)是一個(gè)可行解，下一步考察時(shí)，要討論約束

分析：應(yīng)有g(shù)(X(0))>0T〔gj(X(0))>0j 丨g(X(0))=0若g(X(0))>0,j則在U(X(0))內(nèi),有g(shù)(X)>0,j此時(shí)各個(gè)方向均可選.若g.(X(0))=0,則X(0)eg(X)二0形成的邊界，影響下一步選向.j

故稱g.(X)二0是X(0)點(diǎn)的有效約束.j可行方向(對(duì)可行域來(lái)說(shuō))設(shè)X(0)為可行點(diǎn)，P為某方向，若存在—>0,使得X(0)+九PGR,X€[0,九]則稱P是X(0)點(diǎn)的一個(gè)可行方向.(a)可行方向P與有效約束g(X(o))=0的梯度jVg(X(0))關(guān)系是：jVg(X(0))tP>0.記有效約束下標(biāo)集

J={jIg（X（0））=0,1<j<1}j若P為X（0）的可行方向，則存在九>0,使得當(dāng)九丘［0,九］,有00g（X（0）+XP）>g（X（0））=0,jeJjj從而dg（X（0）+九P）j- =Vg（X（0））tP>0,jeJd九 jX=0見(jiàn)下圖.

gg?(X(0))=0（b）反之，若Vg（X（0））TP>0,則P必為可行方向.j???g（X（0）+入P）=g（X（0））+XVg（X（0））tP+o（九）<1>對(duì)有效約束g（X（0））=0,只要九充分小,得j

g(X(0)+XP)>0,所以P是可行方向；jv2>對(duì)無(wú)效約束g(X(0))>0,同樣只要九充分小,j就有g(shù)(X(0)+xP)>0,故P也是可行方向；j事實(shí)上，對(duì)無(wú)效g(X(0))>0,VP都是可行方向.j下降方向(對(duì)目標(biāo)函數(shù)來(lái)說(shuō))設(shè)X(0)eR,對(duì)某P方向,若在九丘[0,九'],九'>000內(nèi),有f(X(0)+九P)<f(X(0))

則稱P是一個(gè)下降方向.下降方向判定：若W(X(0))tP<0,則P是X(°)的一個(gè)下降方向.因?yàn)閒(X)二f(X(0)+九P)二f(X(0))+XVf(X(0))tP+0(九),只要九充分小，都有f(X)<f(X(o)).可行下降方向若X(0)eR的某方向P是可行方向+下降方向，則稱P是X(0)的可行下降方向.

即存在九>0,當(dāng)九w[0,九]時(shí)，有00g（X（0）+XP）>0且f（X（0）+九P）<f（X（0））,是繼續(xù)尋優(yōu)方向.討論：X（0）非極小值點(diǎn)o存在可行下降方向p；X（0）極小值點(diǎn)o無(wú)可行下降方向p;（可行但不下降，或下降不可行）

定理(局部極(最)小必要條件)設(shè)X*是minf(X),Xg{g.(X)>0}局部極小點(diǎn),if(X),gj(X),jgJ(有效約束下標(biāo)集)在X*處可微g?(X),j電J在X*處連續(xù)，j則在X*處無(wú)可行下降方向P，即不存在P,使fvg(X*)TP>0,jgJ,[Vf(x*)tP<0, ()證否則由(**)及前面的分析，可找出可行下降點(diǎn)9X*非局部極小值點(diǎn)T矛盾.

如圖

所示f(如圖

所示f(X)2.庫(kù)恩一塔克條件（局部最小的必要條件）是非線性規(guī)劃中最重要成果之一⑴Gordan引理（不加證明）設(shè)A,A，…,A是l個(gè)n維向量，則1 2 l

3P，使AtP<0,j=1,2,...,loj3r.>0,不全為零，使￡卩A=0.j jjj=1（不指向同側(cè)的向量，正組合為零）（如l=3,n=2）若同側(cè)，則有P（圖a）,否則無(wú)P（圖b）,但可正組為0.

(2)FritzJohn定理設(shè)X*是＜1＞極小值點(diǎn)，f(X)和g.(X)有一階連j續(xù)偏導(dǎo)數(shù)，則存在不全為零的卩，卩,...,卩，使0i if Vf(X*)Vg(X*)=00 jjj=1'卩g(X*)=0,j=1,2,...,/、卩＞0,j=1,2,...,/j證明因x*是問(wèn)題V1＞的解，故由定理4,不存在可行下降方向P,使

Vf(X*)TP<0-Vg(X*)tP<0,jGJj由Gordan引理,存在不全為零非負(fù)數(shù)卩，卩，jGJoj使Vf(X*)—工PVg(X*)=0o jjjGj對(duì)無(wú)效約束j電J,令卩.二0,則卩Vg(X*)=0j jj從而有(對(duì)所有l(wèi))

卩Vf(X*)卩Vg(X*)二00 jjj=1且有卩g,(X*)=0,卩'0,j=1,2,...,l，證畢.注1:類似于條件極值的必要條件.注2若卩=0,則有效約束的Vg(X*)正線性相關(guān)0 jT同側(cè)T有可行下降方向TX*非極值點(diǎn).故一般設(shè)Vg(X*)線性無(wú)關(guān)T卩＞0.

j 0以上條件稱為FritzJohn條件，X*稱為FritzJohn占八、、?

(3)必要條件(庫(kù)恩-塔克條件)設(shè)X*是vl＞極小值點(diǎn)，f(X)和g.(X)有一階連j續(xù)偏導(dǎo)，且有效約束梯度線性無(wú)關(guān)，則3^*,...,附,使1 l'Vf(X*)^*Vg(X*)=0jjj=1<H*g(X*)=0,j=1,2,...,l<2>jj、H*>0,j=1,2,...,lj證明由FritzJohn引理，Vg(X*)jwJ線性無(wú)關(guān)j

得卩0＞0,作卩；=氣/氣〉0,即得＜2＞.式＜2＞=庫(kù)恩-塔克條件.相應(yīng)點(diǎn)=庫(kù)恩-塔克點(diǎn).簡(jiǎn)稱K-T簡(jiǎn)稱K-T條件,K-T點(diǎn).對(duì)一般非線性規(guī)劃minf(X), _<h(X)=0,i=1,mng(X)>0,j二口vj它的K-T條件如下'minf(X),h(X)>0,-h(X)>0,i=0<3>g(X)>0,j=口設(shè)X*是＜3＞極小值點(diǎn)，相應(yīng)函數(shù)有一階連續(xù)偏導(dǎo),

且有效約束的Vh(X*)和Vg(X*),jeJ線性無(wú)ijTOC\o"1-5"\h\z關(guān)，則3r*二(y*,y*Y*)T和M*=(y*y*)T,1 2 m 1 l使Vf(X*)—遲y*Vh(X*)—工y*Vg(X*)=0ii jj\o"CurrentDocument"i=l j=l\o"CurrentDocument"y*g(X*)=0,j=1,2,...,l <4>jjy*>0,j=1,2,...,lj其中y*,y*，…,y*,y*，…，y*稱為廣義Lagrange乘子.1 2 m1 l注1對(duì)凸規(guī)劃,K-T條件也是充分的.

設(shè)Xk為某可行解,若Xk是極小點(diǎn),且gi(Xk)二設(shè)Xk為某可行解,若Xk是極小點(diǎn),和g(Xk)=0,2則Vf(X(k))必與,叫Xk)和Vg2(Xk)同側(cè)，否則有可行下降方向.由Vg(Xk)和Vg(Xk)線性無(wú)關(guān)12Vf(X*)專叫Xk"叮g2(Xk)

Vf(X*)—pVg(Xk)—pVg(Xk)二01 46

minf(x)=-(x-4)2解變?yōu)椤筭(x)=x-1>0 ,1g(x)=6一x>0J2Vf(x)=-2(x—4),Vg(x)=1,Vg(x)=-1,12引入廣義拉格朗日乘子卩:，巴,則有—2(x:—4)—p：+p：=012p：p：(x：—1)=01p：(6—x：)=02具體分析如下.p：,p：>012

若屮〉0,卩>0,引出矛盾，無(wú)解；TOC\o"1-5"\h\z1 2若附〉0,附二0:x*=1,點(diǎn)；f(x*)二9(附二6)1 2 1若卩*=0,卩*=0:x*=4,f(x*)=0；1 2若卩*=0,|H*>0：x*=6,f(x*)=4(|LI*=4)1 2 2所以最大值點(diǎn)x*=1,最大值f(x*)=9.注：f(x)=-(x-4)2非凸函數(shù)，在［1,6］上有兩個(gè)局部最小值點(diǎn).還有一個(gè)”駐點(diǎn)”

附加例題(略)用K-T條件解非線性規(guī)劃Jminf(x)=(x-3)2[o<x<5 'minf(x)=(x-3)2,解<g(x)=x>0, ,(是凸規(guī)劃)g(x)=5-x>012Vf(x)=2(x-3),Vg(x)=1,Vg(x)=-1,12

2(x*-3)_比+比=012u*x*=0所以＜1 ,具體分析如下.U*(5—x*)=02u*,u*n0V12若u*工0,u*工0,引出矛盾，無(wú)解；12若u*工0,u*=0,解得x*=0,u*=-6，非K-T點(diǎn)；TOC\o"1-5"\h\z1 2 1若u*=0，u*工0,解得x*=5,u*=-4,非K-T點(diǎn);1 2