二次规划问题

1、序列二次规划法求解一般线性优化问题：min f (x)工hi(x) = 0,i E 二1,.ms.t.lg(x) K0,i e !1,.耐(1.1)基本思想：在每次迭代中通过求解一个二次规划子问题来确定一个下降方向，通过减少价值函数来获取当前迭代点的移动步长， 重复这些步骤直到得到原问题的 解。1.1等式约束优化问题的 Lagrange-Newton法考虑等式约束优化问题min f(x)s.t.h j (x) = 0, j E 二1,.,m(1.2)其中f : Rn R, hi : Rn R(i E)都为二阶连续可微的实函数.记 h(x) =(h(x)，,hm(x)T 则(1.3)的Lagra

2、nge函数为：mL(x,u)二 f (x)嘉 ui * hj(x)二 f (x) _uT * h(x)i=1(1.3)其中u =（U1,U2,., Um）T为拉格朗日乘子向量。约束函数 h(x)的 Jacobi矩阵为：A(x)二、h(x)T = C g(x)，八 hm(x)T .对（1.3）求导数，可以得到下列方程组：T*ul=0（1.4）现在考虑用牛顿法求解非线性方程（1.4）.v L（x,u）的 Jacobi矩阵为：W（x,u）A（x厂h(Xk)(1.6)的解。注意：只要A(Xk)行满秩且 W(Xk,uQ是正定的，那么(1.6)的系数矩阵非奇异，且方程组有唯一解。引理1：已知矩阵URnn,

3、SRn m，则对任意满足ST*x=O的非零向量x都有xTUx 0 的充要条件是存在常数 c*0，使得对任意的書一書*都有xT*(U；*S*S T)x 0,-x = 0 Rn.证明略。鉴于方程组(1.6)的求解数值不稳定，故考虑将它转化成一个严格凸二次规划问题.转化的条件是(1.4)的解点X处的最优性二阶充分条件成立，即对满足A(x )T*d =0的任一向量 d = 0，成立 d *W(x ,u )* d 0。1再由引理1知：当 -0充分小时， W(x*,u*)A(X*)T A(x*)正定。2考虑(1.6)中的W(Xk,uk)用一个正定矩阵来代替，记1B(XkukW(Xkuk) 2TA(Xk)T

4、A(X)则当(Xk,uQ； (x ,u )时，矩阵B(x ,u )正定。(1.6)的第一个展开式为W(Xk,uJ*d k-A(Xk)T *Vkf(Xk) A(xJT*Uk将上式变形为：1 1W(Xk,uQA(xQTA(Xk)*d k-A(Xk)T*Vk 山A(xjdk f (xj2令 Uk：=Vk Uk A(Xk)Tdk 后得：B(Xk,Uk)*d k - A(x* Uk =f (xQ . 2t因此，(1.6)等价于Xk,Uk)-A(xk)T *Pf(Xk)、A(xk)0?h(x k)丿(1.7)进一步，可以把方程(1.7 )转换成如下严格凸二次规划：min qO =：dTB(Xk,Uk)d

5、f(x k)Td2s.t h (x k) + A(x k) d = 0（1.8）方程（1.7）和（1.8）具有同解的。12 般形式的约束优化问题将1.1节中构造二次规划子问题求解等式约束优化问题的思想推广到一般形式的约束优化问题（1.5）。在给定点Zk =（Xk,Uk, -k）后，将约束函数线性化，并对拉格朗日函数进行二次多项式近似，得到下列二次规划子问题：1mindTW(xk,uk)d i f(x k)Td2h(xj f (xjd =0,i E S.t 0为罚参数，gi（x）_ =max0, gj（x）。为了保证SQR方法的全局收敛性，通常借助价值函数来确定搜索步长。用来衡量一维 搜索的好坏

6、。算法（一般约束优化问题的SQP方法）Step 0:给定初始点（x,u。，0）Rn Rm Rm2,对称正定矩阵B。，Rn.计算A 二 h(x)T , A0 八 g(x)T, Ao =选择参数1（o,2）,（0,1）,容许误差 oL1, 2 _ 1,令 k =0.Step 1:求解子问题（1.10）得最优解dk.Step 2:若 |dk |1 兰色且 |hk |1 +|(gk)_|h&2 ,stop，得到(1.1)的一个近似 KT 点(xk , uk，几 k).Step 3:对于某种价值函数 （x），选择罚参数 J，使得dk是该函数在Xk处的下降方向。Step 4:Armijo搜索.令mk是使下

7、列不等式成立的最小非负整数m:G（Xk mdk,；k）（Xkfk） ：； m（Xk,6；d k）,令 ak : = ?mk, Xk 1 :=Xk - akdk.Step 5: 计算Ak 1 =h(xk 1),人 1 = h(xk 1), Ak 1 =以及最小二乘乘子t =Ak 1Ak 1Ak V fk 1Step 6:校正矩阵Bk为Bk 1 .令BkSkSk Bk .Sk BkQSk =akdk,ykxL(Xk d,Uk 1, k 1) 一、xL(Xk,山 1, 1)Bk 1 = Bk其中Zkkyk（1 一入）BkSk参数入定义为1,SkYk -0.2s： BkSk纵詔 0.8s： Bkskn

8、o t _T ,skyk 2sk Bk skiSk Bksk _sk ykStep 7：令 k:=k 1,转 1.注意：(step 1)利用K-T条件，问题(1.10)等价于Hi(d,u, ) =Bkd-(AE)Tu-(A；)J f(Xk) =0,H2(d,u, ) =h(Xk) Ae d =0, _0,g(Xk) A；d _ 0, g(Xk) A； d =0.第三式是m2维互补问题，定义光滑函数(1.11)：（；,a,b）二a b- a2 b22；2其中；0为光滑参数.令:：J（ ；,a,b）=（门1（ ；,a,b）,：（ ；,a, b）T，其中：:（；,a,b） = i gi（Xk） （A

9、k）id- ：2一（兀）（Ak）id222其中（Ak）i表示Ak的第i行.记z =（ ；,d,u, ） R . Rn Rm ，那么（1.11 ）问题等价H(z):=H(；,d,u,)理1|H1(d,u,k)H2(d,u,h)恥,d,k) 一则H （z）的Jacobi矩阵为-100H (z) =0Bk-(AE)0AE0VD2(z)A；00 1-(小0U(z) 一其中V八门（；,d ,，）二（V1,., Vm2）T ,V由下式确定:Vi2E.i2 gi(Xk) (Ak)id222而 D1 (z)二diag(a1(z),., ag(z), D2(z)二 diag(b!(z),., bm? (z)，其中 ajz),bi(z)由下式确定:ai.f gg (Ak)id2 22h =1 gg+(A；)id.i2 gi(Xk) (Ak)id22；2给定参数(0,1)，定义非负函数z)=|H(z)|mi n1,|H(z)|.(step 3)中选择价值函数1G(x,；)= f(x) |h(x)|1 |g(x)_|1CT可令 p umax uk H川紅 |, gi(x)_