最优化方法及应用_郭科_约束问题的最优性条件.doc

1、2.7 约束问题的最优性条件所谓最优性条件就是最优化问题的目标函数与约束函数在最优点处满足的充要条件这种条件对于最优化算法的终止判定和最优化理论推证都是至关重要的最优性必要条件是指在最优点处满足哪些条件；充分条件是指满足哪些条件的点是最优点本节仅讲述最基本的结论一、约束最优解对约束优化问题的求解，其目的是在由约束条件所规定的可行域 D内，寻求一个目标函数值最小的点 *X及其函数值 )(*Xf这样的解 )(,*Xf称为约束最优解约束最优点除了可能落在可行域 D内的情况外，更常常是在约束边界上或等式约束曲面上，因此它的定义及它的一阶必要条件与无约束优化问题不同（一）约束优化问题的类型约束优化问题根

2、据约束条件类型的不同分为三种，其数学模型如下：（1）不等式约束优化问题（IP 型） min(),.012ifXstgil， ， ， ， （2.16）（2）等式约束优化问题（EP 型）in().012jfsthXjm， ， ， ， ， （3）一般约束优化问题（GP 型）mi().012ijfgilsthj， ， ， ， ， ， ， ， ， （二）约束优化问题的局部解与全局解按一般约束优化问题，其可行域为 0)(21)(| mjXhliXgDji ，；， 若对某可行点 *存在 0，当 *与它邻域的点 之距离 |*时，总有)(*fXf则称 为该约束优化问题的一个局部最优解下面以一个简单例子说明设有

3、， ， 09)2().1min12xXhgtsf该 问 题 的 几 何 图 形 如 图 2.8 所 示 从 图 上 的 目 标 函 数 等 值 线 和 不 等 式 约 束 与 等 式 约 束 的 函 数曲 线 可 写 出 它 的 两 个 局 部 最 优 解 TT50*1， 这 是 因 为 在 *1X点 邻 域 的 任一 满 足 约 束 的 点 X， 都 有 )()ff； 同 理 ， 2亦 然 图 2.8对某些约束优化问题，局部解可能有多个在所有的局部最优解中，目标函数值最小的那个解称为全局最优解在上例中，由于 16)(4)(*2*1Xff， ，所以全局最优解为 )(*1Xf， 由此可知，约束优

4、化问题全局解一定是局部解，而局部解不一定是全局解这与无约束优化问题是相同的二、约束优化问题局部解的一阶必要条件对于约束，现在进一步阐明起作用约束与不起作用约束的概念一般的约束优化问题，其约束包含不等式约束 liXgi ， 210)(和等式约束 mjXhj ， 210)(在可行点 k处，如果有 0)(kiXg，则该约束 )(Xgi称可行点 k的起作用约束；而如果有 )(i，则该约束 称可行点 k的不起作用约束对于等式约束 )(hj，显然在任意可行点处的等式约束都是起作用约束在某个可行点 k处，起作用约束在 k的邻域内起到限制可行域范围的作用，而不起作用约束在 处的邻域内就不产生影响因此，应把注意

5、力集中在起作用约束上（一）IP 型约束 问题的一阶必要条件图 2.9 所示为具有三个不等式约束的二维最优化问题图 2.9图 2.9（a）是最优点 *X在可行域内部的一种情况在此种情形下， *X点的全部约束函数值 )(*gi均大于零 )321(，i，所以这组约束条件对其最优点 都不起作用换句话说，如果除掉全部约束，其最优点也仍是同一个 *X点因此这种约束优化问题与无约束优化问题是等价的图 2.9（b）所示的约束最优点 在 )(1g的边界曲线与目标函数等值线的切点处此时， 00)(0)(32*1 gg，所以 )(1g是起作用约束，而其余的两个是不起作用约束既然约束最优点 *X是目标函数等值线与 1

6、边界的切点，则在 *X点处目标函数的梯度 )(*f与约束函数梯度矢量 )(*X必共线，而且方向一致若取非负乘子0*1，则在 处存在如下关系 01gf另一种情况如图 2.9（c）所示当前迭代点 k在两约束交点上，该点目标函数的梯度矢量 )(kXf夹于两约束函数的梯度矢量 )()(2k， 之间显然，在 kX点邻近的可行域内部不存在目标函数值比 )(kXf更小的可行点因此，点 k就是约束最优点，记作*由图可知，此时 k点目标函数的梯度 kf可表达为约束函数梯度 )(1kg和)(2kg的线性组合若用 *代替 k即有 )()()( *2*1gf成立，且式中的乘子 *1和 2必为非负总结以上各种情况，最优

7、解的一阶必要条件为 ， ，210)(0)()(*21*iXgfiiii对于（2.16）IP 型约束问题的一阶必要条件讨论如下：设最优点 *X位于 j个约束边界的汇交处，则这 j个约束条件组成一个起作用的约束集按上面的分析，对于 *点必有下式成立 ， ，jiXggfiijii210)(0)()(*1*（2.17）但是在实际求解过程中，并不能预先知道最优点 *位于哪一个或哪几个约束边界的汇交处为此，把 l个约束全部考虑进去，并取不起作用约束的相应乘子为零，则最优解的一阶必要条件应把式（2.17）修改为 ， ， liXggfiilii210)(0)()(*1*（2.18）式（2.18）为 IP 型问

8、题约束最优解的一阶必要条件，它与式（2.17）等价因为在 *X下，对于起作用约束，必有 liXgi ， 210)(*使式（2.18）中的第四式成立；对于不起作用约束，虽然 i而必有*i，可见式（2.18 ）与式（2.17）等价（二）EP 型约束问题的一阶必要条件图 2.10 所示为具有一个等式约束条件的二维化问题，其数学模型为 ， 0)(.minXhtsf在该问题中，等式约束曲线 是它的可行域，而且目标函数等值线 CXf)(与约束曲线 0)(Xh的切点 *是该约束问题的最优解图 2.10在 *X点处，目标函数的梯度 )(*Xf与约束函数的梯度 )(*Xh共线因此，在最优点 处一定存在一个乘子

9、*u，使得 0)(*uf成立对于一般的 n维等式约束优化问题，其数学模型为 mi().012jfXsthjm， ， ， ， ， 则 *X为其解的一阶必要条件为 *1()()002mjjjfuhXhX ， ， ， ， （三）GP 型约束 问题解的一阶 必要条件由上述不等式约束优化与等式约束优化问题的一阶必要条件，可以推出一般约束优化问题的条件设 n维一般约束优化问题的数学模型为 ， ， mjXhligtsfji 210)(.mn（2.19）则 *X为其解的一阶必要条件应为， ， ，mjXhligXhugXfjiili mjji210)( 0)()()(*11* （2.20）函数 lijji Xh

10、ufuL11)()()(，称为关于问题（2.19）的广义拉格朗日函数，式中 Tl21， ，m， 为拉格朗日乘子由于引入拉格朗日函数，条件（2.20）中的第一式可写为 0)(*uXL，（四）KuhnTcker 条件（简称 KT 条件）在优化实用计算中，常常需要判断某可行迭代点 k是否可作为约束最优点 *X输出而结束迭代，或者对此输出的可行结果进行检查，观察它是否已满足约束最优解的必要条件，这种判断或检验通常借助于 条件进行的对于 IP 型问题， TK条件可叙述如下：如果 *X是一个局部极小点 ，且各梯度矢量 )(*Xgi组成线性无关的矢量系，那么必存在一组非负乘子 i，使得 ligfilii，

11、，210)(0)(*1*成立必须指出，在一般情形下， TK条件是判别约束极小点的一阶必要条件，但并非充分条件只是对于凸规划问题，即对于目标函数 )(Xf为凸函数，可行域为凸集的最优化问题， TK条件才是约束最优化问题的充分条件而且，在这种情况下的局部最优解也必为全局最优解应用 条件检验某迭代点 k是否为约束最优点的具体作法可按下述步骤进行：（1）检验 kX是否为可行点为此需要计算 k处的诸约束函数值 )(kiXg，若是可行点，则 ligi ， 210)(（2）选出可行点 k处的起作用约束前面已求得 l个 )(ki值，其中等于零或相当接近零的约束就是起作用约束把这些起作用约束重新编排成序列 Ii

12、i ， )(（3）计算 kX点目标函数的梯度 )(kXf和 I 个起作用约束函数的梯度 )(kiXg（4）按 TK条件， k点应满足 Ii iki Igf1 )21(0)()( ， . (2.21）将式（2.21）中的各梯度矢量用其分量表示，则可得到 i为变量的线性方程组 ，0)()()()( )()()()( 021 22212 111 nkInknknk kIkkk kIkkk xXgxXgxgxXff xXgxXgxgxX 由于矢量系 Iigi ， 是线性无关的，所以该方程组存在唯一解通过解此线性方程组，求得一组乘子 ， 21，若所有乘子均为非负，即 Iii ， 21，则 kX即为约束最

13、优解否则， k点就不是约束最优点例 2.9 设约束优化问题 ， ，0)(1.)2()min1322xXgtsxf它的当前迭代点为TkX01，试用 K条件判别它是否为约束最优点解：（1）计算 点的诸约束函数值 ， 1)()()( 2221 kkk XggkX是可行点（2） k点起作用约束是 22211 )()( xxX，（3）求 k点梯度 ， ，10)(22)()(),(2),(110,(1kkkXgxf（4）求拉格朗日乘子按 TK条件应有 ，0120)()()(12kkk Xgf写成线性方程组 ，21解得 0121， 乘子均为非负，故TkX0,1满足约束最优解的一阶必要条件如图 2.11 所示

14、， kX点确为该约束优化问题的局部最优解，由于可行域是凸集，所以点 kX也是该问题的全局最优解图 2.11GP 型的约束最优化问题的 TK条件类似于 IP 型约束最优化问题的 TK条件：如果 *X是一个局部极小点 ，且各梯度矢量 )(*Xgi和 )(*hj组成线性无关的矢量系，那么必存在两组乘子*i和 ju，使得liXgufili mjji， ， ，210)( 0)()()(*11*（2.22）成立三、约束优化问题局部解的二阶充分条件GP 型的约束最优化问题的极小点的二阶充分条件是：设 *X对条件 )21()lii ， 和 )21(0)mjXhj ， 是可行的，若存在向量Tl21， 和Tmuu， ，它们满足 TK条件（2.22） ，而且对满足条件 mjXhZIigjT ii ， ，且， ，且， 210)( 0（2.23）的任意非零向量 Z有 0)()()(11*2*2*2 ZXhugfli mjjiT，则 *X为 GP 型的约束最优化问题的严格局部极小点这里当然要求 Xhfj，