基于仿射尺度方法的二次规划问题求解

基于仿射尺度方法的二次规划问题求解

二规划问题的求解是数学规划和工业应用的一个重要课题，也是解决一般非线性规划问题的二次规划算法的关键。在第一次解决二次规划问题时，使用了线性规划的简单方法和有效集法。1968年，该算法由karak提出。在提出了解算方法的内部算法后，许多人使用了模仿参数算法进行非线性计算。在本研究中，基于模仿参数方法的概念，将一般不确定的二次规划问题转化为球限制的二次规划问题，并将二次规划问题转化为球限制的凸二次规划问题，丰富了二次规划问题的方法体系。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},∥⋅∥代表欧氏范数.给一初始可行点xk∈SO,使用仿射尺度技术,产生子二次规划问题其中:=XkQXk;=Xkc;Xk=diag(xk);=AXk;0<r<1.令Δx=x-e,这样(QP2)可以写成:记为的零空间的一组标准正交基,由于∈Rm×n,秩()=m,则∈Rn×(n-m).令Δx=Δy,这样(QP3)就变成为如果得到(QP4)的一个局部最优解为Δy*,也就得到了(QP2)的局部最优解,从而也就产生了原问题的下一个迭代点xk+1=Xkˉx.定理1q(xk+1)≤q(xk)证明由于q(xk)=(e),q(xk+1)=().对(x)来说,e为初始可行点,为局部最优点,故有ˉq(ˉx)≤ˉq(e).也即q(xk+1)≤q(xk).由于是(x)的局部最优解,故满足下列条件{ˉ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为相应的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*,进而求得(QP2)局部最优解ˉx相应的Lagrange乘子ˉy.Step3xk+1:=Xkˉx‚yk+1:=ˉy.Step4若pk≤ε,则停止,x*:=xk+1;否则,k:=k+1,转Step2.引理1对某一个0<k<∞,如果pk=0,则xk+1为问题(QP1)的K-T点.证明见文献中.定理2设以上算法产生的序列为{xk},{yk}收敛,进而记ˉ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}证明见文献中.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)转化为求解以下凸二次规划问题(CQΡ){mingk(x)=12ρ∥x∥2-xΤ[(ρΙ-Q)xk-c]s.t.∥x∥≤r这是一个具有球约束的凸二次规划问题.由ᐁgk(x)=0,得到x=(ρΙ-Q)xk-cρ.设xk+1是(CQP)的一个解,则xk+1={(ρΙ-Q)xk-cρ,当[JX-*2][JX*2](ρΙ-Q)xk-cρ[JX-*2][JX*2]≤r时；(ρΙ-Q)xk-c∥(ρΙ-Q)xk-c∥r,当[JX-*2][JX*2](ρΙ-Q)xk-cρ[JX-*2][JX*2]>r时；(2)定理3设x0∈{x∈Rm:∥x∥≤r}是任意给定的一点,那么迭代公式(2)产生的点列{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,…,因此{xk}是有界的.不失一般性,设limk→∞xk=x*,如果‖xk‖<r,那么λk+1=0;如果‖xk‖=r,那么在式(3)两边关于xk+1做内积得λ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设x0∈{x∈Rm:x≤r}‚η≥0,容许误差ε>0,ρ=λn+η,k:=0.Step2解(CQP)得到xk+1={(ρΙ-Q)xk-cρ,当[JX-*2][JX*2](ρΙ-Q)xk-cρ[JX-*2][JX*2]≤r时(ρΙ-Q)xk-c∥(ρΙ-Q)xk-c∥r,当[JX-*2][JX*2](ρΙ-Q)xk-