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

求解二次规划问题的拉格朗日及有效集方法——最优化方法课程实验报告学院：数学与统计学院班级：硕2041班姓名：王彭学号：3112054028指导教师：阮小娥同组人：钱东东求解二次规划问题的拉格朗日及有效集方法-1-求解二次规划问题的拉格朗日及有效集方法摘要二次规划师非线性优化中的一种特殊情形，它的目标函数是二次实函数，约束函数都是线性函数。由于二次规划比较简单，便于求解（仅次于线性规划），并且一些非线性优化问题可以转化为求解一些列的二次规划问题，因此二次规划的求解方法较早引起人们的重视，称为求解非线性优化的一个重要途径。二次规划的算法较多，本文仅介绍求解等式约束凸二尺规划的拉格朗日方法以及求解一般约束凸二次规划的有效集方法。关键字：二次规划，拉格朗日方法，有效集方法。《最优化方法》课程实验报告-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有效集方法的Matlab程序....................................................................-11-求解二次规划问题的拉格朗日及有效集方法-3-1等式约束凸二次规划的解法1.1问题描述我们考虑如下的二次规划问题bAxtsxcHxxTT..,21min(1.1)其中nnRH对称正定，nmRA行满秩，nRxc,，mRb。1.2拉格朗日方法求解等式约束二次规划问题1.2.1拉格朗日方法的推导首先写出拉格朗日函数：)(21)L(x,bAxxcHxxTTT，(1.2)令0),(,0),(xLxLx，得到方程组.,A-HxTbAxc将上述方程组写成分块矩阵形式：.0HbcxAAT(1.3)我们称伤处方程组的系数矩阵0A-A-HT为拉格朗日矩阵。下面的定理给出了线性方程组(1.1)有唯一解的充分条件。定理1设nmRH对称正定，nmRA行满秩。若在问题(1.1)的解*x处满足二阶充分条件，即,0,0,,0dTAddRdHdn则线性方程组(1.4)的系数矩阵非奇异，即方程组（1.4）有唯一解。其中，方程组(1.4)为（1.1）对应的齐次方程组：《最优化方法》课程实验报告-4-00A-HTvdA（1.4）.下面，我们来推导方程(1.3)的求解公式。根据定理1，拉格朗日矩阵必然是非奇异的，故可设其逆为CBBGT0A-A-HT.由恒等式mnmmnnTIICBBG000A-A-HT可得.,0,0,AHGTmTnmmnTTnIABAGCAHBIB于是由上述四个等式得到矩阵CB,G,的表达式)7.1(.)()6.1(,)()5.1(,)(HG111111111-1TTTTAAHCAHAAHBAHAAHAH因此，由(1.3)可得解得表达式)8.1(,xCbBcbBGcbcCBBGTT其中，CB,G,分别由(1.5),(1.6),(1.7)给出。下面给出x和的另一种等价表达式。设kx是问题(1.1)的任一可行点，即kx满足bkAx。而在此点处目标函数的梯度为cHxxfkk)(gk，利用kx和kg，可将(1.8)改写为)9.1(.xkkkBgGgx1.2.2拉格朗日方法的应用（1）拉格朗日方法的Matlab程序见附录。（2）利用拉格朗日方法求解下列问题：求解二次规划问题的拉格朗日及有效集方法-5-.22,4..,22min321321321232221xxxxxxtsxxxxxx解容易写出.24,112111,100,200042022HbAc利用Matlab程序求解该问题可以结果如下：2一般凸二次规划问题的解法2.1问题描述考虑一般二次规划)1.2(,},,1{,0},,,1{,0..,21minmlIibxalEibxatsxcHxxiTiiTiTT其中H是n阶对称阵。记I}i0,b-xa|{i)I(xi*Ti*，下面的定理给出了问题(2.1)的一个最优性充要条件。定理2*x是二次规划问题(2.1)的局部极小点当且仅当《最优化方法》课程实验报告-6-（1）存在mR*，使得.)(\,0;,0,,0,,0,0********xIIiIiIibxaEibxaaacHxiiiTiiTiIiiiEiii(2)记0}.)I(xi0,ad);I(xi0,adE;i0,ad|{0}\R{dS**iT*iTiTni且则对于任意的Sd，均有0dTHd.容易发现，问题(2.1)是凸二次规划的充要条件是H半正定。此时，定理2的第二部分自然满足。注意到凸优化问题的局部极小点也是全局极小点的性质，我们有下面的定理：定理3*x是凸二次规划的全局极小点的充要条件是*x满足KT条件，即存在mR*，使得).(\,0;,0,,0,,0,0Hx********xIIiIiIibxaEibxaaaciiiTiiTiEiIiiiii2.2有效集法求解一般凸二次规划问题2.2.1有效集方法的理论推导首先引入下面的定理，它是有效集方法理论基础。定理4设*x是一般凸二次规划问题的全局极小点，且在*x处的有效集为)()(**xIExS，则*x也是下列等式约束凸二次规划)2.2().(,0..,21min*xSibxatsxcHxxiTiTT的全局极小点。从上述定理可以发现，有效集方法的最大难点是事先一般不知道有效集)(*xS，因此只有想办法构造一个集合序列去逼近它，即从初始点0x出发，计算求解二次规划问题的拉格朗日及有效集方法-7-有效集)(0xS，解对应的等式约束子问题。重复这一做法，得到有效集序列,,1,0)},({kxSk使之)()(*xSxSk，以获得原问题的最优解。基于上述定理，我们分4步来介绍有效集方法的算法原理和实施步骤。第一步，形成子问题并求出搜索方向kd.设kx是问题(2.1)的一个可行点，据此确定相应的有效集)(kkxIES，其中}.,0|{)(IibxaixIikTik求解相应的子问题)3.2(.,0..,21minkiTiTTSibxatsxcHxx上述问题等价于)4.2(.,0..,21)(minkTiTkTkSidatsdgHdddq其中.,cGxgdxxkkk设求出问题(2.4)的全局极小点为kkd,是对应的拉格朗日乘子。第二步，进行线性搜索确定步长因子k.假设0kd，分两种情形讨论。(1)若kkdx是问题(2.1)的可行点，即.,0)(,0)(IibdxaEibdxaikkTiikkTi及则令.,11kkkkdxx(2)若kkdx不是问题(2.1)的可行点，则通过线性搜索求出下降最好的可行点。注意到目标函数是凸二次函数，那么这一点应该在可行域的边界上达到。因此只要求出满足可行条件的最大步长k即可。当kSi时，对于任意的0k，都有0kTida和ikTikkkTibxadxa)(，此时，0k不受限制。当kSi时，即第i个约束是严格的不等式约束，此时要求k满足ikkkTibdxa)(，即.,kkTiikTikSixabda注意到上式右端非正，故当0kTida时，上式恒成立。而当0kTida时，由上式《最优化方法》课程实验报告-8-可解得.kTikTiikdaxab故有.0|minkTikTikTiikkdadaxab合并第(1)(2)可得)5.2(},1min{kk.第三步，修正kS.当1k时，有效集不变，即kkSS:1.而当1k时，kTikTiikkdaxabkkk，故kkikkkTibdxa)(，因此在!kx处增加了一个有效约束，即}{:1kkkiSS.第四步，考虑0kd的情形。此时kx是问题(2.3)的全局极小点。若这是对应的不等式约束的拉格朗日乘