序列二次規(guī)劃算法

1、序列二次規(guī)劃法求解一般線性優(yōu)化問題:minf(x)h(x)二0,ieE二l,.,ms.t.<i1g(x)>0,ieI二l,.,mi2(1.1)基本思想：在每次迭代中通過求解一個二次規(guī)劃子問題來確定一個下降方向，通過減少價值函數(shù)來獲取當(dāng)前迭代點的移動步長，重復(fù)這些步驟直到得到原問題的解。1.1等式約束優(yōu)化問題的Lagrange-Newton法考慮等式約束優(yōu)化問題minf(x)s.t.h(x)二0,jeE二l,.,mj(1.2)其中f:RntR,h:RnTR(ieE)都為二階連續(xù)可微的實函數(shù).i記h(x)=(h(x),.,h(x)t.lm則(1.3)的Lagrange函數(shù)為：L(x,u

2、)=f(x)-£u*h(x)=f(x)一ut*h(x)iii=1(1.3)其中u=(u,u,.,u)T為拉格朗日乘子向量。l2m約束函數(shù)h(x)的Jacobi矩陣為：A(x)=Vh(x)t=(Vh(x),.,Vh(x)t.lm對(1.3)求導(dǎo)數(shù)，可以得到下列方程組：VL(x,u)xVf(x)一A(x)t*uVL(x,u)u-h(x)=0VL(x,u)=1.4)現(xiàn)在考慮用牛頓法求解非線性方程(1.4).VL(x,u)的Jacobi矩陣為:N(x,u)='W(x,u)<A(x)-A(x)T)1.5)其中W(x,u)二'L(x,u)二'2f(x)u*V2h(x

3、)是拉格朗日函數(shù)L(x,u)關(guān)于x的xxiii=1Hessen矩陣.N(x,u)也稱為K-T矩陣。對于給定的點z=(x,u)，牛頓法的迭代格式為：z=z+Az.kkkk+1kk其中曲=(dk'vk)是線性方程組'W(x,u)kk.-A(x)k-A(x)t)*k-Vf(x)+A(x)tukkk、h(x)k1.6)的解。注意：只要A(x)行滿秩且W(x,u)是正定的，那么(1.6)的系數(shù)矩陣非奇異，且方程組kkk有唯一解。引理1：已知矩陣UeRnxn,SeRn®，則對任意滿足St*x=0的非零向量x都有xTUx>0的充要條件是存在常數(shù)b*>0，使得對任意的*都

