库恩―塔克条件.ppt

《库恩―塔克条件.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、库恩—塔克条件数学规划设如下的数学模型称为数学规划(MathematicalProgramming,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*必满足；若为后者，情况就复杂多了，接下来我们就对这一复杂情况进行分析。一

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

5、）如此类推，可以得到（J是所有有效约束的集合）（7）可能的无效约束处理为使所有无效约束也同上述有效约束一样包含在式（7）中，增加约束条件库恩—塔克条件设X*是非线性规划的极小点，而且X*点各有效约束的梯度线性独立，则存在向量，使下述条件成立：（8）一般形式的库恩-塔克条件由于等式约束总是有效约束，所以一般形式的非线性规划的库恩-塔克条件可表达为：设X*是非线性规划的极小点，而且X*点的所有有效约束的梯度和线性独立，则存在向量和使下述条件成立：一般形式的库恩-塔克条件（9）小结库恩-塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为极值点的必要条

6、件；但一般来讲它并不是充分条件，因此满足这一条件的点并非一定就是极值点。对于凸规划，库恩-塔克条件是极值点存在的充分必要条件。