《最优化方法及应用郭科约束问题的最优性条件》由会员分享，可在线阅读，更多相关《最优化方法及应用郭科约束问题的最优性条件（10页珍藏版）》请在金锄头文库上搜索。
1、2.7约束问题的最优性条件所谓最优性条件就是最优化问题的目标函数与约束函数在最优点处满足的充要条件.这种条件对于最优化算法的终止判定和最优化理论推证都是至关重要的.最优性必要条件是指在最优点处满足哪些条件； 充分条件是指满足哪些条件的点是最优点. 本节仅讲述最 基本的结论.一、约束最优解对约束优化问题的求解，其目的是在由约束条件所规定的可行域D内，寻求一个目标函数值最小的点 X*及其函数值f(X*) 这样的解(X*, f(X*)称为约束最优解约束最优点除了可能落在可行域 D内的情况外，更常常是在约束边界上或等式约束曲面上，因此 它的定义及它的一阶必要条件与无约束优化问题不同.(一) 约束优化问
2、题的类型约束优化问题根据约束条件类型的不同分为三种，其数学模型如下:(1) 不等式约束优化问题(IP型)min f (X),s.t.(2) 等式约束优化问题(EP型)min f(X),s.t. hj(X) = 0,(3) 般约束优化问题(GP型)min f (X),t igi(X0,shj(X) =0,(二)约束优化问题的局部解与全局解gi(X)_O, i =1,2,川，I.j =1,2,川，m.i =1,2川1,1,j =1,2,|l,m.(2.16)按一般约束优化问题，其可行域为D =X |gj(X)工0, i =1,2,hj(X) =0, j =1,2, , m.*若对某可行点 X*存在
3、；0 ,当X*与它邻域的点 X之距离l|X -X |卜：；时，总有*f(X厂：f(X)则称X*为该约束优化问题的一个局部最优解. 下面以一个简单例子说明设有min f(X) = (xi1)2 xf,g(X)=X2+2K0,st.22R(X) =(x, -2)2 -x； -9 = 0.该问题的几何图形如图 2.8所示从图上的目标函数等值线和不等式约束与等式约束的函数曲*T*Tv *线可写出它的两个局部最优解Xi一1,0 , X = 5,0.这是因为在X1点邻域的任一满 足约束的点X，都有f (X) f (X1 )；同理，X2亦然.对某些约束优化问题，局部解可能有多个在所有的局部最优解中，目标函数
4、值最小的那个解称为全局最优解.在上例中，由于f (Xi) = 4，f (X2)= 16，所以全局最优解为(Xi,f(Xi).由此可知，约束优化问题全局解一定是局部解，而局部解不一定是全局解这与无约束优化问题是相同的.二、约束优化问题局部解的一阶必要条件对于约束，现在进一步阐明起作用约束与不起作用约束的概念一般的约束优化问题，其约束包含不等式约束gi (X) - 0, i = 12, ,1和等式约束 hj(X) =0, j T，2，,m 在可行点Xk处，如果有gi(Xk) =0，则该约束gi(X)称可行 点Xk的起作用约束；而如果有gi(Xk)，则该约束gi(X)称可行点Xk的不起作用约束对于等
5、式约束 hj(X) = 0，显然在任意可行点处的等式约束都是起作用约束.在某个可行点 Xk处，起作用约束在 Xk的邻域内起到限制可行域范围的作用，而不起 作用约束在Xk处的邻域内就不产生影响.因此，应把注意力集中在起作用约束上.(一) IP型约束问题的一阶必要条件图2.9所示为具有三个不等式约束的二维最优化问题.(7)图2.9图2.9 (a)是最优点X在可行域内部的一种情况.在此种情形下，X点的全部约束*函数值gi(X )均大于零(i二1,2,3)，所以这组约束条件对其最优点X*都不起作用.换句话说，如果除掉全部约束，其最优点也仍是同一个X*点.因此这种约束优化问题与无约束优化问题是等价的.图
6、 2.9 (b)所示的约束最优点 X*在gi(X)的边界曲线与目标函数等值* * *线的切点处.此时，g1(X )=0, g2(X )0, g3(X )0，所以gi(X)是起作用约束，而其余的两个是不起作用约束.既然约束最优点X*是目标函数等值线与gi(X)边界的切点，则在 X*点处目标函数的 梯度Nf(X*)与约束函数梯度矢量7gi(X*)必共线，而且方向一致.若取非负乘子 小0 , 则在X *处存在如下关系Vf(X*W(X*0.另一种情况如图2.9 (c)所示.当前迭代点 Xk在两约束交点上，该点目标函数的梯度矢量 f(Xk)灯两约束函数的梯度矢量v gi(Xk), g2(Xk)之间.显然
7、，在Xk点邻近的可行 域内部不存在目标函数值比f(Xk)更小的可行点.因此，点Xk就是约束最优点，记作X .由图可知，此时 Xk点目标函数的梯度 (Xk)可表达为约束函数梯度 v gi (Xk)和 g2 (Xk)的线性组合.若用X *代替Xk即有可(X*)Rgi(X*)乜可 g2(X*)成立，且式中的乘子 i和2必为非负.总结以上各种情况，最优解的一阶必要条件为 2斫(X*)送 &；%i(X*)=0,* 人 0,、gi(X*)X0,i=i,2.对于(2.I6) IP型约束问题的一阶必要条件讨论如下：设最优点X*位于j个约束边界的汇交处，则这j个约束条件组成一个起作用的约束集按上面的分析，对于
8、X 点必有下式成立lf(X ) 一汽 gi(X ) =0,g。*) _0, i J, 2,j.(2.17)但是在实际求解过程中，并不能预先知道最优点X*位于哪一个或哪几个约束边界的汇交处为此，把丨个约束全部考虑进去，并取不起作用约束的相应乘子为零，则最优解的一阶 必要条件应把式（2.17）修改为f(X*) Agi(X*)=0,.让0,(2.18)gi(x*)K0, *gi(X*) =0,i =1, 2,，I.式（2.18 ）为IP型问题约束最优解的一阶必要条件，它与式（2.17）等价.因为在 X*下,*对于起作用约束，必有 gi（X）i二1, 2,，1使式（2.18）中的第四式成立；对于不*
9、*起作用约束，虽然 gi（X ）0而必有i ，可见式（2.18）与式（2.17）等价.（二）EP型约束问题的一阶必要条件图2.10所示为具有一个等式约束条件的二维化问题，其数学模型为min f(X),s.t. h(X) =0.在该问题中，等式约束曲线 h（X）=0是它的可行域，而且目标函数等值线f（X）=C与约束曲线h（X） =0的切点x*是该约束问题的最优解.图 2.10在X*点处，目标函数的梯度 、f （X ）与约束函数的梯度v h（X ）共线.因此，在最优 点X*处一定存在一个乘子 U*，使得* *If（X ） - u I h（X ）=0成立.对于一般的n维等式约束优化问题，其数学模型为
10、min f(X),s.t. hj(X) =0,j =1,2,I,m.则X*为其解的一阶必要条件为fmf(X*) uhj(X*0,j(X*)=0,j=1,2,|,m.(三) GP型约束问题解的一阶必要条件由上述不等式约束优化与等式约束优化问题的一阶必要条件，可以推出一般约束优化问题的条件.设n维一般约束优化问题的数学模型为min f (X),Q(X)X0, i =1,2,，1,s. t.丿(2.19)(2.20)j(X)=0, j=1,2,，,m,则X *为其解的一阶必要条件应为lmVf(X )_迟扎Vgi(X ) Uj Vhj (X )=0,yj阳X0,5(x*)3 0,打 g,x*)=0,
11、i=1,2,，1, hj(X*)=0,j =1 , 2,二 m.函数LlmL(X , , u)=f(X)- gi(X)八 Ujhj (X)yj 二称为关于问题（2.19）的广义拉格朗日函数，式中1 , 2 , l U 二U1 , U2，,UmT为拉格朗日乘子由于引入拉格朗日函数，条件（2.20）中的第一式可写为JL（X*，汇，u*）=0.（四）Kuhn T u cker条件（简称 KT条件）在优化实用计算中，常常需要判断某可行迭代点Xk是否可作为约束最优点 X*输出而结束迭代，或者对此输出的可行结果进行检查，观察它是否已满足约束最优解的必要条件， 这种判断或检验通常借助于 K -T条件进行的对
12、于IP型问题，K -T条件可叙述如下：*如果X*是一个局部极小点 ，且各梯度矢量、gi（X ）组成线性无关的矢量系，那么必*存在一组非负乘子i,使得l(X*)gi(X*) =0,i# * *igi(X )=0, i =1,2, ,l成立.必须指出，在一般情形下,K -T条件是判别约束极小点的一阶必要条件，但并非充分条件只是对于凸规划问题， 即对于目标函数f(X)为凸函数，可行域为凸集的最优化问题,K -T条件才是约束最优化问题的充分条件.而且，在这种情况下的局部最优解也必为全局最优解.应用K -T条件检验某迭代点 X k是否为约束最优点的具体作法可按下述步骤进行：(1) 检验Xk是否为可行点为
13、此需要计算Xk处的诸约束函数值 gi(Xk)，若是可行 点，则 gi(Xk) o, i = I2，, 1.(2) 选出可行点 Xk处的起作用约束前面已求得I个gi(Xk)值，其中等于零或相当接近零的约束就是起作用约束把这些起作用约束重新编排成序列gi(X), i二1,2，1(3) 计算Xk点目标函数的梯度f(Xk)和|个起作用约束函数的梯度 gi(Xk).(4) 按K -T条件，Xk点应满足Ilf(Xk)八 igi(Xk)=0, i _0 (i =1,2,1)y.(2.21)将式(2.21)中的各梯度矢量用其分量表示，则可得到i为变量的线性方程组 (Xk).-I0?&1.Eg i (x k)
14、| . 0 X2f (Xk):g1(Xk)92(Xk) 1 2；:x1f (Xk)；：x2tx1cx1“血 1(XQ 闵 2(XQ -1 1 2 一.:x2.:x2汗(Xk)% (Xk)-2 . (Xk) 1 :$n由于矢量系gi(Xk),i二1,2,是线性无关的，所以该方程组存在唯一解通过解此线 性方程组，求得一组乘子1, 2,，丨，若所有乘子均为非负，即j _0,二1,2,，I则Xk即为约束最优解否则，例2.9设约束优化问题Xk点就不是约束最优点.2 2min f (X)=(为 -2) x2,gi(X) =1 -x2 -X2 0,s.t. g2(X) =X2 -0,g3(x)= x “它的当前迭代点为 Xk =1,0T，试用K -T条件判别它是否为约束最优点. 解：(1)计算Xk点的诸约束函数值g2(Xk)二 0,g2 (X k)二 1g1(Xk)=1-12=0,Xk是可行点. X2,g2(X)二 X2.(2) Xk点起作用约束是gi(X) 胡-xi2(3)求Xk点梯度2(X1 2),0)02，W 0(1,0)(4)求拉
