二次规划

二次规划 (Quadratic Programming)

二次规划 (Quadratic Programming, QP) 是非线性规划 (Nonlinear Programming, NLP) 的一种特殊且重要的形式。在一个二次规划问题中，其目标是找出一组变量，使得一个 二次目标函数 (quadratic objective function) 达到最小值（或最大化），同时这组变量必须满足一系列 线性约束 (linear constraints)。

由于其数学结构的特殊性，二次规划在理论和实践中都扮演着关键角色。它被广泛认为是线性规划 (Linear Programming, LP) 的自然扩展，同时也是解决更复杂的非线性问题的基础。二次规划在金融学、机器学习、运筹学、机器人学和控制理论等领域有非常重要的应用。

标准数学形式 (Standard Mathematical Form)

一个二次规划问题通常可以表示为以下标准形式：

这里，各个组成部分的定义如下：

• $\mathbf{x}$：是一个包含 $n$ 个决策变量 ($x_1, x_2, \ldots, x_n$) 的向量，是我们要寻找的最优解。
• $Q$：是一个 $n \times n$ 的对称矩阵。它定义了目标函数中的二次项。该矩阵的性质（如下文所述的正定性）直接决定了问题的求解难度。在很多问题中，$Q$ 对应于模型的Hessian矩阵。
• $\mathbf{c}$：是一个 $n$ 维向量，定义了目标函数中的线性项。
• $A$ 和 $\mathbf{b}$：分别是一个 $m \times n$ 的矩阵和一个 $m$ 维向量，共同定义了 $m$ 个等式约束 (equality constraints)。
• $G$ 和 $\mathbf{h}$：分别是一个 $p \times n$ 的矩阵和一个 $p$ 维向量，共同定义了 $p$ 个不等式约束 (inequality constraints)。

表达式 $\mathbf{x}^T Q \mathbf{x}$ 是一个二次型，它使得目标函数成为变量 $\mathbf{x}$ 的二次函数。约束条件 $A \mathbf{x} = \mathbf{b}$ 和 $G \mathbf{x} \le \mathbf{h}$ 构成的可行域是一个多面体 (polyhedron)，这是一个由线性等式和不等式界定的几何空间。

与其它优化问题的关系

• 线性规划 (Linear Programming, LP)：如果矩阵 $Q$ 是一个零矩阵 (zero matrix)，即 $Q=\mathbf{0}$，那么目标函数就只剩下线性项 $\mathbf{c}^T \mathbf{x}$。此时，二次规划问题就退化为了一个线性规划问题。因此，LP可以被看作是QP的一个特例。

• 非线性规划 (Nonlinear Programming, NLP)：二次规划是NLP的一个子类。一般的NLP问题允许目标函数和约束条件都是任意的非线性函数，而QP则要求目标函数是二次的，且所有约束必须是线性的。

• 二次约束二次规划 (Quadratically Constrained Quadratic Programming, QCQP)：如果约束条件中也包含二次项（例如 $\mathbf{x}^T R \mathbf{x} + \mathbf{d}^T\mathbf{x} \le f$），那么问题就变成了更复杂的二次约束二次规划问题。

核心概念与特性

凸性 (Convexity)

凸性是二次规划中最重要的概念，它直接关系到问题的可解性。

• 一个二次规划问题是 凸优化问题 (Convex Optimization Problem)，当且仅当其目标函数是凸函数，并且其可行域是凸集。
• 由于QP的约束总是线性的，它们所定义的可行域（一个多面体）永远是凸集。
• 因此，一个QP问题是否是凸的，完全取决于目标函数 $\frac{1}{2} \mathbf{x}^T Q \mathbf{x} + \mathbf{c}^T \mathbf{x}$ 的凸性。一个二次函数的凸性由其二次项的矩阵 $Q$ 决定。
• 关键结论：当且仅当矩阵 $Q$ 是 半正定矩阵 (Positive Semi-definite) 时，该QP问题是一个凸优化问题。
• 凸二次规划：如果 $Q$ 是半正定的，那么任何局部最优解都是全局最优解。这类问题被认为是“容易解决”的，存在能在多项式时间内找到最优解的高效算法。
• 非凸二次规划：如果 $Q$ 不是半正定的（例如，它是不定矩阵），问题就可能是非凸的。这类问题可能存在多个局部最优解，而找到全局最优解是一个 NP-hard 问题，计算上非常困难。

