最优化理论与算法(第九章)

1、第九章二次规划9.1二次规划问题称形如minQ(x)=2xrHx+grx,arx=bi=1,s.tii0arxbi=m+1,的非线性规划问题为二次规划问题。对二次规划问题，有如下的最优性条件。定理9.1设x*是（9.1）的局部极小点，则必存在乘子勲（i1,m），使得g+Hx*=*ai=1X*arx*b九*0i=m+1,ei=m+1,e且对于一切满足于：dra=0,ieEI(x*)i的deRn，都有dTHd0。注：1）上述定理的前后两部分分别对应2)满足上述条件的d，都有deS（x*,九*）；3)当约束条件均为线性函数时，容易证明：ddra=0idTa0idra=0iFD(x*,X)SFD(x*

2、,X)LFD(x*,X)及S(x*,九*)=G(x*,九*)面给出的是二次规划的必要性条件，下面给出充分性条件。定理9.2设x*是K-T点，九*是相应的Lagrange乘子，如果对满足9.3)ieI(x*)9.3)ieI(x*)且X*0i的一切非零向量deRn，都有dTHd0，则x*是（9.1）的局部严格极小点。注：条件组（9.3）表示的正好是d,G（x*,*）的条件，因此这个定理实际上是上一节二阶充分性条件在二次规划情形的特殊表述。对二次规划问题还有如下充分必要条件定理9.3设x*是（9.1）的可行解，则x*是一局部最小点的充要条件是：存在乘子*二（九*,*），1m使得（9.2）满足，且对一

3、切满足（9.3）的d都有drHd0注：这个定理的证明可参见韩继业二次规划理论与算法，曲阜师范学院学报，1985年第一期18。特别地，当H为正定或半正定时，目标函数为凸函数，二次规划为凸规划。因此任何K-T点必为二次规划的全局极小点，此时求解（9.1）等价于求解其中E=1,m，二次规划问题:的Wolfe对偶为：g+Hx=A为二次规划的全局极小点，此时求解（9.1）等价于求解其中E=1,m，二次规划问题:的Wolfe对偶为：g+Hx=AaTx=biiaTxbiiaTx一b=0iii0iI=m+1,m，=(,)，A=a,ae1m19.2对偶性质minQ(x)=2xtHx+gTxaTx=bi=1,ii

4、arxbi=m+1,max2xtHx+gTx-(Atb)Hx+g=As.t仁0i,Ii9.4)在H正定时，若令A0,i/上的稳定点。i由L(x,)的Hessian矩阵为利用V2L(x,利用V2L(x,，)二HAt_I0-V2L(x,，)IH-1AH0AtH-1I_0I0-AtH-iA0可知V2L恰为n个正特征值，而且它的负特征值的个数正好为A的秩。因而，L（x,，）的稳定点一般是一个鞍点，下面证明（x*,，*）的确是L（x,，）的鞍点。事实上,我们有maxL(x,)二max这里ARm|,0,iI是对偶问题（9.7）的可行域。而对任何,A，若令iy=a，-g则（,y）是（9.7）的可行点，而且1

5、minL（x,）=b，一yTH1y=Q（，,y）xRn2（由于对给定的，L（x,）是x的凸函数，minL（x,）的最优解可由VL（x,）二0解出x得，同xxRn时注意到y=A，g即可得到上式。）设（x*,，*）是K-T问题（9.4）的解，令y*二A，*g，则知（九*,y*）是对偶问题（9.7）的可行点。于是xRn和,A都有:L(x,*)Q(X*,y*)=L(x*,*)=Q(x*)L(x*,)即:L(x*,，)L(x*,，*)L(x,，*即:故（x*,*）是L（x,，）的鞍点。反之，我们还可以证明，若（x*,，*）是L（x,，）的鞍点，则x*必为原始问题（9.1）的极小点。面讨论给出了鞍点问题解

6、与原极小化问题解之间的关系:定理9.7设H正定，则x*wX是原始问题极小点的充要条件是：存在，wA，使得对一切xeX,和一切XeA，都有L(x,)L(x,)L(x,*)和一切XeA，9.3等式约束问题问题形式：minQ(x)2x问题形式：minQ(x)2xtHx+gTxs.tAtxb(假定R(A)m)9.8)一、消去法ara)rx)B，xBaJNx丿NATxb可改写为解出得Atx+Atx可改写为解出得BBNNx(At)-i(b-Atx)BBNN将其代人目标函数得无约束问题：最优性条件：1)若H正定,N2)若方半正定,N3)入1入最优性条件：1)若H正定,N2)若方半正定,N3)入1入mingt

