非线性规划-KT条件

第三讲非线性规划§4约束极值问题(1)问题Jminf(X), [iR二｛x1gj(x)、0,j二⑵ <1>思路:有约束T无约束；非线性T线性；复杂T简；一、最优性条件1.可行下降方向(有用约束，可行方向，下降方向)有用(效)约束设＜1＞式的f(X),g.(X)有一阶连续偏导j设X(0)是一个可行解，下一步考察时，要讨论约束

分析：应有g(X(0))>0T〔gj(X(0))>0j 丨g(X(0))=0若g(X(0))>0,j则在U(X(0))内,有g(X)>0,j此时各个方向均可选.若g.(X(0))=0,则X(0)eg(X)二0形成的边界，影响下一步选向.j

故称g.(X)二0是X(0)点的有效约束.j可行方向(对可行域来说)设X(0)为可行点，P为某方向，若存在—>0,使得X(0)+九PGR,X€[0,九]则称P是X(0)点的一个可行方向.(a)可行方向P与有效约束g(X(o))=0的梯度jVg(X(0))关系是：jVg(X(0))tP>0.记有效约束下标集

J={jIg（X（0））=0,1<j<1}j若P为X（0）的可行方向，则存在九>0,使得当九丘［0,九］,有00g（X（0）+XP）>g（X（0））=0,jeJjj从而dg（X（0）+九P）j- =Vg（X（0））tP>0,jeJd九 jX=0见下图.

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>对有效约束g（X（0））=0,只要九充分小,得j

g(X(0)+XP)>0,所以P是可行方向；jv2>对无效约束g(X(0))>0,同样只要九充分小,j就有g(X(0)+xP)>0,故P也是可行方向；j事实上，对无效g(X(0))>0,VP都是可行方向.j下降方向(对目标函数来说)设X(0)eR,对某P方向,若在九丘[0,九'],九'>000内,有f(X(0)+九P)<f(X(0))

则称P是一个下降方向.下降方向判定：若W(X(0))tP<0,则P是X(°)的一个下降方向.因为f(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,当九w[0,九]时，有00g（X（0）+XP）>0且f（X（0）+九P）<f（X（0））,是继续寻优方向.讨论：X（0）非极小值点o存在可行下降方向p；X（0）极小值点o无可行下降方向p;（可行但不下降，或下降不可行）

定理(局部极(最)小必要条件)设X*是minf(X),Xg{g.(X)>0}局部极小点,if(X),gj(X),jgJ(有效约束下标集)在X*处可微g•(X),j电J在X*处连续，j则在X*处无可行下降方向P，即不存在P,使fvg(X*)TP>0,jgJ,[Vf(x*)tP<0, ()证否则由(**)及前面的分析，可找出可行下降点9X*非局部极小值点T矛盾.

如图

所示f(如图

所示f(X)2.库恩一塔克条件（局部最小的必要条件）是非线性规划中最重要成果之一⑴Gordan引理（不加证明）设A,A，…,A是l个n维向量，则1 2 l

3P，使AtP<0,j=1,2,...,loj3r.>0,不全为零，使£卩A=0.j jjj=1（不指向同侧的向量，正组合为零）（如l=3,n=2）若同侧，则有P（图a）,否则无P（图b）,但可正组为0.

(2)FritzJohn定理设X*是＜1＞极小值点，f(X)和g.(X)有一阶连j续偏导数，则存在不全为零的卩，卩,...,卩，使0i if Vf(X*)Vg(X*)=00 jjj=1'卩g(X*)=0,j=1,2,...,/、卩＞0,j=1,2,...,/j证明因x*是问题V1＞的解，故由定理4,不存在可行下降方向P,使

Vf(X*)TP<0-Vg(X*)tP<0,jGJj由Gordan引理,存在不全为零非负数卩，卩，jGJoj使Vf(X*)—工PVg(X*)=0o jjjGj对无效约束j电J,令卩.二0,则卩Vg(X*)=0j jj从而有(对所有l)

卩Vf(X*)卩Vg(X*)二00 jjj=1且有卩g,(X*)=0,卩'0,j=1,2,...,l，证毕.注1:类似于条件极值的必要条件.注2若卩=0,则有效约束的Vg(X*)正线性相关0 jT同侧T有可行下降方向TX*非极值点.故一般设Vg(X*)线性无关T卩＞0.

j 0以上条件称为FritzJohn条件，X*称为FritzJohn占八、、・

(3)必要条件(库恩-塔克条件)设X*是vl＞极小值点，f(X)和g.(X)有一阶连j续偏导，且有效约束梯度线性无关，则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线性无关j

得卩0＞0,作卩；=气/气〉0,即得＜2＞.式＜2＞=库恩-塔克条件.相应点=库恩-塔克点.简称K-T简称K-T条件,K-T点.对一般非线性规划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=口设X*是＜3＞极小值点，相应函数有一阶连续偏导,

且有效约束的Vh(X*)和Vg(X*),jeJ线性无ijTOC\o"1-5"\h\z关，则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对凸规划,K-T条件也是充分的.

设Xk为某可行解,若Xk是极小点,且gi(Xk)二设Xk为某可行解,若Xk是极小点,和g(Xk)=0,2则Vf(X(k))必与,叫Xk)和Vg2(Xk)同侧，否则有可行下降方向.由Vg(Xk)和Vg(Xk)线性无关12Vf(X*)专叫Xk"叮g2(Xk)

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

minf(x)=-(x-4)2解变为」g(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,引出矛盾，无解；TOC\o"1-5"\h\z1 2若附〉0,附二0:x*=1,点；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所以最大值点x*=1,最大值f(x*)=9.注：f(x)=-(x-4)2非凸函数，在［1,6］上有两个局部最小值点.还有一个”驻点”

附加例题(略)用K-T条件解非线性规划Jminf(x)=(x-3)2[o<x<5 'minf(x)=(x-3)2,解<g(x)=x>0, ,(是凸规划)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,引出矛盾，无解；12若u*工0,u*=0,解得x*=0,u*=-6，非K-T点；TOC\o"1-5"\h\z1 2 1若u*=0，u*工0,解得x*=5,u*=-4,非K-T点;1 2