1. 什么是二次规划（QP）

1.1 标准形式

二次规划是指：

目标函数是二次函数，约束是线性的优化问题。

标准 QP 形式：

$$\begin{array}{rlr}\underset{\mathbf{x}}{\min }& \frac{1}{2}{\mathbf{x}}^T\mathbf{Hx}+{\mathbf{f}}^T\mathbf{x}& \\ \text{s.t.}& \mathbf{Ax}=\mathbf{b}& \mathbf{Cx}\le \mathbf{d}\end{array}$$

其中：

符号	含义
$\mathbf{x}\in {\mathbb{R}}^n$	优化变量
$\mathbf{H}\in {\mathbb{R}}^{n\times n}$	Hessian（对称）
$\mathbf{f}\in {\mathbb{R}}^n$	线性项
$\mathbf{A},\mathbf{b}$	等式约束
$\mathbf{C},\mathbf{d}$	不等式约束

---

1.2 QP 的分类

无约束 QP

$$\underset{\mathbf{x}}{\min }\frac{1}{2}{\mathbf{x}}^T\mathbf{Hx}+{\mathbf{f}}^T\mathbf{x}$$

直接解：
$${\mathbf{x}}^{\star }=-{\mathbf{H}}^{-1}\mathbf{f}$$

---

仅等式约束 QP

用 KKT 条件 → 线性方程组解。

---

含不等式约束 QP

需要 主动集 / 内点法 / ADMM 等算法。

---

二、 二次规划的数学性质

记号与问题标准形式：
$$\begin{array}{rlrl}\underset{x\in {\mathbb{R}}^n}{\min }& \frac{1}{2}{x}^{\top }Hx+f^{\top }x\text{s.t.}& Ax=b,& Cx\le d,\end{array}$$
其中 $H\in {\mathbb{R}}^{n\times n}$ 对称，$f\in {\mathbb{R}}^n$，$A,C$ 为约束矩阵。

---

2.1 凸 QP vs 非凸 QP（代数与结论）

2.1.1 正定 / 半正定的含义与结论

• $H⪰0$（半正定） 意味着：$\forall v,v^{\top }Hv\ge 0$。

  • 若同时对可行域上的二次项“严格凸”，则问题全局凸，任何局部最小即为全局最小。
  • 当存在约束时（线性等式/不等式），满足 Slater 条件（存在严格可行点）时，强对偶成立：原问题的最优值等于对偶问题最优值。

• $H\succ 0$（严格正定） 意味着：$\forall v\ne 0,v^{\top }Hv>0$。

  • 目标函数在全域严格凸，若无约束（或约束可行且合适），解唯一：
    $$x^{\star }=-H^{-1}f$$
    （无约束情形）；
  • 含等式约束时，若 $A$ 的行线性无关且 KKT 矩阵可逆，则有唯一解（见下节 KKT 显式线性系统）。

• $H$ 仅半正定（奇异）时：

  • 在无约束但 $H⪰0$、且 $H$ 在可行方向上零模（存在 $v$ s.t. $Hv=0$ 且 $f^{\top }v\ne 0$）会导致无界或平坦方向（沿零特征向量方向目标为线性函数），解可能不唯一。
  • 等式约束可“去掉”零空间方向：若约束把零空间固定住可以恢复唯一性。

工程结论性：要得到数值稳定与唯一解，优先保证 $H\succ 0$ 或对 $H$ 施加适量的正则化（Tikhonov）$H+\lambda I$。

---

2.1.2 非凸 QP（$H$ 存在负特征值）

• 当 $H$ 含负特征值时，目标在某些方向上是“向下开口”的（即凹的方向），问题可能有 多个局部极小，甚至全局无界（若约束不能阻止沿负方向逃逸）。
• 一般非凸 QP 是 NP-hard（在最一般情形下），因此只能靠特殊结构、松弛（SDP）、分支定界（branch-and-bound）或启发式求解。

工程手段：

• 若问题来自线性化（例如某次线性化产生负特征值），常用做法是：修正 Hessian（取其正定近似）或加正则化 $\lambda I$（LM / Tikhonov）；或采用信赖域方法来保证步长不会进入凹区。

---

2.1.3 等式约束 QP 的闭式解（KKT 线性系统）

若只有等式约束 $Ax=b$，且 $H$ 对可行子空间为正定，可由 KKT 条件得到线性系统解。定义拉格朗日乘子 $\lambda$，KKT 条件：

