求解二次规划问题的拉格朗日及有效集方法

1、求解二次规划问题的拉格朗日及有效集方法最优化方法课程实验报告学 院:数学与统计学院班 级：硕2041班学 号：指导教师：同组人：钱东东求解二次规划问题的拉格朗日及有效集方法摘要二次规划师非线性优化中的一种特殊情形，它的目标函数是二次实函数，约 束函数都是线性函数。由于二次规划比较简单，便于求解（仅次于线性规划）， 并且一些非线性优化问题可以转化为求解一些列的二次规划问题，因此二次规划 的求解方法较早引起人们的重视，称为求解非线性优化的一个重要途径。二次规 划的算法较多，本文仅介绍求解等式约束凸二尺规划的拉格朗日方法以及求解一 般约束凸二次规划的有效集方法。关键字：二次规划，拉格朗日方法，有效集

2、方法。【目录】 TOC o 1-5 h z 摘要-1- HYPERLINK l bookmark16 o Current Document 1等式约束凸二次规划的解法-3- HYPERLINK l bookmark19 o Current Document 1.1问题描述-3- HYPERLINK l bookmark22 o Current Document 1.2拉格朗日方法求解等式约束二次规划问题-3- HYPERLINK l bookmark25 o Current Document 1.2.1拉格朗日方法的推导-3- HYPERLINK l bookmark31 o Current

3、Document 1.2.2拉格朗日方法的应用-4- HYPERLINK l bookmark36 o Current Document 2一般凸二次规划问题的解法-5- HYPERLINK l bookmark39 o Current Document 2.1问题描述-5- HYPERLINK l bookmark43 o Current Document 2.2有效集法求解一般凸二次规划问题-6- HYPERLINK l bookmark46 o Current Document 2.2.1有效集方法的理论推导-6- HYPERLINK l bookmark49 o Current Doc

