《最优化方法及应用_郭科_约束问题的最优性条件.doc》由会员分享，可在线阅读，更多相关《最优化方法及应用_郭科_约束问题的最优性条件.doc（7页珍藏版）》请在金锄头文库上搜索。
1、2.7 约束问题的最优性条件所谓最优性条件就是最优化问题的目标函数与约束函数在最优点处满足的充要条件这种条件对于最优化算法的终止判定和最优化理论推证都是至关重要的最优性必要条件是指在最优点处满足哪些条件；充分条件是指满足哪些条件的点是最优点本节仅讲述最基本的结论一、约束最优解对约束优化问题的求解，其目的是在由约束条件所规定的可行域内，寻求一个目标函数值最小的点及其函数值这样的解称为约束最优解约束最优点除了可能落在可行域内的情况外，更常常是在约束边界上或等式约束曲面上，因此它的定义及它的一阶必要条件与无约束优化问题不同（一）约束优化问题的类型约束优化问题根据约束条件类型的不同分为三种，其数学模型
2、如下：（1）不等式约束优化问题（IP型） （2.16）（2）等式约束优化问题（EP型） （3）一般约束优化问题（GP型） （二）约束优化问题的局部解与全局解按一般约束优化问题，其可行域为若对某可行点存在，当与它邻域的点之距离时，总有则称为该约束优化问题的一个局部最优解下面以一个简单例子说明设有该问题的几何图形如图2.8所示从图上的目标函数等值线和不等式约束与等式约束的函数曲线可写出它的两个局部最优解这是因为在点邻域的任一满足约束的点，都有；同理，亦然图2.8对某些约束优化问题，局部解可能有多个在所有的局部最优解中，目标函数值最小的那个解称为全局最优解在上例中，由于，所以全局最优解为由此可知，约
3、束优化问题全局解一定是局部解，而局部解不一定是全局解这与无约束优化问题是相同的二、约束优化问题局部解的一阶必要条件对于约束，现在进一步阐明起作用约束与不起作用约束的概念一般的约束优化问题，其约束包含不等式约束和等式约束在可行点处，如果有，则该约束称可行点的起作用约束；而如果有，则该约束称可行点的不起作用约束对于等式约束，显然在任意可行点处的等式约束都是起作用约束在某个可行点处，起作用约束在的邻域内起到限制可行域范围的作用，而不起作用约束在处的邻域内就不产生影响因此，应把注意力集中在起作用约束上（一）IP型约束问题的一阶必要条件图2.9所示为具有三个不等式约束的二维最优化问题图2.9图2.9（a
4、）是最优点在可行域内部的一种情况在此种情形下，点的全部约束函数值均大于零，所以这组约束条件对其最优点都不起作用换句话说，如果除掉全部约束，其最优点也仍是同一个点因此这种约束优化问题与无约束优化问题是等价的图2.9（b）所示的约束最优点在的边界曲线与目标函数等值线的切点处此时，所以是起作用约束，而其余的两个是不起作用约束既然约束最优点是目标函数等值线与边界的切点，则在点处目标函数的梯度与约束函数梯度矢量必共线，而且方向一致若取非负乘子，则在处存在如下关系另一种情况如图2.9（c）所示当前迭代点在两约束交点上，该点目标函数的梯度矢量夹于两约束函数的梯度矢量之间显然，在点邻近的可行域内部不存在目标函
5、数值比更小的可行点因此，点就是约束最优点，记作由图可知，此时点目标函数的梯度可表达为约束函数梯度和的线性组合若用代替即有成立，且式中的乘子和必为非负总结以上各种情况，最优解的一阶必要条件为对于（2.16）IP型约束问题的一阶必要条件讨论如下：设最优点位于个约束边界的汇交处，则这个约束条件组成一个起作用的约束集按上面的分析，对于点必有下式成立 （2.17）但是在实际求解过程中，并不能预先知道最优点位于哪一个或哪几个约束边界的汇交处为此，把个约束全部考虑进去，并取不起作用约束的相应乘子为零，则最优解的一阶必要条件应把式（2.17）修改为 （2.18）式（2.18）为IP型问题约束最优解的一阶必要条
6、件，它与式（2.17）等价因为在下，对于起作用约束，必有使式（2.18）中的第四式成立；对于不起作用约束，虽然而必有，可见式（2.18）与式（2.17）等价（二）EP型约束问题的一阶必要条件图2.10所示为具有一个等式约束条件的二维化问题，其数学模型为在该问题中，等式约束曲线是它的可行域，而且目标函数等值线与约束曲线的切点是该约束问题的最优解图2.10在点处，目标函数的梯度与约束函数的梯度共线因此，在最优点处一定存在一个乘子，使得成立对于一般的维等式约束优化问题，其数学模型为则为其解的一阶必要条件为（三）GP型约束问题解的一阶必要条件由上述不等式约束优化与等式约束优化问题的一阶必要条件，可以推
7、出一般约束优化问题的条件设维一般约束优化问题的数学模型为 （2.19）则为其解的一阶必要条件应为 （2.20）函数称为关于问题（2.19）的广义拉格朗日函数，式中，为拉格朗日乘子由于引入拉格朗日函数，条件（2.20）中的第一式可写为（四）KuhnTcker条件（简称KT条件）在优化实用计算中，常常需要判断某可行迭代点是否可作为约束最优点输出而结束迭代，或者对此输出的可行结果进行检查，观察它是否已满足约束最优解的必要条件，这种判断或检验通常借助于条件进行的对于IP型问题，条件可叙述如下：如果是一个局部极小点 ，且各梯度矢量组成线性无关的矢量系，那么必存在一组非负乘子，使得成立必须指出，在一般情形
8、下，条件是判别约束极小点的一阶必要条件，但并非充分条件只是对于凸规划问题，即对于目标函数为凸函数，可行域为凸集的最优化问题，条件才是约束最优化问题的充分条件而且，在这种情况下的局部最优解也必为全局最优解应用条件检验某迭代点是否为约束最优点的具体作法可按下述步骤进行：（1）检验是否为可行点为此需要计算处的诸约束函数值，若是可行点，则（2）选出可行点处的起作用约束前面已求得个值，其中等于零或相当接近零的约束就是起作用约束把这些起作用约束重新编排成序列（3）计算点目标函数的梯度和I个起作用约束函数的梯度（4）按条件，点应满足.(2.21）将式（2.21）中的各梯度矢量用其分量表示，则可得到为变量的线
9、性方程组由于矢量系是线性无关的，所以该方程组存在唯一解通过解此线性方程组，求得一组乘子，若所有乘子均为非负，即，则即为约束最优解否则，点就不是约束最优点例2.9 设约束优化问题它的当前迭代点为，试用条件判别它是否为约束最优点解：（1）计算点的诸约束函数值是可行点（2）点起作用约束是（3）求点梯度（4）求拉格朗日乘子按条件应有写成线性方程组解得乘子均为非负，故满足约束最优解的一阶必要条件如图2.11所示，点确为该约束优化问题的局部最优解，由于可行域是凸集，所以点也是该问题的全局最优解图2.11GP型的约束最优化问题的条件类似于IP型约束最优化问题的条件：如果是一个局部极小点 ，且各梯度矢量和组成线性无关的矢量系，那么必存在两组乘子和，使得 （2.22）成立三、约束优化问题局部解的二阶充分条件GP型的约束最优化问题的极小点的二阶充分条件是：设对条件和是可行的，若存在向量和，它们满足条件（2.22），而且对满足条件 （2.23）的任意非零向量有，则为GP型的约束最优化问题的严格局部极小点这里当然要求