$$\{\begin{array}{l}Hx+f+A^{\top }\lambda =0Ax=b\end{array}$$

合并为线性系统（KKT 矩阵）：

$$\left[\begin{array}{cc}H& A^{\top }\\ A& 0\end{array}\right]\left[\begin{array}{c}x\\ \lambda \end{array}\right]=\left[\begin{array}{c}-f\\ b\end{array}\right].$$

若该 KKT 矩阵可逆（例如 $H\succ 0$ 且 $A$ 行无关），则可直接解出 $(x,\lambda )$。这也是工程中很多稠密小尺度 QP 的常见解法。

---

2.2 数值稳定性与灵敏度（Conditioning）

2.2.1 条件数与求解稳定性

• 关键数量：$\kappa (H)=|H||H^{-1}|$（例如 2-范数条件数 = $|{\lambda }_{\max }/{\lambda }_{\min }|$）。

  • 当 $\kappa (H)$ 很大时，求解对数据（$H$、$f$、约束）的小扰动非常敏感 —— 可能导致解的大幅变化。

• 建议：若 ${\lambda }_{\min }(H)$ 很小（接近 0），常用做法是加正则化 $\lambda I$（使 ${\lambda }_{\min }$ 提高），或者用降秩近似（TSVD）。

2.2.2 灵敏度界

无约束情形 $x^{\star }=-H^{-1}f$，若 $H$ 与 $f$ 同时被小扰动 $\Delta H,\Delta f$，一阶近似敏感度可表示为：

$$\Delta x\approx -H^{-1}\Delta f+H^{-1}(\Delta H)H^{-1}f.$$

由此可以估计扰动放大因子与 $|H^{-1}|$（即约等于 $\kappa (H)/|H|$）有关。

---

2.3 退化（Degeneracy）与零特征值的几何/代数含义

• 若 $H$ 有零特征值（或很小的特征值），则目标函数在对应特征向量方向上平坦或近平坦。

• 如果这些方向同时没有被约束（$A$ / $C$ 不束缚这些方向），那么在这些方向上可以自由移动：

  • 无约束时：沿零空间若 $f$ 的分量为 0，则无穷多解（解不是唯一）；若 $f$ 在零空间上不为 0，则可能无界（目标可以沿负 $f$ 方向下降）。
  • 有等式/不等式约束时：约束可移除自由度，从而恢复唯一性或界定解集。

工程处理：

• 正则化（$H+\lambda I$）是最常见而简单的办法；
• 或者在问题建模时加入小先验约束来消除零空间。

---

2.4 二次项的谱分解与解的结构

对称矩阵 $H$ 的谱（特征）分解：

$$H=V\Lambda V^{\top },\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n).$$

在无约束情形，目标变换到特征坐标系为：

$$\underset{y}{\min }\frac{1}{2}{y}^{\top }\Lambda y+{\tilde{f}}^{\top }y,y=V^{\top }x,\tilde{f}=V^{\top }f.$$

于是各坐标的最优值是独立的（当 ${\lambda }_i>0$）：

$$y_i^{\star }=-{\tilde{f}}_i/{\lambda }_i.$$

直观结论：小特征值 ${\lambda }_i$ 会把对应分量放大（$y_i^{\star }$ 与 $1/{\lambda }_i$ 成正比），这反映了条件数对解放大的作用。

---

2.5 对偶问题与强对偶性（凸情形）

原问题（标准）：

$$\underset{x}{\min }\frac{1}{2}{x}^{\top }Hx+f^{\top }x\text{s.t. }Ax=b,Cx\le d.$$

构造拉格朗日函数（对等式与不等式引入乘子 $\lambda ,\mu (\mu \ge 0)$）并对 $x$ 求极小，可得到对偶问题（凸 QP 时）是另一个 QP（或最小化凸函数）：

• 在 凸 QP 且满足 Slater 条件（严格可行），强对偶成立：原问题的最优值 = 对偶问题最优值，KKT 条件成为必要且充分最优性条件。

工程意义：

• 对偶变量（拉格朗日乘子）有物理意义（例如约束的影子价格 / 灵敏度）。
• 对偶可用于构造停机判据、误差界、以及某些求解器（内点法）的残差监控。

---

2.6 KKT 条件与几何（互补松弛的直观解释）

KKT 条件一览（再次写出）：

1. 梯度消失（站位）：
   $$Hx+f+A^{\top }\lambda +C^{\top }\mu =0$$
2. 可行性：$Ax=b,Cx\le d$。
3. 对偶可行：$\mu \ge 0$。
4. 互补松弛：${\mu }_i(C_{i}x-d_i)=0$。（若第 i 个不等式为非活跃（严格小于），则 ${\mu }_i=0$）

几何直观：

• 二次等高线（椭球）“推进”直到接触可行域边界。
• 若接触在不等式的内部点（无活跃约束），则拉格朗日乘子不出现；若接触在边界上，对应约束成为 active，乘子视为“边界的法向力”抵消目标梯度的法分量。