4、ument 2.2.2有效集方法的算法步骤-9-2.2.3有效集方法的应用-10-3总结与体会-11-4附录-11- HYPERLINK l bookmark61 o Current Document 4.1拉格朗日方法的matlab程序-11- HYPERLINK l bookmark73 o Current Document 4.2有效集方法的Matlab程序-11-1等式约束凸二次规划的解法1.1问题描述我们考虑如下的二次规划问题f 1 ，-min 2xtHx + ctx, ( s.t. Ax = b其中H e Rnxn对称正定，A e Rmxn行满秩，c,x G Rn，b e Rm。1

5、.2拉格朗日方法求解等式约束二次规划问题1.2.1拉格朗日方法的推导首先写出拉格朗日函数：L(x,人)=2 xtHx + ctx -Xt (Ax - b)， (1.2)令V L(x, X) = 0,V/(x, X) = 0，得到方程组Hx - ATX = -c,-Ax=-b.将上述方程组写成分块矩阵形式：；At x X=- c -b.(1.3)我们称伤处方程组的系数矩阵H -AT-A 0为拉格朗日矩阵。下面的定理给出了线性方程组(1.1)有唯一解的充分条件。定理1设H e Rmxn对称正定，A e Rm、n彳丁满秩。若在问题(1.1)的解x*处满 足二阶充分条件，即dTHd 0, Vd e R

6、n, d。0, Ad = 0,则线性方程组(1.4)的系数矩阵非奇异，即方程组(1.4 )有唯一解。其中，方程 组(1.4)为(1.1)对应的齐次方程组：H-At3-a0V=0 (1.4).故可设其逆为下面，我们来推导方程（1.3）的求解公式。根据定理1，拉格朗日矩阵必然 是非奇异的一 H-At=一 G-Bt -A0-Bc由恒等式H-At G-Bt -=_ In0 一nxm-a0 JL- BC _0mxnIm可得HG + At B = I-HBt - AtC = 0nxm-AG = 0mxnABt = Im于是由上述四个等式得到矩阵G,B,C的表达式G = H-1 - H-iAt (AH-i

7、At )-i AH-1,(1.5)B = (AH -i At ) -i AH -i,(1.6)(1.7)C = -( AH -i At ) -i.因此，由（1.3）可得解得表达式X-Bt 一r- c - Gc + BTb=-Bc _-b=Bc - Cb(1.8)其中，G,B,C分别由（1.5）,（1.6）,（1.7）给出。下面给出X和厂的另一种等价表达式。设x是问题（1.1）的任一可行点，即 kXk满足Axk = n 而在此点处目标函数的梯度为gk=W（七）=Hx +c，利用Xk(1.9)和gk，可将（1.8）改写为厂1.2.2拉格朗日方法的应用（1）拉格朗日方法的Matlab程序见附录。（2

8、）利用拉格朗日方法求解下列问题：min X2 + 2X2 + 尤2 2x x + x , s.t. x + x + x = 4, 2x - x + x = 2.解容易写出一 2-20O114H =-240,c =0,A =,b =2-112002111*利用Matlab程序求解该问题可以结果如下：K 二1.9090909090909091.9545454545454550. 136363636363637Lam =2.636363636363636-1.363636363036363val 二3.9772727272727282 一般凸二次规划问题的解法2.1问题描述考虑一般二次规划I 1 ，

9、min xtHx + ctx,(2.1)s.t. aTx-b = 0,i e E = 1,l,aTx-b 0,i e I = l +1,mii其中H是n阶对称阵。记I(x*) = ilaTx*-bi = 0,i e I，下面的定理给出了问题 (2.1)的一个最优性充要条件。定理2 *是二次规划问题(2.1)的局部极小点当且仅当(1)存在X* e Rm，使得Hx+c&a=0,ieEieIaTx* - b = 0, i e E,iiaTx* - b 0,i e I,X* 0, i e I; X* = 0, i e I I (x *) ii记S = d e Rn 0ldTa. = 0,i e E;d

10、Ta. 0,i e I(x*);dTa. = 0,i e I(x*)且X* 0.则对于任意的d e S，均有dTHd 0.容易发现，问题(2.1)是凸二次规划的充要条件是H半正定。此时，定理2 的第二部分自然满足。注意到凸优化问题的局部极小点也是全局极小点的性质， 我们有下面的定理：定理3 x*是凸二次规划的全局极小点的充要条件是x*满足KT条件，即存在X* e Rm，使得Hx* + c-ZX*ai -ZX*ai = 0,ieEieIaTx* - b = 0,i e E, iiaTx* - b 0,i e I,iiX* 0,i e I;X* = 0,i e I I(x*).ii2.2有效集法求

11、解一般凸二次规划问题2.2.1有效集方法的理论推导首先引入下面的定理，它是有效集方法理论基础。定理4设x*是一般凸二次规划问题的全局极小点，且在x*处的有效集为S(x*)= E I(x*)，则x*也是下列等式约束凸二次规划min xtHx + ctx,c、 0, i e I.则令a = 1, x = x + d .(2)若xk + dk不是问题(2.1)的可行点，则通过线性搜索求出下降最好的可行 点。注意到目标函数是凸二次函数，那么这一点应该在可行域的边界上达到。因 此只要求出满足可行条件的最大步长a即可。k当i e S时，对于任意的a 0，都有aTd = 0和aT (x +a d ) = a

12、Tx = b， kki ki k k k i k i此时，ak 0不受限制。当i冬S/寸，即第i个约束是严格的不等式约束，此时要 求a 满足aT (x +a d ) b，艮口a aTd b 一 aTx ,i e S .k i k i i kk注意到上式右端非正，故当aTdk 0时，上式恒成立。而当aTdk 0时，由上式-7 -可解得a b ”.kaTd故有=a = min 一气 X | aTd .k aTd l k J、 l k/合并第(1)(2)可得第三步，修正S .当a k故 aT 3 +a d ) = blklkaTdj k=0, Vj e E; aTd jk 0, Vj e I(xk)

