《求解二次规划问题的拉格朗日及有效集方法》由会员分享，可在线阅读，更多相关《求解二次规划问题的拉格朗日及有效集方法（21页珍藏版）》请在金锄头文库上搜索。
1、求解二次规划问题的拉格朗日及有效集方法最优化方法课程实验报告学 院:数学与统计学院班 级:硕2041班姓 名：王彭学 号：28指导教师：阮小娥同组人：钱东东求解二次规划问题的拉格朗日及有效集方法摘要二次规划师非线性优化中的一种特殊情形，它的目标函数是二次实函数，约 束函数都是线性函数。由于二次规划比较简单，便于求解（仅次于线性规划）， 并且一些非线性优化问题可以转化为求解一些列的二次规划问题，因此二次规划 的求解方法较早引起人们的重视，称为求解非线性优化的一个重要途径。二次规 划的算法较多，本文仅介绍求解等式约束凸二尺规划的拉格朗日方法以及求解一 般约束凸二次规划的有效集方法。关键字：二次规划
2、，拉格朗日方法，有效集方法。【目录】摘要错误!未定义书签。1等式约束凸二次规划的解法错误!未定义书签。问题描述错误!未定义书签。拉格朗日方法求解等式约束二次规划问题错误!未定义书签。拉格朗日方法的推导错误!未定义书签。拉格朗日方法的应用错误!未定义书签。2 一般凸二次规划问题的解法错误!未定义书签。问题描述错误!未定义书签。有效集法求解一般凸二次规划问题错误!未定义书签。有效集方法的理论推导错误!未定义书签。有效集方法的算法步骤错误!未定义书签。有效集方法的应用错误!未定义书签。3总结与体会错误!未定义书签。4附录错误!未定义书签。拉格朗日方法的matlab程序错误!未定义书签。有效集方法的M
3、atlab程序错误!未定义书签。1等式约束凸二次规划的解法问题描述min xtHx + ctx,我们考虑如下的二次规划问题12s.t. Ax = b其中H e Rnxn对称正定，A e Rmxn行满秩，c, X G Rn，b e Rm。拉格朗日方法求解等式约束二次规划问题拉格朗日方法的推导首先写出拉格朗日函数：L(x,人)=xtHx + ctx - Xt (Ax - b)V L(x, X) = 0,V/(x, X) = 0得到方程组Hx - ATX = -c 一 Ax = -b.将上述方程组写成分块矩阵形式:-At-a 0_|_X|_- b我们称伤处方程组的系数矩阵H-A-At0为拉格朗日矩阵
4、。卜面的定理给出了线性方程组有唯一解的充分条件。定理1设H e Rmxn对称正定，A e Rmxn行满秩。若在问题的解X*处满足二 阶充分条件，即dTHd 0, Vd e Rn,d。0, Ad = 0,则线性方程组的系数矩阵非奇异，即方程组（）有唯一解。其中，方程组为（） 对应的齐次方程组：H-Atd-A0 _Lv J=0（）.&下面，我们来推导方程的求解公式。根据定理1，拉格朗日矩阵必然是非奇 异的，故可设其逆为一 H-At=一 G-Bt -A0JL- Bc由恒等式H-At G-Bt -=-1n0 一nxm-A0 JL- bC JL0mxnIm可得HG + At B = I-HBt - At
5、C = 0nxm-AG = 0mxnABt = Im于是由上述四个等式得到矩阵G,B,C的表达式G = H-1 - H-1 At (AH-1 At )-i AH-1,(1.5)B = (AH -1 At ) -1 AH -1,(1.6)(1.7)C = -( AH -1 At ) -1.因此，由可得解得表达式X=一 Bt-c=-Gc + BTb力-Bc_- b jBc - Cb(1.8)其中，G,B,C分别由,给出。下面给出X和厂的另一种等价表达式。设xk是问题的任一可行点，即xk满 足Axk = b。而在此点处目标函数的梯度为gk = W （七）=叫+c，利用xk和gk，气一 Gg(1.9)
6、可将改写为Bg拉格朗日方法的应用（1）拉格朗日方法的Matlab程序见附录。（2）利用拉格朗日方法求解下列问题：min x2 + 2x2 + x2 2x x + x , st. x + x + x = 4, 2x - x + x = 2.解容易写出一 2-20114H =-240,c =0,A =,b =2-112_ 0021_11 ,利用Matlab程序求解该问题可以结果如下:1.9000909090909091.9545454545454550. 136363636363637Lam =2.636363636363636-1.363636363036363val =3.9772727272
7、727282一般凸二次规划问题的解法问题描述考虑一般二次规划I 1 Tmin xtHx + ctx,2s.t. aTx一b = 0,i e E = 1,/,(2.1)i iaTx-b 0,i e I = l +1,mii其中H是n阶对称阵。记I(x*) = i I aTx* -b = 0,i e I，下面的定理给出了问题的一个最优性充要条件。定理2 x*是二次规划问题的局部极小点当且仅当(1)存在人* e Rm，使得Hx+ c-& a-& a = 0,ieEielaTx* - b = 0, i e E,aTx* - b 0, i e I,X* 0, i e I; X* = 0, i e I I
8、 ( x *)ii记S = d e Rn 0ldTa. = 0,ie E;dTa. 0,i e I(x*);dTa. = 0,i e I(x*)且人* 0.则对于任意的d e S，均有dTHd 0.容易发现，问题是凸二次规划的充要条件是H半正定。此时，定理2的第二 部分自然满足。注意到凸优化问题的局部极小点也是全局极小点的性质，我们有卜面的定理:定理3 x*是凸二次规划的全局极小点的充要条件是x*满足KT条件，即存在人* e Rm，使得+ c-&a =0,ieEieIaTx* - b = 0, i e E,iiaTx* - b 0,i e I,iiX* 0,i e I;X* = 0,i e I
9、 I(x*).ii有效集法求解一般凸二次规划问题有效集方法的理论推导首先引入下面的定理，它是有效集方法理论基础。定理4设x*是一般凸二次规划问题的全局极小点，且在x*处的有效集为S(x*)= E I(x*)，则x*也是下列等式约束凸二次规划(2.2)I 1 丁口 , T min xt Hx + ctx, 2st. aTx-b = 0,i e S(x*).i的全局极小点。从上述定理可以发现，有效集方法的最大难点是事先一般不知道有效集S(x*)，因此只有想办法构造一个集合序列去逼近它，即从初始点x0出发，计算 有效集S(x0)，解对应的等式约束子问题。重复这一做法，得到有效集序列S(七),k =
10、0,1,，使之S(七)T s3*)，以获得原问题的最优解。基于上述定理，我们分4步来介绍有效集方法的算法原理和实施步骤。第一步，形成子问题并求出搜索方向dk.设七是问题的一个可行点，据此确定相应的有效集sk其中 I(x ) = i I aTXk - b = 0, i e I.求解相应的aT x子问题2 xtHx + ctx, st. aTx - b = 0, i e S .min(2.3)上述问题等价于min q (d) = -2drHd + grd,s.t. aTd = 0, i e S .(2.4)其中 k=Gxk + C-设求出问题的全局极小点为dk,人k是对应的拉格朗日乘子。第二步，进
11、行线性搜索确定步长因子ak .假设dk丰0分两种情形讨论。k + dk是问题的可行点，即aT (x + d ) - b = 0, i e E 及 aT (x + d ) - b 0, i e I.i k k ii k k i则令a = 1, x = x + d .(2) 若xk + dk不是问题的可行点，则通过线性搜索求出下降最好的可行点。 注意到目标函数是凸二次函数，那么这一点应该在可行域的边界上达到。因此只 要求出满足可行条件的最大步长a即可。k当i e S时，对于任意的a 0，都有aTd = 0和aT (x +a d ) = aTx = b， kki ki k k k i k i此时，a
12、k 0不受限制。当i冬S/寸，即第i个约束是严格的不等式约束，此时要 求a满足aT闵+a kdk) b ,艮口a ad b - aTx , i e S .k i k i i kk注意到上式右端非正，故当aTd k 0时，上式恒成立。而当aTd k 0时，由上式可解得a b 一件.kaTd故有a =a=min 一ai Xk | ad . k E ，k 合并第(1)(2)可得a = min1,a k(2.5).第三步，修正S. .当a k=1时，有效集不变，即SkH：= Sk .而当a k 1时，故 a (x +a d ) = bikk k kikb - axak 以k kaTdk k， i k
13、k因此在xk+(处增加了一个有效约束，即Sk+i := Skik.第四步，考虑dk = 0的情形。此时xk是问题的全局极小点。若这是对应的不 等式约束的拉格朗日乘子均为非负，则xk也是问题的全局极小点，迭代终止。 否则，如果对应的不等式约束的拉格朗日乘子有负的分量，那么需要重新寻找一个下降可行方向。设七广0, e I亳)，现在要求一个下降可行方向dk，满足grdk 0, Vj e I(x)，为简便计算，按下述方式选取d :a (x + d ) b ,a (x + d ) = b , Vj e S , j。j ,j k k jkk|ardk 0,。队=0：月j e Sk, j 壬 j,a*)另一方面，注意到七是子问题的全局极小点，故有A?人:其中A广(les :广。:Les -kk从而，gTd = XtAtd .由知k k k k kATd = Z (aTd )e = (aT
