《求解二次规划问题的拉格朗日及有效集方法》由会员分享，可在线阅读，更多相关《求解二次规划问题的拉格朗日及有效集方法（17页珍藏版）》请在金锄头文库上搜索。
1、求解二次规划问题的拉格朗日及有效集方法最优化方法课程实验报告学班院：数学与统计学院级：硕2041班学号：指导教师：同组人：钱东东求解二次规划问题的拉格朗日 及有效集方法 摘要二次规划师非线性优化中的一种特殊情形，它的目标函数是二次实函数，约 束函数都是线性函数。由于二次规划比较简单，便于求解（仅次于线性规划）， 并且一些非线性优化问题可以转化为求解一些列的二次规划问题，因此二次规划 的求解方法较早引起人们的重视，称为求解非线性优化的一个重要途径。二次规 划的算法较多，本文仅介绍求解等式约束凸二尺规划的拉格朗日方法以及求解一 般约束凸二次规划的有效集方法。关键字：二次规划，拉格朗日方法，有效集方
2、法。【目录】摘要 - 1 -1 等式约束凸二次规划的解法 - 3 -1.1 问题描述 - 3 -1.2 拉格朗日方法求解等式约束二次规划问题 - 3 -1.2.1 拉格朗日方法的推导 - 3 -1.2.2 拉格朗日方法的应用 - 4 -2 一般凸二次规划问题的解法 - 5 -2.1 问题描述 - 5 -2.2 有效集法求解一般凸二次规划问题 - 6 -2.2.1 有效集方法的理论推导 - 6 -2.2.2 有效集方法的算法步骤 - 9 -2.2.3 有效集方法的应用 - 10 -3 总结与体会 - 11 -4 附录 - 11 -4.1 拉格朗日方法的 matlab 程序 - 11 -4.2 有
3、效集方法的 Matlab 程序 - 11 -1 等式约束凸二次规划的解法1.1 问题描述我们考虑如下的二次规划问题 0, Vd e Rn, d 丰 0, Ad = 0,则线性方程组(1.4)的系数矩阵非奇异，即方程组(1.4)有唯一解。其中，方程组(1.4)为(1.1)对应的齐次方程组：_ H-Atd -A0v=0 (1.4).故可设其逆为下面，我们来推导方程(1.3)的求解公式。根据定理 1，拉格朗日矩阵必然 是非奇异的，_ H-At-G一 Bt-A0-BC由恒等式H-At 1 G一 Bt-I0_nnxm-A0 IL- BC0Imx nm可得HG + At B = I-HBt - AtC =
4、 0nxm-AG = 0mxnABt = Im于是由上述四个等式得到矩阵G,B,C的表达式G 二 H-1 - H-1 At (AH-1 At )-1 AH-1,(1.5)B = (AH -1 At ) -1 AH -1,(1.6)(1.7)(1.8)C = -( AH -1 At ) -1.X1G一 Bt-c一 Gc + BTbX-BC-bBc - Cb因此，由(1.3)可得解得表达式其中，G,B,C分别由(1.5),(1.6),(1.7)给出。F面给出X和X的另一种等价表达式。设x是问题(1.1)的任一可行点，即kx满足Ax = b。而在此点处目标函数的梯度为g = Vf(x ) = Hx
5、+ c，利用xk k k k k k和g，可将(1.8)改写为kXx - Gg=kkL Bgk(1.9)1.2.2 拉格朗日方法的应用1) 拉格朗日方法的 Matlab 程序见附录。2) 利用拉格朗日方法求解下列问题：min x 2 + 2 x 2 + x 2 - 2 x x + x ,1231 23s.t. x + x + x = 4,1232x - x + x = 2.123解容易写出-2-20111H =-240,c =0,A =,b =2-1120021_1 利用Matlab程序求解该问题可以结果如下：K =1.9090909090909091.9545454545454550. 13
6、6363636363637Lam =2.636363636363636-1.363636363036363val =3.9772727272727282 一般凸二次规划问题的解法21问题描述考虑一般二次规划min xtHx + ctx,2(2.1) 0,i e I = l +1,，mii其中H是n阶对称阵。记I(x*) = ilaTx*-b = 0,i e I，下面的定理给出了问题ii(2. 1)的一个最优性充要条件。定理2 x*是二次规划问题(2. 1)的局部极小点当且仅当(1)存在九* e Rm，使得Hx* + c 一工九* a - 工九* a = 0,i ii iieEieIaTx* 一
7、 b = 0, i e E,1ii-aTx* 一 b 0,i e I, ii九* 0, i e I;九* = 0, i e I I (x *)ii(2)记S = d e RnOldTa = 0,i e E;dTa 0,i e I(x*);dTa = 0,i e I(x*)且九* 0.iiii则对于任意的d e S，均有dTHd 0.容易发现，问题(2. 1)是凸二次规划的充要条件是H半正定。此时，定理2 的第二部分自然满足。注意到凸优化问题的局部极小点也是全局极小点的性质， 我们有下面的定理：定理3 x*是凸二次规划的全局极小点的充要条件是x*满足KT条件，即存在九* e Rm，使得Hx* +
8、 c 一工九*a 一工九*a = 0,i ii iieEieIaTx* 一 b = 0, i e E,1iiaTx* 一 b 0,i e I, iiX* 0,i e I;X* = 0,i e I I(x*). ii2.2 有效集法求解一般凸二次规划问题2.2.1 有效集方法的理论推导首先引入下面的定理，它是有效集方法理论基础。定理4设x*是一般凸二次规划问题的全局极小点，且在x*处的有效集为S(x*) = E I(x*)，则x*也是下列等式约束凸二次规划min 1 xtHx + ctx,2(2.2)s.t. aTx一b = 0,i e S(x*).ii的全局极小点。从上述定理可以发现，有效集方
9、法的最大难点是事先一般不知道有效集S(x*) ，因此只有想办法构造个集合序列去逼近它，即从初始点x 0出发，计算有效集 S(x ) ，解对应的等式约束子问题。重复这一做法，得到有效集序列0S (Xk)h k二丄使之S(X? T S (X *)，以获得原问题的最优解。基于上述定理，我们分 4 步来介绍有效集方法的算法原理和实施步骤。a T xik第一步，形成子问题并求出搜索方向d 设x是问题(2.1)的一个可行点，据 kk此确定相应的有效集S二E u I(X )，其中I(x )二i I aTx - b二0,i e I.求解相 i应的子问题(2.3)(2.4)min xtHx + ctx, 0,
10、i e I.i k k ii k k i则令a = 1, x = x + d .kk +1k k(2)若x + d不是问题(2.1)的可行点，则通过线性搜索求出下降最好的可行 kk点。注意到目标函数是凸二次函数，那么这一点应该在可行域的边界上达到。因此只要求出满足可行条件的最大步长a即可。k当i e S时，对于任意的a 0，都有aTd = 0和aT(x +a d ) = aTx = b， kki ki k k ki k i此时，a 0不受限制。当i纟S时，即第i个约束是严格的不等式约束，此时要 kk求a满足aT(x +a d ) b，即ki k k kia aTd b 一 aTx ,ie S
11、.k i k i i kk注意到上式右端非正，故当aTd 0时，上式恒成立。而当aTd 0时，由上式i ki k可解得b aT x aW iik .kaT dik故有a =ak=min i_a x | aTd . k aTdi k Jik合并第(1)(2)可得a = min1, a (2.5) .kk第三步，修正S .当akk=1时，有效集不变，即S ：= S .而当a 1时, k +1kk故 aT(x +a d ) =bi k k kikkb 一aTxa = a，kk aTdikk， 因此在 x 处增加了一个有效约束， 即 k+!S:= Si .k +1k k第四步，考虑d = 0的情形。此时x是问题(2.3)的全局极小点。若这是对应kk的不等式约束的拉格朗日乘子均为非负，则 x 也是问题(2.1)的全局极小点，迭代 k终止。否则，如果对应的不
