序列二次规划算法

1、序列二次规划法求解一般线性优化问题minf(x)h(x)=0,iE=1,.,mjs.t.gi(x)_0,iI=1,.,m2)(1.1)基本思想：在每次迭代中通过求解一个二次规划子问题来确定一个下降方向，通过减少价值函数来获取当前迭代点的移动步长，重复这些步骤直到得到原问题的解。1.1等式约束优化问题的Lagrange-Newtoife考虑等式约束优化问题minf(x)s.t.hj(x)-0,jE-1,.,m(1.2)其中f:RnTR,n:RnTR(iWE)都为二阶连续可微的实函数.记h(x)=(n(x),.,hm(x)T.贝0台)的Lagrange函数为：mL(x,u)=f(x)-ui*hi(

2、x)=f(x)-uT*h(x)i1(1.(3)其中u=(Ui,U2,.,Um)T为拉格朗日乘子向量。约束函数h(x)的Jacobi矩阵为：A(x)=h(x)T=(Vh1(x),.,Vhm(x)T.对(1.3)求导数，可以得到下列方程组：卡L器造尸x)T*ul(1.(4)现在考虑用牛顿法求解非线性方程(1.4).L(x,u)的Jacobi矩阵为：W(x，U)-A(x)T'A(x)0)(1.(5)m其中W(x,u)=VxxL(x,u)=W2f(x)-£5*V2hi(x)是拉格朗日函数L(x,u)关于x的i1Hessen矩阵.N(x,u)也称为K-T矩阵。对于给定的点Zk=(xk，

3、Uk),牛顿法的迭代格式为：zk+=zk+izk.其中以=(dk,Vk)是线性方程组W(xk,uk)-A(xk)-A(xk)T01Vk)f(xk)+A(xk)Tuk<h(xk)(1.(6)的解。注意：只要A(xQ行满秩且W(xk,")是正定的，那么(1.6)的系数矩阵非奇异，且方程组有唯一解。引理1：已知矩阵UwRnSwRn小，则对任意满足ST*x=0的非零向量x都有xTUx0的充要条件是存在常数仃*>0,使得对任意的仃之仃*都有xT*(U二*S*ST)x0x=0Rn.证明略。鉴于方程组(1.6)的求解数值不稳定，故考虑将它转化成一个严格凸二次规划问题.转T化的条件是(1

4、.4)的解点x处的最优性二阶充分条件成立，即对满足A(x)T*d=0的任一向一一>、T*重d#0,成立d*W(x,u)*d>0O再由引理1知：当EA0充分小时，W(x*,u*)+-A(x*)TA(x*)正定。2考虑(1.6)中的W(xk,uk)用一个正定矩阵来代替，记1_T_B(xk,见)=W(xkU)A(xk)A(xk)2则当(xk,uk)T(x,u)时,矩阵B(x,u)正定。(1.(6) 一个展开式为W(Xk,uJ*dk-A(xk)T*vk=-"%)A(xJT*Uk将上式变形为：11W(Xk，Uk)A(Xk)TA(Xk)*dk-A(Xk)T*VkUkA(xQdk=f(

5、xQ1令Uk:=Vk+Uk+A(xjdk后得：B(Xk,Uk)*dk-A(Xk)T*Uk=-Vf(Xk).2因此，(1.6)等价于B(Xk,Uk)A(Xk)-A(xk)T0<Uk>Rf%)、h(Xk)(1.(7)进一步，可以把方程(1.7)转换成如下严格凸二次规划：1T.Tminqk(d)=QdB(Xk,Uk)drf(Xk)dsth(xk)+A(xk)d=0(1.(8)方程(1.7)和(1.8)具有同解的。1.2一般形式的约束优化问题将1.1节中构造二次规划子问题求解等式约束优化问题的思想推广到一般形式的约束优化问题(1.5)。在给定点Zk=(Xk，Uk，九k)后，将约束函数线性化

6、，并对拉格朗日函数进行二次多项式近似，得到下列二次规划子问题：1min-dW(Xk,Uk)d%、f(xjdfh(Xk)+h(Xk)Td=0,iwEs.tT9(Xk)gi(Xk)d=0,iI(1.9)其中E=1,.,m1,I=1,.m2,Wk=W(Xk,Uk&k)=vXxL(Xk,Uk,%),拉格朗日函数为m1m2L(x,U)=f(x)-%Ui*hi(x)J*gi(x).i1i1于是，迭代点Xk的校正步dk以及新的拉格朗日乘子估计量Uk书，九k书可以分别定义为问题的一个K-T点X*和相应的拉格朗日乘子向量u*,九*。定理1:给定约束优化问题(1.1)的最优解d*和相应的拉格朗日乘子u*,

7、2*之0.假定在X*处，下面的条件成立：(1) 有效约束的Jacobi矩阵JS(x*)行满秩，其中s(x*)=eU(x*)；(2) 严格互补松弛条件成立，即gi(x*)>0,>H*>0,?H*gi(x*)=0,gi(x*)+?/>0;(3) 二阶最优性充分条件成立，即对满足A(x)T*d=0的任一向量d#0,成立dT*W(x,u,)*d0.*那么若(xk,uk,Zk)充分靠近(x,u，九)，则二次规划问题(1.9)存在一个局部极小点d,使得其对应的有效约束指标集S(d)与原问题在x处的有效指标集S(x)是相同的。注意：在构造二次规划子问题时，需要计算拉格朗日函数在迭代点

8、xk处的Hessen矩阵,计算量过大。为了克服这个缺陷，韩世平基于牛顿-拉格朗日法提出了一种利用对称正定矩阵Bk来代替拉格朗日矩阵四的序列二次规划法。对于一般约束优化问题(1.1),在迭代点zk=(xk,uk,九k),构造下列形式的二次规划子问题:1r(1.10)mindB(xk,uk)d1f(xk)d2hi(xk)rhi(xk)Td=0,iEst«丁gi(xk)vgi(xk)d=0,iI并且用(1.10)的解dk作为原问题变量x在第k次迭代过程中的搜索方向。其中dk有一个好的性质是它许多罚函数(价值函数)的下降方向。例如，对于L1精确罚函数：_1一一P(x,。)=f(x)|hi(x

9、)|gi(x)_|i壬iI其中仃>0为罚参数,gi(x)_=max0,-gi(x)0为了保证SQR方法的全局收敛性，通常借助价值函数来确定搜索步长。用来衡量一维搜索的好坏。算法(一般约束优化问题的SQP方法)Step0:给定初始点(x0,u0,%)WRnMRmRm2,对称正定矩阵B0亡Rn.计算AE=h(x0)T,Ng(x°)T,选择参数Step1:Step2:(Xk，Uk，Step3:Step4:Step5:1、“八e（0,-）,P（0,1）,容许误差0=的，叼=1，令k:=0.2求解子问题（1.10）得最优解dk.若|dk|1"且|hk|1+|（gk）_lli&#

10、171;4,stop,得到（i.i）的一个近似kt点对于某种价值函数（x,。），选择罚参数仃k,使得dk是该函数在Xk处的下降方向。Armijo搜索.令mk是使下列不等式成立的最小非负整数m:中区：mdk,；，）一：'（4,八）m：ml'（xk,；=k;dk）,大ak计算：mk,xk.1>xkakdkAk1='h(xk1),Ak1='h(xk1),Aki=以及最小二乘乘子；UkK=jAk书Ak书T，Ak+fk+1Step6:其中校正矩阵艮为Bk+.令sk=akdk,yk=VxL(xk1,uk1,xL(xk,uk1,1)民1=BkBkSkSTBk.sTBkS

11、kTZkZkCkZk"kYk.(1-A)Bksk参数8k定义为1,SkYk_0.2sTBksk%=00.8sTBksktTckkTk，Skyk<0.2SkBkSk科BkSk-SkykStep7：令k:=k+1,转1.注意：(step1)利用K-T条件，问题(1.10)等价于Hi(d,u,)=Bkd-(AE)Tu-(Ak)'"(Xk)=0,(1.11)问题等价H2(d,u,)=h(Xk)AEd=0,.0,g(Xk)Akd.0,g(Xk)A：d=0.第三式是m2维互补问题，定义光滑函数邛(；，a,b)=ab_.a2b22；2其中注>0为光滑参数.令G(%a,

12、b)=(G1(%a,b),.gm2(w,a,b)T,其中匕(；,a,b)=igi(Xk)(Ak)id-gi(Xk)(Ak)id22；2其中(Ak)i表示A；的第i行.记z=(%d,u&)wR+xRnxRmRm2，那么(1.11)%1H(z):=H(；,d,u,)=|H1(d,u,九)H2(d,u,九)b(,d,九)一则H的Jacobi矩阵为一10000Bk-(ae)ti-(A)0AE00-VD2(z)Ak0D1(z)TH(z)=2；其中v=v弁(旬d,K)=(V1,.,Vm2)T,Vi由下式确定:vi=-：1；.i2gi(Xk)(Ak)id22；2而D1(z)=diag(a1(z),.,am2(z),02(z)=diag(t(z),.,bm2(z),其中a(z),bi(z)由下式确定：a=1,一2I22,i2gi(xk)(Ak)id22；2gi(xk)(Ak)idR=1-,'i2gd(A：)id2给定参数¥三(0,1),定义非负函数：(z)=|H(z)|min(1,|H(z)|).(step3)中选择价值函数1：，(x,；)=f(