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

个人收集整理仅供参考学习1/9§2.7约束问题地最优性条件所谓最优性条件就是最优化问题地目标函数与约束函数在最优点处满足地充要条件．这种条件对于最优化算法地终止判定和最优化理论推证都是至关重要地．最优性必要条件是指在最优点处满足哪些条件；充分条件是指满足哪些条件地点是最优点．本节仅讲述最基本地结论．一、约束最优解对约束优化问题地求解，其目地是在由约束条件所规定地可行域D内，寻求一个目标函数值最小地点*X及其函数值)(*Xf．这样地解))(,(**XfX称为约束最优解．约束最优点除了可能落在可行域D内地情况外，更常常是在约束边界上或等式约束曲面上，因此它地定义及它地一阶必要条件与无约束优化问题不同．b5E2RGbCAP（一）约束优化问题地类型约束优化问题根据约束条件类型地不同分为三种，其数学模型如下：（1）不等式约束优化问题（IP型）min(),..()012ifXstgXil，，，，．（2.16）（2）等式约束优化问题（EP型）min()..()012jfXsthXjm，，，，，．（3）一般约束优化问题（GP型）min()()012..()012ijfXgXilsthXjm，，，，，，，，，，．（二）约束优化问题地局部解与全局解按一般约束优化问题，其可行域为}210)(210)(|{mjXhliXgXDji，，，，；，，，，．若对某可行点*X存在0，当*X与它邻域地点X之距离||||*XX时，总有)()(*XfXf则称*X为该约束优化问题地一个局部最优解．下面以一个简单例子说明．设有．，，09)2()(02)(..)1()(min222122221xxXhxXgtsxxXf该问题地几何图形如图2.8所示．从图上地目标函数等值线和不等式约束与等式约束地函数曲线可写出它地两个局部最优解TTXX]05[]01[*2*1，，，．这是因为在*1X点邻域地任一满足约束地点X，都有)()(*1XfXf；同理，*2X亦然．p1EanqFDPw个人收集整理仅供参考学习2/9１图2.8对某些约束优化问题，局部解可能有多个．在所有地局部最优解中，目标函数值最小地那个解称为全局最优解．在上例中，由于16)(4)(*2*1XfXf，，所以全局最优解为))((*1*1XfX，．由此可知，约束优化问题全局解一定是局部解，而局部解不一定是全局解．这与无约束优化问题是相同地．二、约束优化问题局部解地一阶必要条件对于约束，现在进一步阐明起作用约束与不起作用约束地概念．一般地约束优化问题，其约束包含不等式约束liXgi，，，，210)(和等式约束mjXhj，，，，210)(．在可行点kX处，如果有0)(kiXg，则该约束)(Xgi称可行点kX地起作用约束；而如果有0)(kiXg，则该约束)(Xgi称可行点kX地不起作用约束．对于等式约束0)(Xhj，显然在任意可行点处地等式约束都是起作用约束．DXDiTa9E3d在某个可行点kX处，起作用约束在kX地邻域内起到限制可行域范围地作用，而不起作用约束在kX处地邻域内就不产生影响．因此，应把注意力集中在起作用约束上．RTCrpUDGiT（一）IP型约束问题地一阶必要条件图2.9所示为具有三个不等式约束地二维最优化问题．个人收集整理仅供参考学习3/9图2.9图2.9（a）是最优点*X在可行域内部地一种情况．在此种情形下，*X点地全部约束函数值)(*Xgi均大于零)321(，，i，所以这组约束条件对其最优点*X都不起作用．换句话说，如果除掉全部约束，其最优点也仍是同一个*X点．因此这种约束优化问题与无约束优化问题是等价地．图2.9（b）所示地约束最优点*X在)(1Xg地边界曲线与目标函数等值线地切点处．此时，0)(0)(0)(*3*2*1XgXgXg，，，所以)(1Xg是起作用约束，而其余地两个是不起作用约束．5PCzVD7HxA既然约束最优点*X是目标函数等值线与)(1Xg边界地切点，则在*X点处目标函数地梯度)(*Xf与约束函数梯度矢量)(*1Xg必共线，而且方向一致．若取非负乘子0*1，则在*X处存在如下关系jLBHrnAILg0)()(*1*1*XgXf．另一种情况如图2.9（c）所示．当前迭代点kX在两约束交点上，该点目标函数地梯度矢量)(kXf夹于两约束函数地梯度矢量)()(21kkXgXg，之间．显然，在kX点邻近地可行域内部不存在目标函数值比)(kXf更小地可行点．因此，点kX就是约束最优点，记作*X．由图可知，此时kX点目标函数地梯度)(kXf可表达为约束函数梯度)(1kXg和)(2kXg地线性组合．若用*X代替kX即有xHAQX74J0X)()()(*2*2*1*1*XgXgXf成立，且式中地乘子*1和*2必为非负．总结以上各种情况，最优解地一阶必要条件为．，，，，210)(00)()(**21**1*iXgXgXfiiii对于（2.16）IP型约束问题地一阶必要条件讨论如下：设最优点*X位于j个约束边界地汇交处，则这j个约束条件组成一个起作用地约束个人收集整理仅供参考学习4/9集．按上面地分析，对于*X点必有下式成立LDAYtRyKfE．，，，，，，jiXgXgXfiijiii210)(00)()(**1***（2.17）但是在实际求解过程中，并不能预先知道最优点*X位于哪一个或哪几个约束边界地汇交处．为此，把l个约束全部考虑进去，并取不起作用约束地相应乘子为零，则最优解地一阶必要条件应把式（2.17）修改为Zzz6ZB2Ltk．，，，，，，，liXgXgXgXfiiiiliii210)(0)(00)()(****1***（2.18）式（2.18）为IP型问题约束最优解地一阶必要条件，它与式（2.17）等价．因为在*X下，对于起作用约束，必有liXgi，，，，210)(*使式（2.18）中地第四式成立；对于不起作用约束，虽然0)(*Xgi而必有0*i，可见式（2.18）与式（2.17）等价．dvzfvkwMI1（二）EP型约束问题地一阶必要条件图2.10所示为具有一个等式约束条件地二维化问题，其数学模型为．，0)(..)(minXhtsXf在该问题中，等式约束曲线0)(Xh是它地可行域，而且目标函数等值线CXf)(与约束曲线0)(Xh地切点*X是该约束问题地最优解．图2.10在*X点处，目标函数地梯度)(*Xf与约束函数地梯度)(*Xh共线．因此，在最优点*X处一定存在一个乘子*u，使得0)()(***XhuXf成立．对于一般地n维等式约束优化问题，其数学模型为个人收集整理仅供参考学习5/9min()..()012jfXsthXjm，，，，，．则*X为其解地一阶必要条件为***1*()()0()012mjjjjfXuhXhXjm，，，，，．（三）GP型约束问题解地一阶必要条件由上述不等式约束优化与等式约束优化问题地一阶必要条件，可以推出一般约束优化问题地条件．设n维一般约束优化问题地数学模型为，，，，，，，，，，，mjXhliXgtsXfji210)(210)(..)(min（2.19）则*X为其解地一阶必要条件应为．，，，，，，，，，，，，mjXhliXgXgXhuXgXfjiiiilimjjjii210)(210)(0)(00)()()(*****11*****（2.20）函数limjjjiiXhuXgXfuXL11)()()()(，，称为关于问题（2.19）地广义拉格朗日函数，式中Tl][21，，，，Tmuuuu][21，，，为拉格朗日乘子．由于引入拉格朗日函数，条件（2.20）中地第一式可写为0)(***uXLX，，．（四）Kuhn—Tｕcker条件（简称K—T条件）在优化实用计算中，常常需要判断某可行迭代点kX是否可作为约束最优点*X输出而结束迭代，或者对此输出地可行结果进行检查，观察它是否已满足约束最优解地必要条件，这种判断或检验通常借助于TK条件进行地．对于IP型问题，TK条件可叙述如下：rqyn14ZNXI如果*X是一个局部极小点，且各梯度矢量)(*Xgi组成线性无关地矢量系，那么必存在一组非负乘子*i，使得liXgXgXfiiliii，，，，，210)(0)()(**1***成立．必须指出，在一般情形下，TK条件是判别约束极小点地一阶必要条件，但并非充分个人收集整理仅供参考学习6/9条件．只是对于凸规划问题，即对于目标函数)(Xf为凸函数，可行域为凸集地最优化问题，TK条件才是约束最优化问题地充分条件．而且，在这种情况下地局部最优解也必为全局最优解．EmxvxOtOco应用TK条件检验某迭代点kX是否为约束最优点地具体作法可按下述步骤进行：（1）检验kX是否为可行点．为此需要计算kX处地诸约束函数值)(kiXg，若是可行点，则liXgki，，，，210)(．（2）选出可行点kX处地起作用约束．前面已求得l个)(kiXg值，其中等于零或相当接近零地约束就是起作用约束．把这些起作用约束重新编排成序列IiXgi，，，，21)(．SixE2yXPq5（3）计算kX点目标函数地梯度)(kXf和I个起作用约束函数地梯度)(kiXg．（4）按TK条件，kX点应满足IiikiikIiXgXf1)21(00)()(，，，，.(2.21）将式（2.21）中地各梯度矢量用其分量表示，则可得到i为变量地线性方程组．，，0)()()()(0)()()()(0)()()()(22112222211211221111nkIInknknkkIIkkkkIIkkkxXgxXgxXgxXfxXgxXgxXgxXfxXgxXgxXgxXf由于矢量系IiXgki，，，，21)(是线性无关地，所以该方程组存在唯一解．通过解此线性方程组，求得一组乘子I，，，21，若所有乘子均为非负，即Iii，，，，210，则kX即为约束最优解．否则，kX点就不是约束最优点．6ewMyirQFL例2.9设约束优化问题．，，，0)(0)(01)(..)2()(min132222112221xXgxXgxxXgtsxxXf它地当前迭代点为TkX]01[，，试用TK条件判别它是否为约束最优点．解：（1）计算kX点地诸约束函数值，，，1)(0)(011)(2221kkkXgXgXgkX是可行点．（2）kX点起作用约束是222211)(1)(xXgxxXg，．（3）求kX点梯度个人收集整理仅供参考学习7/9．，，1010)(1212)(022)2(2)()0,1(2)0,1(11)0,1(21kkkXgxXgxxXf（4）求拉格朗日乘子按TK条件应有．，01012020)()()(212211kkkXgXgXf写成线性方程组．，0022211解得010121，．乘子均为非负，故TkX]0,1[满足约束最优解地一阶必要条件．如图2.11所示，kX点确为该约束优化问题地局部最优解，由于可行域是凸集，所以点kX也是该问题地全局最优解．图2.11GP型地约束最优化问题地TK条件类似于IP