题目:二次规划问题和MATLAB函数quadprog的使用
其中,为纯量,为阶对称矩阵。易知二次规划的Hesse矩阵等于。如果为半正定矩阵,则称此规划为凸二次规划,否则为非凸规划。对于凸二次规划,目标函数q(x)是一个凸函数。如果有至少一个向量x满足约束而且q(x)在可行域有下界,二次规划问题就有一个全局最小值x。 如果G是正定矩阵,则称此规划为严格凸二次规划,此时全局最小值就是唯一的。如果G=0,二次规划问题就变成线性规划问题。根据优化理论,一个点x 成为全局最小值的必要条件是满足Karush-Kuhn-Tucker(KKT)条件。当q(x)是凸函数时,KKT条件也是充分条件。
根据约束条件的不同,二次规划可分为等式约束二次规划问题和不等式约束二次规划问题。等式约束二次规划问题即只含有等式约束,常见的解法有直接消去法、广义消去法、拉格朗日(Lagrange)法;对于不等式约束二次规划问题,其基本思想是把不等式约束转化为等式约束再求解,常见解法有有效集(active set)方法,有效集方法在每步迭代中把有效约束作为等式约束,然后可以用拉格朗日法求解,重复直到求得最优解。
很多学者专门研究各类二次规划的求解方法,如文献[4][5],对于非数学专业的的人来讲更重要的是怎么把二次规划当作一个工具去使用它。
最后,矩阵H只与两个变量x1和x2的二次项有关,所以,这里要注意的是不同于二次型,这里有个系数1/2,所以矩阵H的元素是二次型中的矩阵元素大小的两倍。给出一个规律:设矩阵H第i行第j列的元素大小为H(i,j),二次项xixj的系数为a(i,j),则
【1】孙文瑜, 徐成贤,朱德通.最优化方法(第二版)[M]. 北京:高等教育出版社, 2010.
【2】龚纯,王正林. 精通MATLAB最优化计算[M].北京: 电子工业出版社,2009.
【4】李明强.几类特殊凸二次规划问题的求解算法研究[D].山东科技大学,2013 .
【5】于绍慧.边界约束凸二次规划的求解[D].南京航空航天大学,2005.