库恩-塔克条件.ppt

四*、非线性规划第7章无约束问题第8章约束极值问题清华大学出版社第8章约束极值问题第1节最优性条件第2节二次规划第3节可行方向法第4节制约函数法清华大学出版社第1节最优性条件大多数极值问题其变量的取值都会受到一定限制,这种限制由约束条件来体现。带有约束条件的极值问题称为约束极值问题。非线性规划的一般形式为或问题(7-2)也常写成(7-1)(7-2)(7-3),假定f(X)、hi(X)和具有一阶连续偏导数。设是非线性规划的一个可行解。现考虑某一不等式约束条件满足它有两种可能:其一为,这时,点不是处于由这一约束条件形成的可行域边界上,因而这一约束对点的微小摄动不起限制作用,从而称这个约束条件是点的不起作用约束(或无效约束);其二是,这时点处于该约束条件形成的可行域边界上,它对的摄动起到了某种限制作用,故称这个约束是点的起作用约束(有效约束)。显而易见,等式约束对所有可行点来说都是起作用约束。清华大学出版社第1节最优性条件假定X(0)是非线性规划(7-3)式的一个可行点,现考虑此点的某一方向D,若存在实数,使对任意均有就称方向D是X(0)点的一个可行方向。清华大学出版社第1节最优性条件若D是可行点X(0)处的任一可行方向,则对该点的所有起作用约束均有其中J为这个点所有起作用约束下标的集合。另一方面,由泰勒公式对所有起作用约束,当λ>0足够小时,只要就有此外,对X(0)点的不起作用约束,由约束函数的连续性,当λ>0足够小时亦有上式成立。从而,只要方向D满足(7-6)式,即可保证它是X(0)点的可行方向。图7-1(7-5)(7-6)清华大学出版社第1节最优性条件考虑非线性规划的某一可行点X(0),对该点的任一方向D来说,若存在实数,使对任意均有就称方向D为X(0)点的一个下降方向。将目标函数f(X)在点X(0)处作一阶泰勒展开,可知满足条件的方向D必为X(0)点的下降方向。如果方向D既是X(0)点的可行方向,又是这个点的下降方向,就称它是该点的可行下降方向。假如X(0)点不是极小点,继续寻优时的搜索方向就应从该点的可行下降方向中去找。显然,若某点存在可行下降方向,它就不会是极小点。另一方面,若某点为极小点,则在该点不存在可行下降方向。清华大学出版社第1节最优性条件定理1设X*是非线性规划(7-3)式的一个局部极小点,目标函数f(X)在X*处可微,而且在X*处可微,当在X*处连续,当则在X*不存在可行下降方向,从而不存在向量D同时满足:-塔克条件假定X*是非线性规划(7-3)式的极小点,该点可能位于可行域的内部,也可能处于可行域的边界上。若为前者,这事实上是个无约束问题,X*必满足条件若为后者,情况就复杂得多了。下面讨论当极小点位于可行域边界的情形。清华大学出版社第1节最优性条件不失一般性,设X*位于第一个约束条件形成的可行域边界上,即第一个约束条件是X*点的起作用约束()。若X*是极小点,则必与在一条直线上且方向相反。否则,在该点就一定存在可行下降方向(图7-2中的X*点为极小点;X点不满足上述要求,它不是极小点,角度β表示了该点可行下降方向的范围)。上面的论述说明,在上述条件下,存在实数,使清华大学出版社