更新时间：2023-12-12 19:57
二次规划是非线性规划中的一类特殊数学规划问题，在很多方面都有应用，如投资组合、约束最小二乘问题的求解、序列二次规划在非线性优化问题中应用等。在过去的几十年里，二次规划已经成为运筹学、经济数学、管理科学、系统分析和组合优化科学的基本方法。
二次规划的一般形式可以表示为：
其中G是Hessian矩阵，τ是有限指标集，c，x和 ，都是R中的向量。如果Hessian矩阵是半正定的，则我们说该式是一个凸二次规划，在这种情况下该问题的困难程度类似于线性规划。如果有至少一个向量满足约束并且在可行域有下界，则凸二次规划问题就有一个全局最小值。如果是正定的，则这类二次规划为严格的凸二次规划，那么全局最小值就是唯一的。如果是一个不定矩阵，则为非凸二次规划，这类二次规划更有挑战性，因为它们有多个平稳点和局部极小值点。
已经出现了很多求解二次规划问题的算法，如拉格朗日方法、Lemke方法、内点法、有效集法、椭球算法等等，并且仍有很多学者在从事这方面的研究工作。
在数学规划中，由于凸二次规划有着特殊作用，人们一直把它作为一个重要课题加以研究。等式约束二次规划问题的一个求解方法是拉格朗日算法。首先定义拉格朗日函数，对此函数求导，再令导数为零，这样便得到一个线性方程组。拉格朗日算法有两个不足之处：
（1）构造的线性方程组的方程个数与m有关(n+m个方程)，当n与m都很大时，将占用计算机很大的存储空间，并且使计算量增加；
（2）必须计算矩阵的逆。
首先引入下面的定理，它是有效集方法理论基础。
设x*是一般凸二次规划问题的全局极小点，且在x*处的有效集为
则x*也是下列等式约束凸二次规划：
的全局最小点。
从上述定理可以发现，有效集方法的最大难点是事先一般不知道有效集S(x*)，因此只有想办法构造一个集合序列去逼近它，即从初始点 出发，计算有效集 ，解对应的等式约束子问题。
修正后的子问题如下：
由此可知，修正后的子问题的全局极小点必然是原问题的一个下降可行方向。
有效集方法的算法步骤如下：
（1）选取初值。给定初始可行点 ，令k:=0。
（2）解子问题。确定相应的有效集
求解子问题
得极小点 和拉格朗日乘子向量 。若 转步骤（4）；否则，转步骤（3）。
（3）检验终止准则。计算拉格朗日乘子：
其中
令
若 ，则 是全局极小点，停算；否则，转步骤（2）。
（4）确定步长 。令 ，其中
令 。
（5）若 =1，则令 ；否则，若 <1，则令 ，其中
（6）令k:=k+1，转步骤（1）。
我们考虑如下的二次规划问题：
其中矩阵H对称正定，A行满秩。
首先写出拉格朗日函数：
令
将上述方程组写成分块矩阵形式：
我们称此方程组的系数矩阵：
为拉格朗日矩阵。
解的表达式为：