库恩塔克条件

《库恩塔克条件》由会员分享，可在线阅读，更多相关《库恩塔克条件（19页珍藏版）》请在金锄头文库上搜索。

1、库恩塔克条件数学规划n设 如下的数学模型称为数学规划(Mathematical Programming, MP)： 约束集或可行域约束集或可行域向量化表达n令 n其中， 那么(MP)可简记为 或者 当p=0,q=0时，称为无约束非线性规划无约束非线性规划或者无约无约束最优化问题。束最优化问题。否则，称为约束非线性规划约束非线性规划或者约束最优化问题约束最优化问题。有效约束n 是非线性规划的一个可行解。现考虑某一不等式约束 ，满足该不等式有两种可能：（1） 此时不在由该约束形成的可行域边界上，因此该约束对的微小变动不起限制作用，从而称该约束为无效约束无效约束；（2） 此时处在由该约束形成的可行域

2、边界上，因此该约束对的微小变动会起某种限制作用，从而称该约束为有效约束有效约束。 显而易见，所有等式约束都是有效约束。 可行方向的有效约束n若是点的任一可行方向，则对该点所有有效约束均有： (1) 其中j代表在点所有有效约束下标的集合 可行方向的有效约束n另一方面，由泰勒展开式 (2) 可知对所有有效约束，当足够小时，只要满足（1）式，则有 此外，对点所有的无效约束来讲，由于约束函数的连续性，当足够小时，上式依然成立。从而，只要方向满足式（1），即可保证是点的可行方向。 可行下降方向n将目标函数在处作一阶泰勒展开，若方向D满足 （3） 则D必是 点的一个下降方向。n如果方向既是点的一个可行方向

3、又是一个下降方向，就称是点的一个可行下降方向可行下降方向。显然，如果某点存在可行下降方向，那么该点就不会是极小点；另一方面，如果某点是极小点，则该点不存在可行下降方向。局部极小值点的性质n设X*是非线性规划的一个局部极小点，则在点X*不存在可行下降方向，从而不存在向量D同时满足 （4） 式（4）的几何意义是十分明显的，即点处满足该条件的方向方向D与X*点目标函数负梯度方向目标函数负梯度方向的夹角为锐角，与X*点所有有效约束梯度方向有效约束梯度方向的夹角也为锐角。 两种情况n假设X*是非线性规划的极小点，该点可能处于可行域的内部，也可能处于可行域的边缘上。若为前者，该规划问题实质是一个无约束极值

4、问题，X*必满足 ；若为后者，情况就复杂多了，接下来我们就对这一复杂情况进行分析。 一个有效约束边界的情况n设X*位于第一个约束所形成的可行域的边缘上，即第一个约束是X*点处的有效约束， 。若是极小点，则 必与 在同一直线上，且方向相反；否则，在X*点处就一定存在可行下降方向 。n既然 与 在同一直线上，且方向相反，则必存在一个实数 ，使n （5）两个有效约束边界的情况n若X*点处在两个有效约束边缘上，比如说 和 。在这种情况下， 必处于 和 的夹角之内；如若不然，X*点必存在可行下降方向，这与X*是极小点的相矛盾。两个有效约束边界的情况及推广n由此可见，如果X*是极小点，而且X*点的有效约束

5、的梯度 和 线性独立，则可以将 表示成为 和 的非负线性组合；也就是说，存在实数 和 ，使： （6）如此类推，可以得到（J是所有有效约束的集合） （7）可能的无效约束处理n为使所有无效约束也同上述有效约束一样包含在式（7）中，增加约束条件 库恩塔克条件n设X*是非线性规划 的极小点，而且X*点各有效约束的梯度线性独立，则存在向量 ，使下述条件成立： （8） 一般形式的库恩-塔克条件 n由于等式约束总是有效约束，所以一般形式的非线性规划的库恩-塔克条件可表达为：设X*是非线性规划 的极小点，而且X*点的所有有效约束的梯度 和 线性独立，则存在向量 和 使下述条件成立： 一般形式的库恩-塔克条件（9）小结n库恩-塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为极值点的必要条件必要条件；但一般来讲它并不是充分条件不是充分条件，因此满足这一条件的点并非一定就是极值点。对于凸规划凸规划，库恩-塔克条件是极值点存在的充分必要条件充分必要条件。