库恩—塔克条件.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,库恩,塔克条件,数学规划,设,如下的数学模型称为数学规划,(Mathematical Programming,MP),：,约束集或可行域,向量化表达,令,其中，那么,(MP),可简记为,或者,当,p=0,q=0,时，称为,无约束非线性规划,或者,无约束最优化问题。,否则，称为,约束非线性规划,或者,约束最优化问题,。,有效约束,是非线性规划的一个可行解。现考虑某一不等式约束 ，满足该不等式有两种可能：,（,1,）此时不在由该约束形成的可行域边界上，因此该约束对的微小变动不起限制作用，从而称该约束为,无效约束,；,（,2,）此时处在由该约束形成的可行域边界上，因此该约束对的微小变动会起某种限制作用，从而称该约束为,有效约束,。,显而易见，所有等式约束都是有效约束。,可行方向的有效约束,若是点的任一可行方向，则对该点所有有效约束均有：,(1),其中,j,代表在点所有有效约束下标的集合,局部极小值点的性质,设,X*,是非线性规划的一个局部极小点，则在点,X*,不存在可行下降方向，从而不存在向量,D,同时满足,（,4,）,式（,4,）的几何意义是十分明显的，即点处满足该条件的,方向,D,与,X*,点,目标函数负梯度方向,的夹角为锐角，与,X*,点所有,有效约束梯度方向,的夹角也为锐角。,两种情况,假设,X*,是非线性规划的极小点，该点可能处于可行域的内部，也可能处于可行域的边缘上。若为前者，该规划问题实质是一个无约束极值问题，,X*,必满足 ；若为后者，情况就复杂多了，接下来我们就对这一复杂情况进行分析。,一个有效约束边界的情况,设,X*,位于第一个约束所形成的可行域的边缘上，即第一个约束是,X*,点处的有效约束，。若是极小点，则 必与 在同一直线上，且方向相反；否则，在,X*,点处就一定存在可行下降方向。,既然 与 在同一直线上，且方向相反，则必存在一个实数 ，使,（,5,）,两个有效约束边界的情况,若,X*,点处在两个有效约束边缘上，比如说 和 。在这种情况下，必处于 和,的夹角之内；如若不然，,X*,点必存在可行下降方向，这与,X*,是极小点的相矛盾。,两个有效约束边界的情况及推广,由此可见，如果,X*,是极小点，而且,X*,点的有效约束的梯度 和 线性独立，则可以将,表示成为 和 的非负线性组合；也就是说，存在实数 和 ，使：,（,6,）,如此类推，可以得到,（,J,是所有有效约束的集合,）,（,7,）,可能的无效约束处理,为使所有无效约束也同上述有效约束一样包含在式（,7,）中，增加约束条件,库恩,塔克条件,设,X*,是非线性规划,的极小点，而且,X*,点各有效约束的梯度线性独立，则存在向量 ，使下述条件成立：,（,8,）,一般形式的库恩,-,塔克条件,由于等式约束总是有效约束，所以一般形式的非线性规划的库恩,-,塔克条件可表达为：设,X*,是非线性规划,的极小点，而且,X*,点的所有有效约束的梯度,和 线性独立，则存在向量,和 使下述条件成立：,一般形式的库恩,-,塔克条件,（,9,）,小结,库恩,-,塔克条件是非线性规划领域中最重要的理论成果之一，是确定某点为极值点的,必要条件,；但一般来讲它并,不是充分条件,，因此满足这一条件的点并非一定就是极值点。对于,凸规划,，库恩,-,塔克条件是极值点存在的,充分必要条件,。,