# 二次规划 (Quadratic Programming)
二次规划 (Quadratic Programming, QP) 是{{{非线性规划}}} (Nonlinear Programming, NLP) 的一种特殊且重要的形式。在一个二次规划问题中，其目标是找出一组变量，使得一个 二次{{{目标函数}}} (quadratic objective function) 达到最小值（或最大化），同时这组变量必须满足一系列 线性{{{约束}}} (linear constraints)。
由于其数学结构的特殊性，二次规划在理论和实践中都扮演着关键角色。它被广泛认为是{{{线性规划}}} (Linear Programming, LP) 的自然扩展，同时也是解决更复杂的非线性问题的基础。二次规划在{{{金融学}}}、{{{机器学习}}}、{{{运筹学}}}、{{{机器人学}}}和{{{控制理论}}}等领域有非常重要的应用。
## 标准数学形式 (Standard Mathematical Form)
一个二次规划问题通常可以表示为以下标准形式：
$$ \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & \frac{1}{2} \mathbf{x}^T Q \mathbf{x} + \mathbf{c}^T \mathbf{x} \\ & \text{subject to} & & A \mathbf{x} = \mathbf{b} \quad (\text{等式约束}) \\ & & & G \mathbf{x} \le \mathbf{h} \quad (\text{不等式约束}) \end{aligned} $$
这里，各个组成部分的定义如下：
* $\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的`CVXPY`, `scipy.optimize`，或MATLAB的`quadprog`函数）来求解QP问题，而不需要从头实现这些算法。