最優(yōu)化理論與算法(第九章)

1、第九章二次規(guī)劃9.1二次規(guī)劃問題稱形如minQ(x)=2xrHx+grx,arx=bi=1,s.tii0arxbi=m+1,的非線性規(guī)劃問題為二次規(guī)劃問題。對二次規(guī)劃問題，有如下的最優(yōu)性條件。定理9.1設(shè)x*是（9.1）的局部極小點(diǎn)，則必存在乘子勲（i1,m），使得g+Hx*=*ai=1X*arx*b九*0i=m+1,ei=m+1,e且對于一切滿足于：dra=0,ieEI(x*)i的deRn，都有dTHd0。注：1）上述定理的前后兩部分分別對應(yīng)2)滿足上述條件的d，都有deS（x*,九*）；3)當(dāng)約束條件均為線性函數(shù)時(shí)，容易證明：ddra=0idTa0idra=0iFD(x*,X)SFD(x*

2、,X)LFD(x*,X)及S(x*,九*)=G(x*,九*)面給出的是二次規(guī)劃的必要性條件，下面給出充分性條件。定理9.2設(shè)x*是K-T點(diǎn)，九*是相應(yīng)的Lagrange乘子，如果對滿足9.3)ieI(x*)9.3)ieI(x*)且X*0i的一切非零向量deRn，都有dTHd0，則x*是（9.1）的局部嚴(yán)格極小點(diǎn)。注：條件組（9.3）表示的正好是d,G（x*,*）的條件，因此這個(gè)定理實(shí)際上是上一節(jié)二階充分性條件在二次規(guī)劃情形的特殊表述。對二次規(guī)劃問題還有如下充分必要條件定理9.3設(shè)x*是（9.1）的可行解，則x*是一局部最小點(diǎn)的充要條件是：存在乘子*二（九*,*），1m使得（9.2）滿足，且對一

3、切滿足（9.3）的d都有drHd0注：這個(gè)定理的證明可參見韓繼業(yè)二次規(guī)劃理論與算法，曲阜師范學(xué)院學(xué)報(bào)，1985年第一期18。特別地，當(dāng)H為正定或半正定時(shí)，目標(biāo)函數(shù)為凸函數(shù)，二次規(guī)劃為凸規(guī)劃。因此任何K-T點(diǎn)必為二次規(guī)劃的全局極小點(diǎn)，此時(shí)求解（9.1）等價(jià)于求解其中E=1,m，二次規(guī)劃問題:的Wolfe對偶為：g+Hx=A為二次規(guī)劃的全局極小點(diǎn)，此時(shí)求解（9.1）等價(jià)于求解其中E=1,m，二次規(guī)劃問題:的Wolfe對偶為：g+Hx=AaTx=biiaTxbiiaTx一b=0iii0iI=m+1,m，=(,)，A=a,ae1m19.2對偶性質(zhì)minQ(x)=2xtHx+gTxaTx=bi=1,ii

4、arxbi=m+1,max2xtHx+gTx-(Atb)Hx+g=As.t仁0i,Ii9.4)在H正定時(shí)，若令A(yù)0,i/上的穩(wěn)定點(diǎn)。i由L(x,)的Hessian矩陣為利用V2L(x,利用V2L(x,，)二HAt_I0-V2L(x,，)IH-1AH0AtH-1I_0I0-AtH-iA0可知V2L恰為n個(gè)正特征值，而且它的負(fù)特征值的個(gè)數(shù)正好為A的秩。因而，L（x,，）的穩(wěn)定點(diǎn)一般是一個(gè)鞍點(diǎn)，下面證明（x*,，*）的確是L（x,，）的鞍點(diǎn)。事實(shí)上,我們有maxL(x,)二max這里ARm|,0,iI是對偶問題（9.7）的可行域。而對任何,A，若令iy=a，-g則（,y）是（9.7）的可行點(diǎn)，而且1

5、minL（x,）=b，一yTH1y=Q（，,y）xRn2（由于對給定的，L（x,）是x的凸函數(shù)，minL（x,）的最優(yōu)解可由VL（x,）二0解出x得，同xxRn時(shí)注意到y(tǒng)=A，g即可得到上式。）設(shè)（x*,，*）是K-T問題（9.4）的解，令y*二A，*g，則知（九*,y*）是對偶問題（9.7）的可行點(diǎn)。于是xRn和,A都有:L(x,*)Q(X*,y*)=L(x*,*)=Q(x*)L(x*,)即:L(x*,，)L(x*,，*)L(x,，*即:故（x*,*）是L（x,，）的鞍點(diǎn)。反之，我們還可以證明，若（x*,，*）是L（x,，）的鞍點(diǎn)，則x*必為原始問題（9.1）的極小點(diǎn)。面討論給出了鞍點(diǎn)問題解

6、與原極小化問題解之間的關(guān)系:定理9.7設(shè)H正定，則x*wX是原始問題極小點(diǎn)的充要條件是：存在，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將其代人目標(biāo)函數(shù)得無約束問題：最優(yōu)性條件：1)若H正定,N2)若方半正定,N3)入1入最優(yōu)性條件：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有負(fù)特征值，則問題無界。N注：問題(9.9)可利用無約束優(yōu)化問題的各種算法求解。、廣義消去法設(shè)y,y是域空間R(A)的一組線性無關(guān)的向量(即R(A)的一組基)，z,1m1Null(At)的一組線性無關(guān)向量，顯然Null(At)與R(A)互為正交補(bǔ)。若記Yy,y，Zz,1m1則有：AtY非奇異，而AtZ0。事實(shí)上，由于A與Y的列向量組均為R(A)的基，故有:y,ya,aT1y,ya,aT1m1(T為兩組基之間的過渡矩陣)AtYAtY

