库恩—塔克条件

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

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

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

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

4、所形成的可行域的边缘上，即第一个约束是X*点处的有效约束， 。若是极小点，则 必与 在同一直线上，且方向相反；否则，在X*点处就一定存在可行下降方向 。 既然 与 在同一直线上，且方向相反，则必存在一个实数 ，使 （5）,两个有效约束边界的情况,若X*点处在两个有效约束边缘上，比如说 和 。在这种情况下， 必处于 和 的夹角之内；如若不然，X*点必存在可行下降方向，这与X*是极小点的相矛盾。,两个有效约束边界的情况及推广,由此可见，如果X*是极小点，而且X*点的有效约束的梯度 和 线性独立，则可以将 表示成为 和 的非负线性组合；也就是说，存在实数 和 ，使： （6） 如此类推，可以得到（J是

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