4、有xt*(U+a*S*St)x>0,Vx豐0eRn.證明略。鑒于方程組(1.6)的求解數(shù)值不穩(wěn)定，故考慮將它轉(zhuǎn)化成一個嚴(yán)格凸二次規(guī)劃問題.轉(zhuǎn)化的條件是(1.4)的解點x*處的最優(yōu)性二階充分條件成立，即對滿足A(x*)t*d=0的任一向量d豐0，成立dT*W(x*,u*)*d>0。1再由引理1知：當(dāng)e>0充分小時，W(x*,u*)+A(x*)TA(x*)正定。2t考慮(1.6)中的W(x,u)用一個正定矩陣來代替，記kk1B(x,u)=W(x,u)+A(x)tA(x)kkkk2ekk則當(dāng)(x,u)T(x*,u*)時，矩陣B(x*,u*)正定。kk(1.6)的第一個展開式為W(x

5、,u)*d-A(x)t*v=-Vf(x)+A(x)t*ukkkkkkkk將上式變形為：11W(x,u)+一A(x)tA(x)*d-A(x)t*v+u+一A(x)d=-Vf(x)kk2Tkkkkkk2Tkkk1令U,:二v+u+A(x)Td后得:kkk2kkB(x,u)*d-A(x)T*ukk=-Vf(xk)-因此，(1.6)等價于'B(x,u)kkA(x)k-A(x)t'k*(d)k0丿(uk丿kk(Vf(x)k.h(x)丿k1.7)進一步，可以把方程(1.7)轉(zhuǎn)換成如下嚴(yán)格凸二次規(guī)劃:minq(d)=drB(x,u)d+Vf(x)rdk2kkks.th(x)+A(x)d=0k

6、k1.8)方程(1.7)和(1.8)具有同解的。1.2一般形式的約束優(yōu)化問題將1.1節(jié)中構(gòu)造二次規(guī)劃子問題求解等式約束優(yōu)化問題的思想推廣到一般形式的約束優(yōu)化問題(15)。在給定點z=(x,u,九)后，將約束函數(shù)線性化，并對拉格朗日函數(shù)進行二次kkkk多項式近似，得到下列二次規(guī)劃子問題:mindTW(x,u)d+Vf(x)td2kkkh(x)+Vh(x)td=0,ieEs.t<ikikg(x)+Vg(x)td=0,ieIikik(19)其中E=l,.,m,I=,W=W(x,u,九)=V2L(x,u,X)，拉格朗日函數(shù)為2kkkkxxkkkL(x,u)=f(x)一區(qū)u*h(x)一遲X*g(x

7、).iiiii=li=l于是，迭代點x的校正步d以及新的拉格朗日乘子估計量u,X可以分別定義為問題kkk+lk+l的一個K-T點x*和相應(yīng)的拉格朗日乘子向量u*,九*定理1：給定約束優(yōu)化問題(1.1)的最優(yōu)解d*和相應(yīng)的拉格朗日乘子u*,九*>0.假定在x*處，下面的條件成立：(1) 有效約束的Jacobi矩陣J*行滿秩，其中s(x*)=eU心*)；S(x*)(2) 嚴(yán)格互補松弛條件成立，即g(x*)>0,九*>0,九*g(x*)二0,g(x*)+九*>0；iiiiii(3) 二階最優(yōu)性充分條件成立，即對滿足A(x*)t*d=0的任一向量d豐0，成立dT*W(x*,u*

8、,九*)*d>0.那么若(x,u,九)充分靠近(x*,u*,九*)，則二次規(guī)劃問題(1.9)存在一個局部極小點d*，kkk使得其對應(yīng)的有效約束指標(biāo)集S(d*)與原問題在x*處的有效指標(biāo)集S(x*)是相同的。注意:在構(gòu)造二次規(guī)劃子問題時，需要計算拉格朗日函數(shù)在迭代點x處的Hessen矩陣，k計算量過大。為了克服這個缺陷，韓世平基于牛頓-拉格朗日法提出了一種利用對稱正定矩陣B來代替拉格朗日矩陣W的序列二次規(guī)劃法。kk對于一般約束優(yōu)化問題(1.1)，在迭代點z=(x,u,九)，構(gòu)造下列形式的二次規(guī)劃子kkkk問題：min1dTB(x,u)d+Vf(xd2kkk'h(x)+Vh(x)td

9、=0,ieE(1,10)S.t<ikikg(x)+Vg(x)td=0,ieIikik并且用(110)的解d作為原問題變量x在第k次迭代過程中的搜索方向。其中d有kk一個好的性質(zhì)是它許多罰函數(shù)(價值函數(shù))的下降方向。例如，對于L1精確罰函數(shù)：P(XQ)=f(x)+丄工lh(x)l+工lg(x)_IaiiieEieI其中a>0為罰參數(shù)，g(x)_=max0,-g(x)。ii為了保證SQR方法的全局收斂性，通常借助價值函數(shù)來確定搜索步長。用來衡量一維搜索的好壞。算法(一般約束優(yōu)化問題的SQP方法)Step0:給定初始點(x,u,九)eRnxRmxR對稱正定矩陣BeRn.0000計算AeA

10、e=Vh(x)t,Ai=Vg(x)t,A=0oooooAi0選擇參數(shù)“(O，Pe(QI),容許誤差0*£2h令k：=O.Step1:求解子問題(1.10)得最優(yōu)解d.kStep2:若lidII<£且IIhII+11(g)_ll<£,stop,得到(1.1)的一個近似KT點(x,u,九).k11k1k12kkkStep3:對于某種價值函數(shù)(x,a)，選擇罰參數(shù)a，使得d是該函數(shù)在x處的下降方向。kkkStep4:Armijo搜索.令m是使下列不等式成立的最小非負整數(shù)m:k(x+pmd,a)(x,a)<pmO'(x,a;d),kkkkkkkk

11、令a:=pmk,x:=x+ad.kk+ikkkStep5:計算AE=Vh(x)T,Ai=Vh(x)T,Ak+1k+1k+1k+1k+1以及最小二乘乘子uk+1九k+1Step6:校正矩陣B為B令kk+1其中參數(shù)0定義為kAVfk+1k+1Aek+1Aik+1=ad,y=VL(x,u,九)VL(x,u,九)kkkxk+1k+1k+1xkk+1k+1BssTBzzTB=B一kkkk+kkk+1ksTBssTzkkkkkz=0y+(10)Bskkkkkk1,sy>0.2stBskkkkkStep7:令k:=k+1,轉(zhuǎn)1.o.8sTBsk-k,sysTBssTykkkkkkk<0.2stB

12、skkk注意：(step1)利用K-T條件，問題(1.10)等價于H(d,u,九)二Bd-(Ae)tu-(Ai)tX+Vf(x)二0,1kkkkH(d,u,X)二h(x)+Aed二0,(111)2kkX>0,g(x)+Aid>0,Xg(x)+Aid二0.kkkk第三式是m維互補問題，定義光滑函數(shù)2(£,a,b)二a+b-Ja2+b2+2e2其中*>0為光滑參數(shù)令(s,a,b)=(s,a,b),.,(&,a,b)T，1m2其中(s,a,b)=X+g(x)+(A1)dX2+g(x)+(A1)d2+2s2iiikkiiikkiki其中(Ai)表示Ai的第i行.記z

13、=(s,d,u,X)eRxRnxRxRm2，那么(1.11)問題等價k*H(z):=H(£,d,u,X)H(d,u,X)1H(d,u,X)2(*,d,X)則H(z)的Jacobi矩陣為H'=0BkAEkD(z)Ai2k0-(AE)Tk000-(Ai)Tk0D(z)1m2其中v=VgO(E,d,X)=(，vm)T，vi由下式確定:2*1定：而D=diag(a(z),.，a(z),D=diag(b(z),.，b(z)，其中a(z),b由下式確1m221m2iiX.X2+g(x)+(A1)d2+2s2iikkib=1.盯化)+(Ak)d°X2+g(x)+(Ai)d2+2s2¥iikki給定參數(shù)丫w(0,1)，定義非負函數(shù)卩(z)二丫IIH(z)llmin1,llH(z)ll.(step3)中選擇價值函數(shù)0(XQ)二f(x)+丄llh(x)ll+llg(x