KKT 条件 (Karush-Kuhn-Tucker Conditions)

KKT条件 是解决带约束优化问题的理论基石，它从数学上描述了最优解需要满足的必要条件。对于二次规划问题：

• KKT条件是拉格朗日乘数法的推广，能够处理不等式约束。
• 对于任何QP问题（无论凸或非凸），一个局部最优解都必须满足KKT条件（在满足某些正则性条件的前提下）。
• 对于一个 凸二次规划 问题，KKT条件不仅是必要条件，也是 充分条件。这意味着，任何满足KKT条件的点都必定是全局最优解。因此，许多求解算法的目标就是去寻找满足KKT条件的点。

主要应用领域

二次规划的结构使其能够精确地为许多现实世界的问题建模。

1. 金融学：投资组合优化

这是QP最经典和著名的应用，源于诺贝尔奖得主哈里·马科维茨提出的现代投资组合理论 (Modern Portfolio Theory)。

• 目标：在给定预期收益水平下，最小化投资组合的风险（通常用收益的方差来度量）。
• 数学模型：
• 设 $\mathbf{w}$ 为各项资产在投资组合中的权重向量。
• 设 $\Sigma$ 为资产收益的协方差矩阵。
• 投资组合的方差为 $\mathbf{w}^T \Sigma \mathbf{w}$。
• 目标函数为：$\text{minimize} \quad \mathbf{w}^T \Sigma \mathbf{w}$。这是一个二次函数（因为协方差矩阵是半正定的，所以这是凸QP）。
• 约束条件通常包括：
• 期望收益约束：$\mathbf{r}^T \mathbf{w} \ge R_{target}$ (线性约束)。
• 预算约束：$\sum_{i=1}^n w_i = 1$ (线性约束)。
• 禁止做空约束：$w_i \ge 0$ (线性约束)。
• 因此，经典的Markowitz模型正是一个标准的二次规划问题。

2. 机器学习：支持向量机

支持向量机 (Support Vector Machine, SVM) 是一种强大的监督学习模型，广泛用于分类问题和回归问题。其训练过程可以被表述为一个二次规划问题。

• 目标：在特征空间中找到一个能够将不同類別的数据点分得最开的超平面 (hyperplane)。“分得最开”意味着最大化两类数据点到超平面之间的间隔 (margin)。
• 数学模型：
• 最大化间隔等价于最小化 $||\mathbf{w}||^2$，其中 $\mathbf{w}$ 是超平面的法向量。这是一个二次目标函数，即 $\frac{1}{2}\mathbf{w}^T\mathbf{w}$。
• 约束条件要求所有数据点都被正确分类，并且位于间隔边界之外。这些约束是关于 $\mathbf{w}$ 和偏置项 $b$ 的线性不等式。
• 因此，训练一个（软间隔或硬间隔）线性SVM的核心就是求解一个凸二次规划问题。

3. 其他应用

• 控制理论：在模型预测控制 (Model Predictive Control, MPC) 中，系统在每个时间步都需要通过求解一个QP问题来确定未来一系列的最优控制输入。
• 运筹学：用于解决资源分配、调度以及一些网络流问题。
• 经济学：在计算一般均衡模型和某些博弈论问题中也会用到二次规划。

求解方法

由于QP问题的重要性，研究人员开发了多种高效的算法来求解它，特别是针对凸QP问题。常见的方法包括：

• 内点法 (Interior-point methods)：对于大规模问题非常有效，是许多现代优化软件中的默认算法。
• 有效集法 (Active-set methods)：在每次迭代中猜测哪些不等式约束在最优解处是“有效的”（即取等号），然后求解一个只含等式约束的QP子问题。对于中小型问题非常高效。
• 梯度投影法 (Gradient projection methods)：一种类似于梯度下降的方法，但每次迭代后会将解投影回可行域。
• 增广拉格朗日法 (Augmented Lagrangian methods)：将带约束问题转化为一系列无约束或更简单约束的子问题来求解。

在实际应用中，通常直接使用成熟的优化软件包（如Python的\texttt{CVXPY}, \texttt{scipy.optimize}，或MATLAB的\texttt{quadprog}函数）来求解QP问题，而不需要从头实现这些算法。