库恩―塔克条件

库恩—塔克条件数学规划设如下的数学模型称为数学规划(MathematicalProgramming,MP)：约束集或可行域nTnRxxx),...,(1RRqjxhpixgxfnji:,...,1),(;,...,1),();(qjxhpixgtsxfji,...,1,0)(,...,1,0)(..)(min()0,1,...,()0,1,...,injgxipSxRhxjq向量化表达令其中，那么(MP)可简记为或者Tpxgxgxg))(),...,(()(1Tpxhxhxh))(),...,(()(1qnpnRRhRRg:,:min()..0()0fxstg(x)hxmin()xSfx当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。否则，称为约束非线性规划或者约束最优化问题。定义1.设:,,,0nnnfRRxRdRd，若存在0，使()(),(0,)fxtdfxt则称向量d是函数f(x)在点x处的下降方向。定义2设,,,0nnSRxSdRd，若存在0t，使xtdS则称向量d是函数f(x)在点x处关于S的可行方向。定义3.设:,,,0,nnndfRRxRdRded，如果极限0()()lim,fxefxR存在，则称此极限为函数f(x)在点x处的方向导数,记做()fxd有效约束是非线性规划的一个可行解。现考虑某一不等式约束，满足该不等式有两种可能：（1）此时不在由该约束形成的可行域边界上，因此该约束对的微小变动不起限制作用，从而称该约束为无效约束；（2）此时处在由该约束形成的可行域边界上，因此该约束对的微小变动会起某种限制作用，从而称该约束为有效约束。显而易见，所有等式约束都是有效约束。)0(X0)(Xgj0)()0(Xgj0)()0(Xgj可行方向的有效约束若是点的任一可行方向，则对该点所有有效约束均有：(1)其中j代表在点所有有效约束下标的集合0)()0(DXgTj可行方向的有效约束另一方面，由泰勒展开式(2)可知对所有有效约束，当足够小时，只要满足（1）式，则有此外，对点所有的无效约束来讲，由于约束函数的连续性，当足够小时，上式依然成立。从而，只要方向满足式（1），即可保证是点的可行方向。可行下降方向将目标函数在处作一阶泰勒展开，若方向D满足（3）则D必是点的一个下降方向。如果Ｄ方向既是点的一个可行方向又是一个下降方向，就称Ｄ是点的一个可行下降方向。显然，如果某点存在可行下降方向，那么该点就不会是极小点；另一方面，如果某点是极小点，则该点不存在可行下降方向。0)()0(DXfT)0(X)0(X)0(X局部极小值点的性质设X*是非线性规划的一个局部极小点，则在点X*不存在可行下降方向，从而不存在向量D同时满足（4）式（4）的几何意义是十分明显的，即点处满足该条件的方向D与X*点目标函数负梯度方向的夹角为锐角，与X*点所有有效约束梯度方向的夹角也为锐角。0)(DXfT()0TjgXD—Jj两种情况假设X*是非线性规划的极小点，该点可能处于可行域的内部，也可能处于可行域的边缘上。若为前者，该规划问题实质是一个无约束极值问题，X*必满足；若为后者，情况就复杂多了，接下来我们就对这一复杂情况进行分析。0)(Xf一个有效约束边界的情况设X*位于第一个约束所形成的可行域的边缘上，即第一个约束是X*点处的有效约束，。若是极小点，则必与在同一直线上，且方向相反；否则，在X*点处就一定存在可行下降方向。既然与在同一直线上，且方向相反，则必存在一个实数，使（5）0)(1Xg)(1Xg)(Xf1()gX)(Xf01)(Xf0)(11Xg两个有效约束边界的情况若X*点处在两个有效约束边缘上，比如说和。在这种情况下，必处于和的夹角之内；如若不然，X*点必存在可行下降方向，这与X*是极小点的相矛盾。0)(1Xg0)(2Xg)(Xf)(1Xg)(2Xg两个有效约束边界的情况及推广由此可见，如果X*是极小点，而且X*点的有效约束的梯度和线性独立，则可以将表示成为和的非负线性组合；也就是说，存在实数和，使：（6）如此类推，可以得到（J是所有有效约束的集合）（7）)(1Xg)(2Xg)(Xf)(1Xg)(2Xg0102)(11Xg0)(22Xg)(11Xg0)()(XgXfjJjj可能的无效约束处理为使所有无效约束也同上述有效约束一样包含在式（7）中，增加约束条件}0;0)({jjjXg库恩—塔克条件设X*是非线性规划的极小点，而且X*点各有效约束的梯度线性独立，则存在向量，使下述条件成立：（8）},,2,1,0)(),({minnjXgXfj),,,(21n0)()(1XgXfjnjj0)(Xgjjnj,,2,10jnj,,2,1一般形式的库恩-塔克条件由于等式约束总是有效约束，所以一般形式的非线性规划的库恩-塔克条件可表达为：设X*是非线性规划的极小点，而且X*点的所有有效约束的梯度和线性独立，则存在向量和使下述条件成立：},,2,1,0)(;,,2,1,0)();({minnjXgmiXhXfji)(Xhi),,2,1(mi)(Xgj)(Jj),,,(21m),,,(21n一般形式的库恩-塔克条件0)()()(11XgXhXfjnjjimii0)(Xgjjnj,,2,10jnj,,2,1（9）小结库恩-塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为极值点的必要条件；但一般来讲它并不是充分条件，因此满足这一条件的点并非一定就是极值点。对于凸规划，库恩-塔克条件是极值点存在的充分必要条件。