---

2.7 特殊且常见的子情况

(a) 只有等式约束（已给 KKT 解法）

KKT 系统直接解线性方程组（稠密小规模）：复杂度主要在矩阵分解 $O(n^3)$。

(b) 只有边界约束（盒约束） $l\le x\le u$

这类 QP 常用投影梯度、坐标下降或专门的活性集法（qpOASES 也能高效处理）。若 $H$ 对角（或对角占优），可非常快速。

© 带稀疏 Hessian 的大规模 QP

SLAM / 大规模 MPC 的常见情形：利用稀疏线性代数（因子化、稀疏 LDLᵗ）是关键。内点法与活性集法都需要维持稀疏性。

---

2.8 二次规划的几何理解

• 目标的等高线是中心对称的椭球/椭圆，方向由 $H$ 的特征向量给定，轴长与特征值成反比。

• 约束是半空间交集（多面体）。

• 最优点几何上是 椭球收缩直到触及可行集的第一个位置。

  • 若最早接触点是在多面体的顶点（corner），通常多重约束同时活跃；若在边/面上，则对应较少约束活跃。

• 接触处的法向量与拉格朗日乘子方向一致（乘子大小衡量目标在被约束方向上的“下降能力”被约束反作用抵消的程度）。

---

2.9 非凸 QP 的常用处理

当 $H$ 非凸（含负特征值）但问题来源于线性化或近似时，常见策略：

1. 谱修正 / 取正定近似：令 $H_{\text{pos}}=V\max (\Lambda ,ϵI)V^{\top }$（把负/小特征值截断或提升）。

2. Tikhonov 正则化：$H+\lambda I$，数值简单且能提升条件数。

3. 信赖域方法：限制步长，避免进入凹区造成误步（尤其在非线性最小二乘中常用）。

4. 全局化方法（若必须求全局）：

   • 半正定松弛（SDP relaxation）将 QCQP 松弛为 SDP（常用于某些组合性/二次二次问题）。
   • 分支定界（branch-and-bound / branch-and-cut）：穷举+界（计算量大）。

---

2.10 简单二维例子

令 $n=2$，$H=\left[\begin{array}{cc}a& 0\\ 0& b\end{array}\right]$，$f=0$，目标为 $\frac{1}{2}(a{x}_1^2+b{x}_2^2)$。

• 等高线是轴对齐椭圆，主轴长度 $\propto 1/\sqrt{a}$ 和 $1/\sqrt{b}$。
• 若有不等式约束 $x_1\ge c$，最优点要么在 $(c,0)$（若 $c$ 大 enough），要么在 $(0,0)$（若可行且更优）。
• 若 $a\to 0$，椭圆沿 $x_1$ 方向伸长 → 解对 $f$ 中 $x_1$ 的分量极度敏感（需要正则化）。

---

2.11 额外重要结论

• 唯一性：若 $H\succ 0$ 且约束一致（不矛盾）则解唯一。

• 存在性：在凸 QP 中（$H⪰0$），若可行集非空且目标下界存在，则最优解存在（若可行集紧闭则一定存在）。

• 强对偶：若凸 QP 且满足 Slater，则强对偶成立。

• 数值建议：

  • 若条件数 $\kappa (H)$ 太大，优先加正则化或做特征截断（TSVD）。
  • 若 $H$ 奇异，请分析 $H$ 的零空间与约束 $A$ 的关系，或添加小先验约束。
  • 对大规模稀疏问题，使用稀疏 LDLᵗ / 因子化或专用求解器（OSQP、qpOASES、qpoases 等）。

---

2.12 与最小二乘（LS）与线性代数的关系

• 最小二乘问题是特殊的 QP：$H=A^{\top }A$（自然 PSD）。
• 如果 $A$ 列线性相关则 $H$ 奇异（说明 LS 有多解），一般用正则化或最小范数解（Moore–Penrose 伪逆）解决。

---

2.13 小结

1. 凸 QP（$H⪰0$）：可全局求解，KKT 给出必要充分条件，强对偶通常成立。
2. 严格凸（$H\succ 0$）：解唯一，数值稳定（前提条件数不过大）。
3. 奇异/退化（${\lambda }_{\min }\approx 0$）：导致多解/不稳定，需正则化或约束补偿。
4. 非凸 QP（含负特征值）：存在局部极小，工程上常通过谱修正 / 正则化 / 信赖域 来保证稳定与可行性；若要求全局最优需更复杂的全局算法（SDP、分支定界等）。
5. 几何视角（椭球 + 半空间）是理解活性约束、乘子物理意义与解的直观利器。

---