二次规划问题

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)=(t(x),.,hm(x)T.贝0台)的Lagrange函数为：mL(x,u)=f(x)-ui*hi(

2、x)=f(x)-uT*h(x)i1(1.(3)其中u=(U1,U2,.,Um)T为拉格朗日乘子向量。约束函数h(x)的Jacobi矩阵为：A(x)=h(x)T=($%(刈,.，Vhm(x)T.对(1.3)求导数，可以得到下列方程组：“4LC：；造尸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)=7xxL(x,u)=72f(x)-Z5*V2hi(x)是拉格朗日函数L(x,u)关于x的i4Hessen矩阵.N(x,u)也称为K-T矩阵。对于给定的点4=(xk，Uk),牛

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

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

5、Xk)221令Uk:=Vk+Uk+丁A(Xk)%k后得：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)=2dB(Xk,Uk)drf(Xk)ds.th(Xk)+A(xk)d=0(1.8)方程(1.7)和(1.8)具有同解的。1.2一般形式的约束优化问题将1.1节中构造二次规划子问题求解等式约束优化问题的思想推广到一般形式的约束优化问题(1.5)。在给定点Zk=(Xk,Uk,%)后，将约束函

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

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

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

9、>0为罚参数,gi(x)_=max0,-g"x)。为了保证SQR方法的全局收敛性，通常借助价值函数来确定搜索步长。用来衡量一维搜索的好坏。算法(一般约束优化问题的SQP方法)Step0:给定初始点(x0,u0,%)WRnMRMRm2,对称正定矩阵B0亡Rn.计算AE=Vh(Xo)T,N=Vg(Xo)T,A。=选择参数，c1、c,e(0,-),Pw(0,1),容许误差0=鸟32=1，令k:=o.Step1:求解子问题（1.10）得最优解dk.Step2:若|dk|i<£）且|hk|1+|（gk）_|1Ww2，stop,得到（1.1）的一个近似KT点（Xk,uk,&

10、#39;k）.Step3：对于某种价值函数（x,。），选择罚参数仃使得dk是该函数在Xk处的下降方向。Step4:Armijo搜索.令mk是使下列不等式成立的最小非负整数m:中（Xk：mdk,；=k）一：'（4,二k）-（Xk,；k；dk）,Step5:计算令ak:=：；mk,Xk1:=Xk.akdk.Ak1='h(Xk1),Ak1=1h(Xk1),Ak1=以及最小二乘乘子Step6:校正矩阵民为Bk»令sk=akdk，yk-TXL(Xk1,uk1,'kJ-vXL(Xk,uk')BkSkBk.ZkZTBk1-BktDTSkBkSkSkZk其中Zk-&q

11、uot;kyk(1-"k)BkSk参数率定义为1,skyk一°.2skBksk6k=00.8sTBkskt=kY<0.2SkBkSk、SkBkSk-SkYkStep7：令k:=k+1,转1.注意：(step1)利用K-T条件，问题(1.10)等价于Hi(d,u,)=Bkd-(AE)Tu-(Ak)T-"(Xk)=0,H2(d,u,K)=h(Xk)+AEd=0,(1.11).0,g(Xk)Akd.0,g(Xk)A：d=0.第三式是m2维互补问题，定义光滑函数邛(；，a,b)=ab_.a2b22；2其中注>0为光滑参数.令中”,a,b)=(1(%a,b),.

12、,Gm2(%a,b)T,其中匕(；,a,b)=igi(Xk)(Ak)id-2gi(Xk)-(Ak)id22；2其中（Ak）i表示A；的第i行.记z=（"d,u/，.）wRQRnxRmRm2，那么（1.11）问题等价%1H(z):=H(；,d,u,)|H1(d,u,九)H2(d,u,九),Gd,九)一则H的Jacobi矩阵为一10000Bk-(ae)t1-(A)0AE00-vD2(z)A；0D1(z)H(z)=T2；其中v=V弁(邑d,K)=(v1,.,Vm2)T,Vi由下式确定:vi=-：1；.i2gi(Xk)(Ak)id22；2而D(z)=diag(a1(z),.,am2(z),D2(z)=diag(t(z),.,bm2(z),其中ai(z),bi(z)由下式确定：.i2gi(xk)(Ak)id22;2g(xk)(Ak)id,i2gi(xk)(Ak)id22；2给定参数V(0,1),定义非负函数：(z)=|H(z)|min(1,|H(z)|).(step3)中选择价值函数,1：，(xQ=f(x)|h(x)|1|g(