库恩—塔克条件.ppt

库恩—塔克条件.ppt库恩—塔克条件数学规划设如下的数学模型称为数学规划(MathematicalProgramming,MP):约束集或可行域向量化表达令其中,那么(MP)可简记为或者当p=0,q=0时,称为无约束非线性规划或者无约束最优化问题。否则,称为约束非线性规划或者约束最优化问题。有效约束是非线性规划的一个可行解。现考虑某一不等式约束,满足该不等式有两种可能:(1)此时不在由该约束形成的可行域边界上,因此该约束对的微小变动不起限制作用,从而称该约束为无效约束;(2)此时处在由该约束形成的可行域边界上,因此该约束对的微小变动会起某种限制作用,从而称该约束为有效约束。显而易见,所有等式约束都是有效约束。可行方向的有效约束若是点的任一可行方向,则对该点所有有效约束均有:(1)其中j代表在点所有有效约束下标的集合可行方向的有效约束另一方面,由泰勒展开式(2)可知对所有有效约束,当足够小时,只要满足(1)式,则有此外,对点所有的无效约束来讲,由于约束函数的连续性,当足够小时,上式依然成立。从而,只要方向满足式(1),即可保证是点的可行方向。可行下降方向将目标函数在处作一阶泰勒展开,若方向D满足(3)则D必是点的一个下降方向。如果D方向既是点的一个可行方向又是一个下降方向,就称D是点的一个可行下降方向。显然,如果某点存在可行下降方向,那么该点就不会是极小点;另一方面,如果某点是极小点,则该点不存在可行下降方向。局部极小值点的性质设X*是非线性规划的一个局部极小点,则在点X*不存在可行下降方向,从而不存在向量D同时满足(4)式(4)的几何意义是十分明显的,即点处满足该条件的方向D与X*点目标函数负梯度方向的夹角为锐角,与X*点所有有效约束梯度方向的夹角也为锐角。两种情况假设X*是非线性规划的极小点,该点可能处于可行域的内部,也可能处于可行域的边缘上。若为前者,该规划问题实质是一个无约束极值问题,X*必满足;若为后者,情况就复杂多了,接下来我们就对这一复杂情况进行分析。