7、x+xtHxNN2NNxNWRn-mHHx+goNNx-H-1gNNN借助广义逆，有9.9)x*一H+g+(I一H+H)x(xeRn-m任意，解不唯一)NNNNN若h有负特征值，则问题无界。N注：问题(9.9)可利用无约束优化问题的各种算法求解。、广义消去法设y,y是域空间R(A)的一组线性无关的向量(即R(A)的一组基)，z,1m1Null(At)的一组线性无关向量，显然Null(At)与R(A)互为正交补。若记Yy,y，Zz,1m1则有：AtY非奇异，而AtZ0。事实上，由于A与Y的列向量组均为R(A)的基，故有:y,ya,aT1y,ya,aT1m1(T为两组基之间的过渡矩阵)AtYAtY

8、=AtAT因此xY(AtY)-ib+Z进一步有：由A列满秩知AtA是正定矩阵，再由T可逆，故有AtY非奇异。而由于Z中列向量均在Null(At)中，故有AtZ0。显然，,xeRn，x可表示为xYx+Zx。特别地，对满足atx=b的x有bAtxAtYxAtZxX(AtY)-1Atx(AtY)-1b将此代入目标函数并略去常数项，得到：9.10)min(gHY(AtY)-1b)tZx-XtZtHZx9.10)2称ZtHZ为既约Hessian矩阵，而Zt(g+HY(AtY)-1b)为既约梯度。三、Lagrange乘子法直接求Lagrange函数L(X,)2xtHxgTx一t(Atx-b)的稳定点：gH

9、XAATxb9.11)9.4积极集法(有效集法)一、算法的理论基础积极集法是通过求解有限多个等式约束二次规划问题，来求解一般约束二次规划问题，下面引理是其理论基础。定理9.8设X*是二次规划问题(9.1)的局部极小点，则X*也必是问题mingTx1xtHx2s.taTx，bieEI(x*)(9.12)ii的局部极小点；反之，若x*是(9.12)的K_T点，且还是原问题(9.1)的可行点。相应Lagrange乘子*满足：九：0，ieI(x*)。则x*也是原週的K-T点。证明：设x*是原问题的解，若它不是(9.12)的极小点，那么必有充分靠近x*的点x使得而当x充分靠近x*时，也必是原问题的可行点

10、，这与x*是最优点矛盾。另一方面，设x*是原问题的可行点，且满足(9.12)的K-T条件，则存在*(ieEI(x*)，i使得gHx*，工a*使得iiieEI(x*)且还有*0，iieI(x*)。进一步地(JeI-1(x*)时，令*，0且还有*0，ig+Hx*，近a*ii且满足i，1且满足*0，*(aTx*-b)，0，ieIiiii由x*可行，即知x*是原问题的K-T点。积极集法是一个可行点法，在迭代过程中，始终保持迭代点可行。而每次迭代求解一个只含等式约束的二次规划。如果等式约束问题的解是原约束问题的可行解，则进一步检验九*0，ieI(x*)i是否满足。若满足，则停止计算，否则，可去掉一约束重

11、新求解约束问题。若等式约束二次规划之解不是原问题的可行解，则需要增加约束，然后重新求解等式约束问题。、算法的迭代步骤1给出初始可行点x，1令S，EI(x),k:,1。ii2求解等式约束问题(U3d)s丄aTd，0,ieSik得d，若d0，则转3.kk若九k,0(iGSikikiG若九k,0(iGSikikiGS3.令amink算法停止;i，xxk+ik令九（k）min九（k）ikSSi，kkkxk+1xk，转4.令Sk：Skj。1（卩线性无关则算法必若a1，转4令Sk：Skj。1（卩线性无关则算法必kkjkkkj4S:S;k:k+1转2.kk三、算法的有限终止性定理9.8设xk是由积极集法产生的点列若对任何k都有a.（iGE有限终止于问题的K-T