基于仿射尺度方法的二次規(guī)劃問題求解

基于仿射尺度方法的二次規(guī)劃問題求解

二規(guī)劃問題的求解是數(shù)學(xué)規(guī)劃和工業(yè)應(yīng)用的一個重要課題，也是解決一般非線性規(guī)劃問題的二次規(guī)劃算法的關(guān)鍵。在第一次解決二次規(guī)劃問題時，使用了線性規(guī)劃的簡單方法和有效集法。1968年，該算法由karak提出。在提出了解算方法的內(nèi)部算法后，許多人使用了模仿參數(shù)算法進(jìn)行非線性計算。在本研究中，基于模仿參數(shù)方法的概念，將一般不確定的二次規(guī)劃問題轉(zhuǎn)化為球限制的二次規(guī)劃問題，并將二次規(guī)劃問題轉(zhuǎn)化為球限制的凸二次規(guī)劃問題，豐富了二次規(guī)劃問題的方法體系。1有qxqx考慮問題其中:Q∈Rn×n,Q不定,且Q是非奇異的實對稱矩陣,c,x∈Rn;A∈Rm×n,m≤n,秩(A)=m.記S={x|Ax=b,x≥0},SS={x|Ax=b,x≥0},S非空,且S為有界集.記SΟ={x|Ax=b,x>0},∥?∥代表歐氏范數(shù).給一初始可行點xk∈SO,使用仿射尺度技術(shù),產(chǎn)生子二次規(guī)劃問題其中:=XkQXk;=Xkc;Xk=diag(xk);=AXk;0<r<1.令Δx=x-e,這樣(QP2)可以寫成:記為的零空間的一組標(biāo)準(zhǔn)正交基,由于∈Rm×n,秩()=m,則∈Rn×(n-m).令Δx=Δy,這樣(QP3)就變成為如果得到(QP4)的一個局部最優(yōu)解為Δy*,也就得到了(QP2)的局部最優(yōu)解,從而也就產(chǎn)生了原問題的下一個迭代點xk+1=Xkˉx.定理1q(xk+1)≤q(xk)證明由于q(xk)=(e),q(xk+1)=().對(x)來說,e為初始可行點,為局部最優(yōu)點,故有ˉq(ˉx)≤ˉq(e).也即q(xk+1)≤q(xk).由于是(x)的局部最優(yōu)解,故滿足下列條件{ˉQˉx+ˉc-ˉAΤˉy+uk(ˉx-e)=0,ˉA(ˉx-e)=0∥ˉx-e∥≤r?uk(r-∥ˉx-e∥)=0,uk≥0(1)其中,uk為相應(yīng)的Lagrange乘子.令pk=+-T,sk+1=s(xk)=QXk+c-AT則uk=∥pk∥r?pk=Xksk+1那么xk+1=Xkˉx=Xk(e-rpk∥pk∥)下面給出仿射尺度算法.算法1Step1給出r,0<r<1,初始點x0∈So,容許誤差為ε,令k:=0.Step2形成(QP4),并解(QP4),得到Δy*,進(jìn)而求得(QP2)局部最優(yōu)解ˉx相應(yīng)的Lagrange乘子ˉy.Step3xk+1:=Xkˉx?yk+1:=ˉy.Step4若pk≤ε,則停止,x*:=xk+1;否則,k:=k+1,轉(zhuǎn)Step2.引理1對某一個0<k<∞,如果pk=0,則xk+1為問題(QP1)的K-T點.證明見文獻(xiàn)中.定理2設(shè)以上算法產(chǎn)生的序列為{xk},{yk}收斂,進(jìn)而記ˉx=limk→∞xk,ˉy=limk→∞yk,則ˉx,ˉy對(QP1)是可行的,且ˉx,ˉy滿足一階必要條件和二階必要條件,即Qˉx+c-AΤˉy≥0?ˉX(Qˉx+c-AΤˉy)=0,且對?d∈G,有dTQd≥0.其中ˉy為Ax=b的Lagrange乘子,G={x∈Rn:Ax=0,且eΤjx=0,j∈J},J={j∈{1,2,?,n}:ˉxj=0}證明見文獻(xiàn)中.2xk-k-t下面的問題是如何求解(QP4).為了討論方便,把(QP4)寫成一般形式(QΡ){min12xΤQx+cΤxs.t.∥x∥≤r其中Q∈Rm×m,且QT=Q,Q非奇異,c∈Rm,0<r<1.記λ1,λn分別為Q的最小特征值和最大特征值,xk∈{x∈Rm:∥x∥≤r},讓ρ=λn+η,η≥0,此時(ρI-Q)半正定,因此f(x)=12xΤQx+cΤx≤gk(x)+12(xk)Τ(ρΙ-Q)xkgk(x)=12ρ∥x∥2-xΤ[(ρΙ-Q)xk-c]這樣問題(QP)轉(zhuǎn)化為求解以下凸二次規(guī)劃問題(CQΡ){mingk(x)=12ρ∥x∥2-xΤ[(ρΙ-Q)xk-c]s.t.∥x∥≤r這是一個具有球約束的凸二次規(guī)劃問題.由?gk(x)=0,得到x=(ρΙ-Q)xk-cρ.設(shè)xk+1是(CQP)的一個解,則xk+1={(ρΙ-Q)xk-cρ,當(dāng)[JX-*2][JX*2](ρΙ-Q)xk-cρ[JX-*2][JX*2]≤r時；(ρΙ-Q)xk-c∥(ρΙ-Q)xk-c∥r,當(dāng)[JX-*2][JX*2](ρΙ-Q)xk-cρ[JX-*2][JX*2]>r時；(2)定理3設(shè)x0∈{x∈Rm:∥x∥≤r}是任意給定的一點,那么迭代公式(2)產(chǎn)生的點列{xk}的每一個聚點x*都是(QP)的K-T點.證明因為xk+1是(CQP)的解,所以xk+1滿足(CQP)的K-T條件{ρxk+1-[(ρΙ-Q)xk-c]+λk+1xk+1=012λk+1(∥xk+1∥2-r2)=0,λk+1≥0(3)[ΚΗ*3D](4)其中λk+1是Lagrange乘子.顯然‖xk‖≤r,k=1,2,…,因此{(lán)xk}是有界的.不失一般性,設(shè)limk→∞xk=x*,如果‖xk‖<r,那么λk+1=0;如果‖xk‖=r,那么在式(3)兩邊關(guān)于xk+1做內(nèi)積得λk+1=?(ρΙ-Q)xk-c,xk+1?-ρr2r2,因此λ*=limk→∞λk+1=?(ρΙ-Q)x*-c,x*?-ρr2r2=-(x*)ΤQx*-cΤx*r2.綜上所述有ˉλ*={λ*?∥x∥=r0,∥x∥<r.在式(3)和(4)兩邊取極限得{Qx*+c+ˉλ*x*=0,12ˉλ*(∥x*∥2-r2)=0,ˉλ*≥0(5)[ΚΗ*3D](6)式(5)和(6)恰好是(QP)的K-T條件,因此x*是(QP)的一個K-T點,ˉλ*是Lagrange乘子.于是得到算法2.算法2Step1設(shè)x0∈{x∈Rm:x≤r}?η≥0,容許誤差ε>0,ρ=λn+η,k:=0.Step2解(CQP)得到xk+1={(ρΙ-Q)xk-cρ,當(dāng)[JX-*2][JX*2](ρΙ-Q)xk-cρ[JX-*2][JX*2]≤r時(ρΙ-Q)xk-c∥(ρΙ-Q)xk-c∥r,當(dāng)[JX-*2][JX*2](ρΙ-Q)xk-