参考资料

• 二次规划的若干算法研究
• 关于凸二次规划若干算法的研究
• 二次规划
• 不等式约束的优化问题

由于在面试中有被问及QP的原理，所以重点来总结一波QP的原理。

1. 二次规划形式

二次规划问题（Quadratic Programming，QP）是一种非线性规划问题，它的目标函数为二次函数，约束条件和线性规划问题的约束条件一样，都是线性等式或线性不等式，即

一般二次规划问题可以分成以下几类：

• 凸二次规划问题：G半正定，问题有全局解
• 严格凸二次规划问题：G正定，问题有唯一全局解
• 一般二次规划问题：G不定，问题有稳定点或局部解

二次规划应用广泛，常见的例如有：求最小二乘法，点到多面体的距离，模型预测控制的求解等。

下面我们分别介绍等式约束和不等式约束下的二次规划的求解。

2. 等式约束二次规划问题

等式约束的二次规划问题一般形式如下：

其中

2.1 变量消去法

1. 示例

变量消去法思路很简单，就是初中时候学过的消元法（当然，抽象之后还是挺高级的）。例如举个小栗子，假设要求解下面这个二次规划问题：

消除一个变量，这样就可以很简单的求解出来:

当然我们还可以用拉格朗日法，推导出KKT条件（后面会讲）:

2. 具体过程

应用变量消去法求解包括以下3个步骤：

1. 将分成基本变量 与非基本变量 两部分，利用等式约束将基本变量用非基本变量表示出来；
2. 再将基本变量带入目标函数，从而消去基本变量，把问题化为一个关于非基本变量的无约束最优化问题；
3. 最后求解无约束最优化问题的方法解之

具体来说：

将 分块，使其包含一个 非奇异矩阵 做对应的分块

所以等式约束就转化为：

将等式(4)写开得

将基本变量用非基本变量表示出来

这样原变量就可以写成:

即写成了一个类似于 的形式，这样我们将其代入目标函数，消去基本变量，把问题化为一个关于非基本变量的无约束最优化问题，最后求解无约束最优化问题的方法就能解出答案。

我们将 带入到目标函数中得：

除了，其他都是已知的常数项 ，由于常数项不影响优化结果，所以优化过程中省略常数项，得如下形式:

对其求导等于零:

如果想要其有唯一最优解，也就必须要满足 为正定。

2.2 Lagrange法

等式约束二次规划的Lagrange函数为

其中称为Lagrange乘数，正负皆有可能。Lagrange乘数法将原本的约束优化问题转换成等价的无约束优化问题

计算 对 与 的偏导数并设为零，可得最优解的必要条件:

表示为方程组:

这样将这个方程组求解之后就可以求得最优解。

2.3 变量消去 vs Lagrange法

根据等式(10)和(14)的维度关系，变量消去法其实是转化成了一个 维的问题，也就是说求解个方程组就能解决这个问题。而 Lagrange法是将其转化成一个 维的问题，即 个变量， 个乘子。

如果建模建出来的问题就只需要求解一次等式二次规划问题，那么哪一个其实都可以求解，如果维数太大，建议用变量消去法。

变量消去法很直观，使用非基变量表示基变量，但是由于需要计算的逆，当接近奇异时会导致误差很大.

3. 不等式约束二次规划问题

本节主要来自参考资料4.

3.1 Lagrange乘数法与KKT条件

1. 只有不等式约束的一般形式

先考虑只有不等式约束的一般形式：

约束不等式 称为原始可行性(primal feasibility)，据此我们定义可行域(feasible region)

假设 为满足约束条件的最佳解，分开两种情况讨论：

• ，最佳解位于 的内部，称为内部解(interior solution)，这时约束条件是无效的 (inactive);
• ，最佳解落在 的边界，称为边界解(boundary solution)，此时约束条件是有 效的(active)。

这两种情况的最佳解具有不同的必要条件。

• 内部解: 在约束条件无效的情形下， 不起作用，约束优化问题退化为无约束优化问题， 因此驻点 满足 且 。
• 边界解：在约束条件有效的情形下，约束不等式变成等式 ，这与前述Lagrange乘数法的情况相同。 我们可以证明驻点 发生于 （span是生成子空间），换句话说，存在 使得 ，但这里 的正负号是有其意义的。因为我们希望最小化 ，梯度 (函数 在点 的最陡上升方向)应该指向可行域 的内部(因为你的最优解最小值是在边界取得的)，但 指向 的外部(即 的区域，因为你的约束是小于等于 0 ），因此 ，称为对偶可行性(dual feasibility)。

因此，不论是内部解或边界解， 恒成立，称为互补松弛性(complementary slackness)。整合上述两种情况，最佳解的必要条件包括Lagrangian函数 的定常方程式、原始可行性、对偶可行性，以及互补松弛性：

这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化 且受限于 ，那么对偶可行性要改成 。

2. 标准约束优化

考虑标准约束优化问题(或称非线性规划)：

定义Lagrangian 函数

其中 是对应 的Lagrange乘数， 是对应 的Lagrange乘数(或称 KKT乘数)。KKT条件包括定常方程式、原始可行性、对偶可行性，以及互补松弛性，如下所示：

3. 示例

1. 考虑这个问题
   
   其中 为实数。写出Lagrangigan函数
   
   KKT 方程组如下:
   
   求偏导可得
   

   分别解出
   
   代入约束等式
   

   合并上面结果，
   

   最后再加入约束不等式

   
   即

   底下分开三种情况讨论。

   1. : 不难验证 满足所有的KKT条件，约束不等式是无效的， 是内部解，目标函数的极小值是 。
   2. : 如同 1 ， 满足所有的KKT条件， 是边界解，因为 。
   3. : 这时约束不等式是有效的， ，则 且 ，目 标函数的极小值是 。

2. 考虑优化问题
   
   试验证 为 点，并求出问题的 对。
   【解】记
   

   求梯度（都使用向量的形式写法，更紧凑），得到
   
   把 代入上面5个式子，由 条件有，

   
   因为
   
   所以(4)变为
   
   求解 式，得到
   
   这表明 是 点， 是 对，其中， 。

分割线，下面待更新

3.2 内点法

内点法引入障碍函数将约束条件转化为目标函数，生成等价于原模型的优化问题。

3.3 积极集法