13、，为简便计算，按下述方式选取dk :a = min1,a k(2.5).=1时，有效集不变，即七：=S而当a k 1时，b - aTxak ak ，kaTdk k， l k k因此在xk+(处增加了一个有效约束，即 第四步，考虑dk = 0的情形。此时x是问题(2.3)的全局极小点。若这是对应的不等式约束的拉格朗日乘子均为非负，则七也是问题(2.1)的全局极小点，迭代 终止。否则，如果对应的不等式约束的拉格朗日乘子有负的分量，那么需要重新 寻找一个下降可行方向。kk设七广0, jk e I (x )，现在要求一个下降可行方向 d，满足gTd b ,jk k kjkaT (x + d ) = b

14、 , Vj e S , j。j ,j k k jkk|aTdk 0,ak = 0：Vj e Sk, j 牛 j,a*)另一方面，注意到xk是子问题(2.3)的全局极小点，故有Hx + c Z 人k a = 0,leSk其中气=(气)心,广。:)心kk从而，gTd = XtAtd .由(2.6)知 k k k k kATd =Z (aTd )e = (aT d )e于是有jeSkJJJkJkgTd = Xt (qt d )e, =Xk (aT d ) 0，则x是全局极小点，停算。否则，若(X ) 0，则令S := S t， ktkk tk k转步骤(2)。确定步长a .令a = min1,ak，

15、其中=min心k否则，若a V1，k则令 Sk+1 = Sk/J，其b 一件 k | aTd v 0.aTd， k J中匕满足 b - aT xk aT djk k（6）令k := k +1，转步骤（1）。2.2.3有效集方法的应用有效集法的Matlab程序见附录。用有效集方法求解下列二次规划问题:min f (x) = x 2 xx + 2x 2 x 一 10 x , 11 2212 0, x2 0.解首先确定有关数据：- 3-2-62-1-1H =,c =,Ae = , be = , Ai =10,bi =0-14-1011 1010利用Matlab计算可得结果如下:X =0. 50002

16、. 250Cesitflag =0lambda =output -0.750Cfva.1: -13.7500iter: 83总结与体会通过本次实验，笔者对求解等式约束凸二次规划问题的拉格朗日方法及一般 约束条件下凸二次规划问题的有效集方法有了较深的认识和了解。感谢阮老师的悉心教诲和指导，使得笔者对最优化课程中的理论推导、算法 步骤及编程都比较熟悉，对以后的科研工作有很好的指导和借鉴意义。4附录4.1拉格朗日方法的matlab程序拉格朗日算法函数%本程序用拉格朗日方法求解灯饰约束条件的二次规划问题。function x,lam,fval=qlag(H,A,b,c)%功能：用拉格朗日方法求解等式约

17、束二次规划：% min f(x)=0.5*xHx+cx，s.t. Ax=b%输入：H,c分别是目标函数的矩阵和向量，A,b分别是约束条件中的矩阵和向量%输出：(x,lam)是KT点，fval是最优值IH=inv(H);AHA=A*IH*A;IAHA=inv(AHA);AIH=A*IH;G=IH-AIH*IAHA*AIH;B=IAHA*AIH;C=-IAHA;x=B*b-G*c;lam=B*c-C*b;fval=0.5*x*H*x+c*x;拉格朗日算法求解等式约束凸二次规划问题主程序：H=2 -2 0;-2 4 0;0 0 2;c=0 0 1;A=1 1 1;2 -1 1;b=4 2;x,lam

18、,fval=qlag(H,A,b,c)4.2有效集方法的Matlab程序(1)有效集方法函数%本程序主要适用于求解一般约束条件下的凸二次规划问题function x,lamk,exitflag,output=qpact(H,c,Ae,be,Ai,bi,x0)%功能：用有效集方法解一般约束二次规划问题%min f(x)=0.5*x*H*x+c*x,% s.t. a_i*x-b_i=0,(i=1,.,l),%a_i*x-b_i=0,(i=l+1,.,m)%输入：x0是初始点，H,c分别是目标函数二次矩阵和向量；%Ae=(a_1,.,a_l),be=(b_1,.,b_l);%Ai=(a_l+1,.,

19、a_m),bi=(b_l+1,.,b_m).%输出：x是最优解，lambda是对应的乘子向量；output是结构变量%输出极小值f(x)，迭代次数k等信息，exitflag是算法终止类型%初始化epsilon=1.0e-9;err=1.0e-6;k=0;x=x0;n=length(x);kmax=1.0e3;ne=length(be);ni=length(bi);lamk=zeros(ne+ni,1);index=ones(ni,1);for i=1:niif Ai(i,:)*xbi(i)+epsilonindex(i)=0;endend%算法主程序while k0Aee=Ae;endfor j=1:niif index(j)0Aee=Aee;Ai(j,:);endendg