库恩塔克定理

1、6-1最优性条件现考虑一般形式的非线性规划数学模型minf(X),XEnh(X)=0,(i=1,2,m)iLg(X)，0,(j=1,2,l)假设()、()和()均具有一阶连续偏导f(X)h(X)g(X)数，是非线性规划的一个可行解。现考虑某一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、所有等式约束都是有效约束。是非线性规划的一个可行解，对于此点的X(0)某一方向，若存在实数00使任意“均D000,0有，就称方向是点的一个可行方X(0)DRDX(0)向，此处代表非线性规划的可行域。R若是(0)点的任一可行方向，则对该点所有DX(0)有效约束均有：g(X)，0jjJVg(X(0)TD,0j（6-18）其中代表在点所有有效约束下标的集合，如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可知对所有有效约束，当兀足够小时，只要0Vg（X（0）T

3、D0，j（6-19）就有九,g(X(0)D),0jGJ此外，对点所有的无效约束来讲，由于约X(0)束函数的连续性，当九足够小时，上式依然成0立。从而，只要方向满足式(6-19)，即可保证D是点的可行方向。DX(0)非线性规划的某一可行点，对该点的任一X(0)方向来说，若存在实数心使任意九R均有00G0,0九，就称方向是点的一个下降方f(X(0)D)f(X(0)DX(0)向。将目标函数()在处作一阶泰勒展开，若f(X)X(0)方向满足DVf(X(0)TD0(6-20)则必是点的一个下降方向。DX(0)如果方向既是点的一个可行方向又是DX(0)一个下降方向，就称是点的一个可行下降方DX(0)向。显

4、然，如果某点存在可行下降方向，那么该点就不会是极小点；另一方面，如果某点是极小点，则该点不存在可行下降方向。定理3设是非线性规划的一个局部极小X*点，目标函数()在处可微，而且f(X)X*()在处可微，当时g(X)X*jGJ()在处连续，当时g(X)Xj纟JTOC o 1-5 h z(此处代表在处有效约束的下标集合)则在JX点不存在可行下降方向，从而不存在向量同XD时满足6-21)事实上，若在点存在向量满足式(6-21)，XD则从点出发沿方向搜索可找到比点更好的XDX点，这与点是一个局部极小点的假设相矛盾；X所以这个定理是显然成立的。式(6-21)的几何意义是十分明显的，即点X处满足该条件的方

5、向与点目标函数负梯度方DX向的夹角为锐角，与点所有有效约束梯度方向X的夹角也为锐角。假设是非线性规划的极小点，该点可能处X于可行域的内部，也可能处于可行域的边缘上。若为前者，该规划问题实质是一个无约束极值问题，必满足()0；若为后者，情况就复杂多XVf(X)0了，接下来我们就对这一复杂情况进行分析。不失一般性，设位于第一个约束所形成的X可行域的边缘上，即第一个约束是点处的有效X约束，()0。若是极小点，则()必与()g(X*)0X*,g(X*)-,f(X*)在同一直线上，且方向相反(这里假定()和，g(X*)()皆不为“0”)；否则，在点处就一定存在可f(X*)X*行下降方向，如图6-15所示

6、。图6-15中的点X*是满足上述条件的极小点，角度表示非极小点处的可行下降方向的范围。既然()与()在同一直线上，且方向相反，则必存在一-，f(X*)个实数，使。Y0,f(X*)-Y，g(X*)0若点处在两个有效约束边缘上，比如说X*。在这种情况下的夹角之内；如若不然是极小点的相矛盾，如()0和()0。在这种情况下，()必处于g(X*)0g(X*)0,f(X*)12()和()的夹角之内；如若不然，点必存在可行下降方向，这与X图6-16所示。由此可见，如果是极小点，而且点的有XX效约束的梯度()和()线性独立，则可以将vg(X)Vg(X)12()表示成为()和()的非负线性组合；也yf(X)vg

7、(X)Vg(X)就是说，存在实数和，使：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,当g(X*)=0时y,0；当g(X*)0时y0简称K-T条件，满足这一条件的点称为K-T点)。设是非线性规划的极小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由于等式约束总是有效约束，所以一般形式的非线性规划的库恩-塔克条件可表达为：设是X*非线性规划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