求解二次规划问题的拉格朗
日及有效集方法
——最优化方法课程实验报告
学 院：数学与统计学院
班 级：硕
2041
班
姓 名：王彭
学 号：3112054028
指导教师：阮小娥
同 组 人：钱东东
《最优化方法》课程实验报告
求解二次规划问题的拉格朗日
及有效集方法
摘要
二次规划师非线性优化中的一种特殊情形，它的目标函数是二次实函数，
约束函数都是线性函数。由于二次规划比较简单，便于求解（仅次于线性规
划），并且一些非线性优化问题可以转化为求解一些列的二次规划问题，因此
二次规划的求解方法较早引起人们的重视，称为求解非线性优化的一个重要途
径。二次规划的算法较多，本文仅介绍求解等式约束凸二尺规划的拉格朗日方
法以及求解一般约束凸二次规划的有效集方法。
关键字：二次规划，拉格朗日方法，有效集方法。
1
求解二次规划问题的拉格朗日及有效集方法
【目录】
摘要.....................................................................................................................................................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 有效集方法的算法步骤....................................................................................................8
2.2.3 有效集方法的应用............................................................................................................9
3 总结与体会....................................................................................................................................10
4 附录................................................................................................................................................10
4.1 拉格朗日方法的 matlab 程序....................................................................................................10
4.2 有效集方法的 Matlab 程序........................................................................................................11
2
《最优化方法》课程实验报告
1 等式约束凸二次规划的解法
1.1 问题描述
我们考虑如下的二次规划问题
(1.1)
其中 对称正定， 行满秩， ， 。
1.2 拉格朗日方法求解等式约束二次规划问题
1.2.1 拉格朗日方法的推导
首先写出拉格朗日函数：
，(1.2)
令
，
得到方程组
将上述方程组写成分块矩阵形式：
(1.3)
我们称伤处方程组的系数矩阵
为拉格朗日矩阵。
下面的定理给出了线性方程组(1.1)有唯一解的充分条件。
定理 1 设 对称正定， 行满秩。若在问题(1.1)的解
处满足二阶充分条件，即
则线性方程组(1.4)的系数矩阵非奇异，即方程组（1.4）有唯一解。其中，方
程组(1.4)为（1.1）对应的齐次方程组：
（1.4）.
下面，我们来推导方程(1.3)的求解公式。根据定理 1，拉格朗日矩阵必然
3
求解二次规划问题的拉格朗日及有效集方法
是非奇异的，故可设其逆为
.
由恒等式
可得
于是由上述四个等式得到矩阵 的表达式
因此，由(1.3)可得解得表达式
其中， 分别由(1.5),(1.6),(1.7)给出。
下面给出 和 的另一种等价表达式。设 是问题(1.1)的任一可行点，
即 满足 。而在此点处目标函数的梯度为 ，利用
和 ，可将(1.8)改写为
1.2.2 拉格朗日方法的应用
（1）拉格朗日方法的 Matlab 程序见附录。
（2）利用拉格朗日方法求解下列问题：
解 容易写出
利用 Matlab 程序求解该问题可以结果如下：
4
