库恩—塔克条件PPT.ppt

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