8、=AtAT因此xY(AtY)-ib+Z進(jìn)一步有：由A列滿秩知AtA是正定矩陣，再由T可逆，故有AtY非奇異。而由于Z中列向量均在Null(At)中，故有AtZ0。顯然，,xeRn，x可表示為xYx+Zx。特別地，對滿足atx=b的x有bAtxAtYxAtZxX(AtY)-1Atx(AtY)-1b將此代入目標(biāo)函數(shù)并略去常數(shù)項(xiàng)，得到：9.10)min(gHY(AtY)-1b)tZx-XtZtHZx9.10)2稱ZtHZ為既約Hessian矩陣，而Zt(g+HY(AtY)-1b)為既約梯度。三、Lagrange乘子法直接求Lagrange函數(shù)L(X,)2xtHxgTx一t(Atx-b)的穩(wěn)定點(diǎn)：gH

9、XAATxb9.11)9.4積極集法(有效集法)一、算法的理論基礎(chǔ)積極集法是通過求解有限多個(gè)等式約束二次規(guī)劃問題，來求解一般約束二次規(guī)劃問題，下面引理是其理論基礎(chǔ)。定理9.8設(shè)X*是二次規(guī)劃問題(9.1)的局部極小點(diǎn)，則X*也必是問題mingTx1xtHx2s.taTx，bieEI(x*)(9.12)ii的局部極小點(diǎn)；反之，若x*是(9.12)的K_T點(diǎn)，且還是原問題(9.1)的可行點(diǎn)。相應(yīng)Lagrange乘子*滿足：九：0，ieI(x*)。則x*也是原週的K-T點(diǎn)。證明：設(shè)x*是原問題的解，若它不是(9.12)的極小點(diǎn)，那么必有充分靠近x*的點(diǎn)x使得而當(dāng)x充分靠近x*時(shí)，也必是原問題的可行點(diǎn)

10、，這與x*是最優(yōu)點(diǎn)矛盾。另一方面，設(shè)x*是原問題的可行點(diǎn)，且滿足(9.12)的K-T條件，則存在*(ieEI(x*)，i使得gHx*，工a*使得iiieEI(x*)且還有*0，iieI(x*)。進(jìn)一步地(JeI-1(x*)時(shí)，令*，0且還有*0，ig+Hx*，近a*ii且滿足i，1且滿足*0，*(aTx*-b)，0，ieIiiii由x*可行，即知x*是原問題的K-T點(diǎn)。積極集法是一個(gè)可行點(diǎn)法，在迭代過程中，始終保持迭代點(diǎn)可行。而每次迭代求解一個(gè)只含等式約束的二次規(guī)劃。如果等式約束問題的解是原約束問題的可行解，則進(jìn)一步檢驗(yàn)九*0，ieI(x*)i是否滿足。若滿足，則停止計(jì)算，否則，可去掉一約束重

11、新求解約束問題。若等式約束二次規(guī)劃之解不是原問題的可行解，則需要增加約束，然后重新求解等式約束問題。、算法的迭代步驟1給出初始可行點(diǎn)x，1令S，EI(x),k:,1。ii2求解等式約束問題(U3d)s丄aTd，0,ieSik得d，若d0，則轉(zhuǎn)3.kk若九k,0(iGSikikiG若九k,0(iGSikikiGS3.令amink算法停止;i，xxk+ik令九（k）min九（k）ikSSi，kkkxk+1xk，轉(zhuǎn)4.令Sk：Skj。1（卩線性無關(guān)則算法必若a1，轉(zhuǎn)4令Sk：Skj。1（卩線性無關(guān)則算法必kkjkkkj4S:S;k:k+1轉(zhuǎn)2.kk三、算法的有限終止性定理9.8設(shè)xk是由積極集法產(chǎn)生的點(diǎn)列若對任何k都有a.（iGE有限終止于問題的K-T