凸优化问题与对偶理论¶
前置自测¶
📋 前置自测（答不出 ≥ 2 题 → 先回凸分析基础和共轭函数章节复习）
- 什么是凸函数的一阶最优性条件？次梯度版本是什么？
- Fenchel-Young 不等式 \(f(x) + f^*(y) \geq \langle x, y\rangle\) 的等号条件是什么？
- 什么是半正定锥 \(\mathbb{S}^n_+\)？它为什么是自对偶的？
- 写出 \(\|x\|_1\) 的共轭函数和 proximal 算子。
- 分离超平面定理的几何含义是什么？它与最优性条件有什么关系？
本章目标¶
学完本章后，你将能够：(1) 看到一个凸优化问题能立即识别其类型（LP/QP/SOCP/SDP）并写出对偶；(2) 独立证明弱对偶和 Slater 条件下的强对偶；(3) 精确陈述 KKT 条件并理解其在凸问题中的充要性；(4) 理解对偶变量作为"影子价格"的经济学解释；(5) 为 MPC-QP、certifiable SLAM 的 SDP 松弛选择正确的求解器。
3.1 凸优化问题的标准形式与等价变换 ⭐¶
动机¶
在 SLAM 后端用 Gauss-Newton 解非线性最小二乘、在 MPC 中解 QP、在 certifiable perception 中解 SDP——这些看似不同的问题有一个共同结构：它们都是（或可以被松弛为）凸优化问题。识别问题的"类型"是选择正确求解器和理解问题难度的第一步。
标准形式¶
凸优化问题标准形式：
其中 \(f_0, f_1, ..., f_m\) 是凸函数，\(h_1, ..., h_p\) 是仿射函数。
为什么等式约束必须仿射：如果允许非线性等式约束 \(h(x) = 0\)（\(h\) 非仿射），则可行域 \(\{x \mid h(x) = 0\}\) 一般不是凸集。例如 \(x_1^2 + x_2^2 = 1\) 定义的是一个圆——这不是凸集。只有仿射等式约束 \(Ax = b\) 定义的集合（超平面的交，即仿射集）才保证凸性。
等价变换技巧大全 ⭐⭐¶
凸优化的一个核心技能是把"看起来不凸"的问题变换为标准凸形式。以下是常用技巧：
| 原始形式 | 变换后 | 类型 |
|---|---|---|
| \(\min \max_i f_i(x)\) | \(\min t\) s.t. \(f_i(x) \leq t\) | Epigraph |
| \(\min \|Ax-b\|_\infty\) | \(\min t\) s.t. \(-t \leq (Ax-b)_i \leq t\) | LP |
| \(\min \|Ax-b\|_1\) | \(\min \mathbf{1}^\top u\) s.t. \(-u \leq Ax-b \leq u\) | LP |
| \(\min f(x)/g(x)\) (\(g > 0\), \(f/g\) 拟凸) | 二分法 + 凸可行性 | 拟凸 |
| \(x \geq 0\), \(y \geq 0\), \(xy \geq 1\) | \((x, y, 1) \in\) 旋转 SOC | SOCP |
| \(\text{rank}(X) \leq r\) | \(\|X\|_* \leq \tau\)（松弛） | SDP |
| \(R^\top R = I\) | \(X \succeq 0\), \(X_{ii} = I\)（松弛） | SDP |
Epigraph 变换¶
很多看起来不符合标准形式的问题可以通过**引入辅助变量**转换。最常用的是 epigraph 变换：
应用：\(\min_x \max_i f_i(x)\) 不直接符合标准形式（目标不可微），但转为： $\(\min_{x, t} \; t \quad \text{s.t. } f_i(x) \leq t, \; i = 1,...,m\)$
这是标准凸优化问题（线性目标 + 凸约束）。
凸优化的根本性质¶
本质洞察：凸优化问题的核心保证是——任何局部最优解都是全局最优解。这不是"运气好"，而是凸性的数学必然：如果存在一个更好的可行点，凸性保证了连接局部最优和该点的路径上函数值单调不增，矛盾。
反事实推理：如果问题不是凸的会怎样？ - 可能有指数多个局部最优（如组合优化） - 梯度法只能找到局部最优，无法保证全局最优 - 没有高效的全局最优性判定方法
这就是为什么机器人学中"把问题凸化"（凸松弛、凸近似）如此重要。
凸化策略总结：
| 策略 | 方法 | 适用场景 | 精确度 |
|---|---|---|---|
| 凸松弛 | SDP/SOCP 松弛 | 旋转同步、QCQP | 可能精确（tight） |
| 凸近似 | Sequential Convex Programming | 轨迹优化 | 近似（局部） |
| 凸包络 | 用 \(f^{**}\) 替代非凸 \(f\) | 核范数替代秩 | 最紧凸下界 |
| Continuation | Moreau 包络从凸到非凸 | GNC 鲁棒估计 | 逐步逼近 |
| 对偶下界 | Lagrange 对偶 | 任何问题 | 全局下界 |
⚠️ 常见陷阱¶
💡 概念误区：忽略凸优化的等价变换 - Boyd 反复强调 epigraph 变换、松弛变量、变量替换可以把看起来不凸的问题化为凸 - 例如 \(\min \|Ax-b\|_\infty\) 看起来不光滑不凸，但等价于 LP - 初学者常在原变量空间苦苦思索而忽略换元
凸优化的算法复杂度理论 ⭐⭐¶
一阶方法复杂度下界（Nemirovsky & Yudin, 1983）：对 \(L\)-光滑凸优化问题，任何黑箱一阶方法至少需要 \(\Omega(1/\sqrt{\epsilon})\) 次梯度计算才能达到 \(\epsilon\) 精度（光滑凸情形）；对 \(\mu\)-强凸且 \(L\)-光滑问题，下界为 \(\Omega(\sqrt{\kappa}\log(1/\epsilon))\)，其中 \(\kappa = L/\mu\)。
这个下界被内点法匹配：IPM 的迭代次数是 \(O(\sqrt{n} \log(1/\epsilon))\)——每次迭代需要 \(O(n^2)\) 到 \(O(n^3)\) 的计算，总复杂度为 \(O(n^{3.5} \log(1/\epsilon))\)。
各类问题的复杂度分类：
| 问题 | 最佳已知复杂度 | 下界 | 是否 tight |
|---|---|---|---|
| LP | \(O(n^{2.5} L)\) (IPM) | \(\Omega(n L)\)? | 未知 |
| 凸 QP | \(O(n^3)\) (IPM) | \(\Omega(n^{2.37})\)（矩阵乘法） | 接近 |
| 一般凸 | \(O(1/\epsilon^2)\) (一阶) | \(\Omega(1/\epsilon^2)\) | 是 |
| 强凸 | \(O(\sqrt{\kappa}\log(1/\epsilon))\) (加速) | \(\Omega(\sqrt{\kappa}\log(1/\epsilon))\) | 是 |
练习¶
- 把 \(\min_x \|Ax - b\|_\infty\) 化为标准 LP 形式。提示：引入变量 \(t\)，约束 \(-t \leq (Ax-b)_i \leq t\)。
- 把 \(\min_x \|Ax - b\|_1\) 化为标准 LP 形式。提示：分裂正负部分 \(u_i = (Ax-b)_i^+\)，\(v_i = (Ax-b)_i^-\)。
- 证明：凸优化问题的最优解集是凸集。提示：利用目标函数的凸性。
- 证明：若 \(f_0\) 严格凸，凸优化问题最多有一个最优解。
- 把 \(\min \text{rank}(X)\) s.t. \(\mathcal{A}(X) = b\) 的核范数松弛写出，并解释为什么核范数是秩函数的凸包络。
3.2 凸优化问题的六大家族 ⭐⭐¶
动机¶
凸优化问题不是"一锅端"——它们有精细的层级结构。从最简单的 LP 到最复杂的 SDP，每一级都有专用的高效求解器。识别问题类型 = 选对求解器 = 实际可解。
LP（线性规划）⭐¶
标准形式：\(\min c^\top x\) s.t. \(Ax \leq b\), \(Cx = d\)
特点： - 可行域是多面体 - 最优解在顶点取到（单纯形法的基础） - 多项式时间可解（内点法 / 椭球法） - 强对偶几乎总成立（只要一方可行有界）
LP 的三种等价形式：
| 形式 | 表达 | 用途 |
|---|---|---|
| 不等式形式 | \(\min c^\top x\) s.t. \(Ax \leq b\) | 最直观 |
| 标准形式 | \(\min c^\top x\) s.t. \(Ax = b\), \(x \geq 0\) | 单纯形法 |
| 自由变量形式 | \(\min c^\top x\) s.t. \(Ax = b\) | 理论分析 |
三种形式可以通过引入松弛变量和变量分裂互相转化。
机器人应用： - 网络流、任务分配 - \(\ell_1\) 优化（稀疏恢复）可以化为 LP - \(\ell_\infty\) 优化（minimax）可以化为 LP - 某些轨迹规划的线性化子问题
QP（二次规划）⭐⭐¶
标准形式：\(\min \frac{1}{2}x^\top P x + q^\top x\) s.t. \(Gx \leq h\), \(Ax = b\)
凸性要求 \(P \succeq 0\)。
机器人应用： - MPC：每个时间步解一个 QP（OSQP, qpOASES, HPIPM） - CBF-QP：安全约束下的控制（CLF-CBF-QP） - 全身控制（WBC/TSID）：力分配问题（ProxQP） - 逆运动学：最小范数关节速度
求解器选择：
| 求解器 | 方法 | 场景 | 速度 |
|---|---|---|---|
| OSQP | ADMM | 通用 MPC | 毫秒级 |
| qpOASES | Active-set | 参数化 QP | 微秒级（warm-start） |
| HPIPM | IPM + Riccati | 长 horizon | 最快（结构利用） |
| ProxQP | 增广 Lagrangian | 全身控制 | 毫秒级 |
QP 的对偶推导 ⭐⭐¶
原问题：\(\min \frac{1}{2}x^\top Px + q^\top x\) s.t. \(Gx \leq h\), \(Ax = b\)（\(P \succeq 0\)）。
Lagrangian：\(L(x, \lambda, \nu) = \frac{1}{2}x^\top Px + q^\top x + \lambda^\top(Gx-h) + \nu^\top(Ax-b)\)
对偶函数：对 \(x\) 求导令零：\(Px + q + G^\top\lambda + A^\top\nu = 0\)
若 \(P \succ 0\)：\(x^* = -P^{-1}(q + G^\top\lambda + A^\top\nu)\)
代回：\(g(\lambda,\nu) = -\frac{1}{2}(q+G^\top\lambda+A^\top\nu)^\top P^{-1}(q+G^\top\lambda+A^\top\nu) - h^\top\lambda - b^\top\nu\)
对偶问题（QP 对偶也是 QP）： $\(\max_{\lambda \geq 0, \nu} -\frac{1}{2}(q+G^\top\lambda+A^\top\nu)^\top P^{-1}(q+G^\top\lambda+A^\top\nu) - h^\top\lambda - b^\top\nu\)$
LP 的对偶（\(P = 0\) 的特例）：
原问题 \(\min c^\top x\) s.t. \(Ax \leq b\)。Lagrangian \(L = c^\top x + \lambda^\top(Ax-b) = (c+A^\top\lambda)^\top x - b^\top\lambda\)。
\(g(\lambda) = \inf_x (c+A^\top\lambda)^\top x = \begin{cases} -b^\top\lambda & A^\top\lambda = -c \\ -\infty & \text{otherwise} \end{cases}\)
LP 对偶：\(\max -b^\top\lambda\) s.t. \(A^\top\lambda = -c\), \(\lambda \geq 0\)，即 \(\max b^\top y\) s.t. \(A^\top y \leq c\)（换符号）。
SOCP（二阶锥规划）⭐⭐¶
标准形式： $\(\min f^\top x \quad \text{s.t. } \|A_i x + b_i\|_2 \leq c_i^\top x + d_i, \quad i = 1,...,m\)$
几何含义：约束要求 \((A_i x + b_i, c_i^\top x + d_i)\) 在二阶锥（ice cream cone）内。
机器人应用： - 摩擦锥约束：接触力 \(f\) 必须满足 \(\|f_t\| \leq \mu f_n\) - 鲁棒 LP：参数不确定时的 worst-case 保证化为 SOCP - 推力约束轨迹优化：火箭着陆（SpaceX 用的凸化方法）
SOCP 的对偶 ⭐⭐⭐¶
SOCP 原问题 \(\min f^\top x\) s.t. \(\|A_i x + b_i\| \leq c_i^\top x + d_i\) 的对偶也是 SOCP——对偶变量 \((u_i, v_i)\) 满足 \(\|u_i\| \leq v_i\)（也在二阶锥中）。这种"自对偶性"使得 SOCP 的理论特别干净。
鲁棒 LP → SOCP 的推导 ⭐⭐：
考虑约束 \((a_i + u_i)^\top x \leq b_i\)，其中 \(\|u_i\| \leq \rho_i\)（参数不确定性）。
worst-case 要求：\(\sup_{\|u_i\| \leq \rho_i} (a_i + u_i)^\top x \leq b_i\)
\(\sup_{\|u\| \leq \rho} u^\top x = \rho\|x\|\)（Cauchy-Schwarz 等号条件）
因此约束变为 \(a_i^\top x + \rho_i\|x\| \leq b_i\)，即 \(\|x\| \leq (b_i - a_i^\top x)/\rho_i\)——这是 SOC 约束。
SDP（半正定规划）⭐⭐⭐¶
标准形式： $\(\min \langle C, X \rangle \quad \text{s.t. } \langle A_i, X \rangle = b_i, \; i = 1,...,m, \quad X \succeq 0\)$
其中 \(\langle A, B \rangle = \text{tr}(A^\top B)\) 是矩阵内积。
为什么 SDP 如此重要： 1. 它是锥规划层级的"顶端"：LP \(\subset\) QP \(\subset\) SOCP \(\subset\) SDP 2. 很多非凸问题可以松弛为 SDP（Shor 松弛、Lasserre 层级） 3. 控制综合（LMI）、Lyapunov 稳定性验证、SOS 多项式验证都化为 SDP
机器人应用： - Certifiable SLAM（SE-Sync）：旋转同步的非凸 QCQP → SDP 松弛 - LMI 控制综合：\(A^\top P + PA \prec 0, P \succ 0\) → SDP 可行性 - SOS-Lyapunov：多项式 \(V(x) > 0\) 验证 → SDP
锥包含链¶
每一级严格包含前一级。计算复杂度也逐级增加：LP 是 \(O(n^{2.5}L)\)，SDP 最坏情况是 \(O(n^6)\)。
**Schur 互补**是连接各级的桥梁。例如 SOCP 约束 \(\|Ax+b\| \leq c^\top x + d\) 可以通过 Schur 互补写成 LMI：
锥规划的统一框架 ⭐⭐⭐¶
所有前面讨论的问题（LP、QP、SOCP、SDP）都可以统一到**锥规划**（Conic Programming）框架中：
其中 \(K\) 是一个 proper cone（闭凸锥，有非空内部，pointed）。
| 问题类型 | 锥 \(K\) | 维度 |
|---|---|---|
| LP | \(\mathbb{R}^n_+\)（非负象限） | \(n\) |
| SOCP | \(\text{SOC}_{n_1} \times ... \times \text{SOC}_{n_k}\)（二阶锥的笛卡尔积） | \(\sum n_i\) |
| SDP | \(\mathbb{S}^n_+\)（半正定锥） | \(\binom{n+1}{2}\) |
锥规划对偶的统一形式：
原问题 \(\min c^\top x\) s.t. \(Ax = b\), \(x \in K\)。
对偶问题 \(\max b^\top y\) s.t. \(c - A^\top y \in K^*\)（\(K^*\) 是对偶锥）。
自对偶锥（\(K^* = K\)）：\(\mathbb{R}^n_+\)、\(\text{SOC}_n\)、\(\mathbb{S}^n_+\) 都是自对偶的。这使得原问题和对偶问题有相同的结构——对偶的对偶回到原问题（Fenchel-Moreau 在锥规划中的体现）。
锥互补松弛：\(\langle x, s \rangle = 0\)，\(x \in K\)，\(s \in K^*\)。
对 LP：\(x_i s_i = 0\)（逐元素互补）。 对 SOCP：\(\langle x, s \rangle = 0\)，\(x, s \in \text{SOC}\)。 对 SDP：\(\text{tr}(XS) = 0\)，\(X, S \succeq 0\)，即 \(XS = 0\)（矩阵互补）。
SOCP 对偶的完整推导 ⭐⭐¶
考虑标准 SOCP：\(\min f^\top x\) s.t. \(\|A_i x + b_i\|_2 \leq c_i^\top x + d_i\)（\(i=1,...,m\)）。
Step 1：引入辅助变量 \(t_i = c_i^\top x + d_i\)，\(u_i = A_i x + b_i\)，约束变为 \(\|u_i\| \leq t_i\)，即 \((u_i, t_i) \in \text{SOC}\)。
Step 2：写 Lagrangian。对偶变量 \((\alpha_i, \beta_i)\) 对应锥约束： $\(L = f^\top x + \sum_i [\alpha_i^\top(A_i x + b_i - u_i) + \beta_i(c_i^\top x + d_i - t_i)]\)$
加上锥约束的对偶条件 \((\alpha_i, \beta_i) \in \text{SOC}^*\)（\(\|\alpha_i\| \leq \beta_i\)）。
Step 3：对 \(x\) 求 inf：\(f + \sum_i(A_i^\top\alpha_i + c_i\beta_i) = 0\)（稳定性）。
Step 4：对偶问题： $\(\max -\sum_i(b_i^\top\alpha_i + d_i\beta_i)\)$ $\(\text{s.t. } f + \sum_i(A_i^\top\alpha_i + c_i\beta_i) = 0, \; \|\alpha_i\| \leq \beta_i\)$
对偶变量也在二阶锥中——SOCP 对偶是自对偶的。
⚠️ 常见陷阱¶
🧠 思维陷阱：把 LP 的强对偶直觉直接移植到 SDP - LP 只要原问题可行且有界，就有强对偶 - SDP 可以有有限正对偶间隙（Ramana 经典例子） - 原因：半正定锥的相对内部可能与约束仿射空间相交于边界 - SDP 的强对偶需要 Slater 条件（严格可行解存在）
💡 概念误区：DCP 规则误用 - CVXPY 拒绝
x*y或sqrt(quad_form(x,P))不是因为"问题不凸" - 而是不满足 DCP 合成规则（编译器无法自动验证凸性） - 解决方法：用 DCP-compatible atom 或手动做等价变换
各层级的复杂度与实际规模¶
| 层级 | 理论复杂度 | 实际求解规模 | 求解器 |
|---|---|---|---|
| LP | \(O(n^{2.5} L)\) | \(n \sim 10^6\) | HiGHS, Gurobi |
| QP | \(O(n^3)\) | \(n \sim 10^4\) | OSQP, HPIPM |
| SOCP | \(O(n^{3.5})\) | \(n \sim 10^3\) | ECOS, Clarabel |
| SDP | \(O(n^6)\) (worst) | \(n \sim 10^2\) | MOSEK, SCS |
机器人学中的问题识别流程¶
Step 1：检查目标函数类型（线性/二次/非线性凸/非凸）。 Step 2：检查约束类型（线性/范数/LMI/正交）。 Step 3：匹配到 LP/QP/SOCP/SDP/NLP 并选求解器。 Step 4：用 CVXPY 验证并检查 KKT 残差。
QCQP 与 Shor 松弛 ⭐⭐⭐¶
QCQP（二次约束二次规划）：\(\min x^\top P_0 x + q_0^\top x\) s.t. \(x^\top P_i x + q_i^\top x \leq b_i\)
若所有 \(P_i \succeq 0\)（凸 QCQP）→ SOCP 子类。若某些 \(P_i\) 不 PSD → 非凸，NP-hard。
Shor 松弛：令 \(X = xx^\top\)，约束 \(x^\top P_i x = \text{tr}(P_i X)\)。放松 \(X = xx^\top\) 为 \(X \succeq 0\)（去掉 rank-1 约束）→ SDP。
松弛 tight 的判据：\(\text{rank}(X^*) = 1\)。此时 $x^* = $ 从 \(X^*\) 提取的向量就是全局最优。
在 SLAM 中的应用：旋转同步 \(\min \sum \|R_i - R_{ij}R_j\|^2\) s.t. \(R^\top R = I\) 是非凸 QCQP → Shor 松弛为 SDP → SE-Sync。
练习¶
- 把 Markowitz portfolio 优化 \(\min x^\top \Sigma x\) s.t. \(\mu^\top x \geq r, \mathbf{1}^\top x = 1, x \geq 0\) 识别为哪类问题？写出其 CVXPY 代码。
- 证明 SOCP \(\subset\) SDP（利用 Schur 互补将 SOC 约束写成 LMI）。
- 对鲁棒最小二乘 \(\min_x \sup_{\|u\| \leq \rho} \|(A+u)x - b\|\)，推导其等价 SOCP 形式。
3.3 Lagrange 对偶与弱对偶 ⭐⭐¶
动机¶
对偶理论的核心问题：能否从"外部"给出原问题最优值的下界？ 如果能，且下界恰好等于最优值（强对偶），那么我们就有了一个判定最优性的工具。
对偶理论的历史背景¶
Lagrange 乘子法由 Joseph-Louis Lagrange (1736-1813) 在 1788 年的《分析力学》中提出，用于处理约束下的力学问题。但现代意义上的对偶理论——特别是弱对偶和强对偶的精确条件——主要由以下人物发展：
| 年代 | 贡献 | 贡献者 |
|---|---|---|
| 1788 | Lagrange 乘子（等式约束） | Lagrange |
| 1939 | 线性规划对偶 | von Neumann (未发表) |
| 1947 | LP 对偶定理 | Dantzig, Gale-Kuhn-Tucker |
| 1951 | 非线性规划 KKT 条件 | Karush (1939), Kuhn & Tucker |
| 1951 | Fenchel 对偶 | Fenchel |
| 1970 | 凸分析统一框架 | Rockafellar |
| 1996 | SDP 对偶综述 | Vandenberghe & Boyd |
| 2004 | 工程化的对偶理论教材 | Boyd & Vandenberghe |
跨领域类比：对偶理论之于优化，就像 Fourier 变换之于信号处理。两者都把问题从一个"空间"映射到另一个"空间"，在新空间中某些困难变得简单。Fourier 变换把卷积变成乘法，对偶变换把约束优化变成无约束优化（对偶函数自动满足约束）。
Lagrangian¶
定义 3.3.1：考虑优化问题 \(\min f_0(x)\) s.t. \(f_i(x) \leq 0\), \(h_j(x) = 0\)。
其 Lagrangian 为： $\(L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x)\)$
其中 \(\lambda_i \geq 0\) 是不等式约束的对偶变量（Lagrange 乘子），\(\nu_j\) 是等式约束的对偶变量。
直觉：Lagrangian 通过"软化"约束来获得下界——把硬约束 \(f_i(x) \leq 0\) 变成惩罚项 \(\lambda_i f_i(x)\)。当约束被违反时（\(f_i > 0\)），惩罚为正，增加目标值；当约束被满足时（\(f_i < 0\)），"奖励"为负，减少目标值。
经济学解释：\(\lambda_i\) 是约束 \(f_i(x) \leq 0\) 的"价格"。如果放松约束（允许 \(f_i \leq \epsilon\)），最优值大约改善 \(\lambda_i \epsilon\)。所以 \(\lambda_i\) 衡量了"这个约束值多少钱"——即**影子价格**。
对偶函数¶
定义 3.3.2：对偶函数 \(g: \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} \cup \{-\infty\}\)：
对偶函数的关键性质 ⭐⭐¶
性质 1：对偶函数永远凹。无论原问题是否凸！
证明：\(g(\lambda, \nu)\) 是仿射函数（关于 \((\lambda, \nu)\)）的逐点 infimum。仿射函数既凸又凹，inf 保凹（类似 sup 保凸），故 \(g\) 凹。
等价地：\(g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)\)，对每个固定 \(x\)，\(L(x, \lambda, \nu)\) 关于 \((\lambda, \nu)\) 是仿射的（因此凹的）。凹函数族的 infimum 仍凹。
性质 2：对偶函数给出原问题的下界。
定理 3.3.3（弱对偶）：对任何 \(\lambda \succeq 0\) 和任何 \(\nu\)：
其中 \(p^*\) 是原问题最优值。
证明（三行完成）：设 \(\tilde{x}\) 是任意可行点。则 \(f_i(\tilde{x}) \leq 0\) 且 \(h_j(\tilde{x}) = 0\)。
对所有可行 \(\tilde{x}\) 成立，取 inf：\(g(\lambda, \nu) \leq p^*\)。
本质洞察：弱对偶的本质是——通过"放松"约束（乘以非负权重加到目标上），我们只能让最优值变得更好（更小），不会变差。因此对偶函数的每个值都是原问题最优值的下界。
对偶问题¶
定义 3.3.4（对偶问题）： $\(d^* = \max_{\lambda \succeq 0, \nu} g(\lambda, \nu) = \max_{\lambda \succeq 0, \nu} \inf_x L(x, \lambda, \nu)\)$
对偶问题是：在所有下界中找最紧的那个。
对偶间隙：\(p^* - d^* \geq 0\)（由弱对偶）。若 \(p^* - d^* = 0\)，称强对偶成立。
对偶间隙的几何解释：
考虑"值函数" \(p(u) = \inf\{f_0(x) : f_i(x) \leq u_i\}\)（约束松弛 \(u\) 的最优值函数）。
弱对偶说的是：\(g(\lambda) = \inf_x L(x, \lambda) = \inf_u [p(u) + \lambda^\top u]\)（\(p\) 的 Fenchel 共轭的负数）。
几何上：\(g(\lambda)\) 是 \(p(u)\) 的一个支撑超平面（斜率 \(-\lambda\)、截距 \(g(\lambda)\)）在 \(u = 0\) 处的值。\(d^* = \max g(\lambda)\) 是所有这样的支撑超平面中，在 \(u=0\) 处值最大的那个。
强对偶 \(d^* = p^* = p(0)\) 意味着：最好的支撑超平面恰好在 \(u=0\) 处"触碰" \(p\) 的图像——这正是 \(p\) 在 \(u=0\) 处"闭凸"的要求，即 \(p^{**}(0) = p(0)\)。Slater 条件保证了这一点。
反事实推理：如果 \(p(u)\) 在 \(u=0\) 处不连续（有向下的跳跃），那么支撑超平面无法精确触碰，强对偶失败。Slater 条件排除了这种不连续性——严格可行意味着 \(p\) 在 \(u=0\) 附近"行为良好"。
⚠️ 常见陷阱¶
💡 概念误区：混淆弱对偶和强对偶 - 弱对偶 \(g(\lambda,\nu) \leq p^*\) 对**任何**优化问题（包括非凸）永远成立 - 强对偶 \(d^* = p^*\) 需要凸性 + 约束品性（Slater 条件） - 写论文时把"对偶给出下界"说成"对偶等于最优"是最频繁的错误
🧠 思维陷阱：认为对偶问题只对凸问题有用 - 即使原问题非凸，对偶问题仍然是凸的（\(g\) 凹 → \(\max g\) 是凸优化） - 对偶下界在非凸问题中依然有价值——用于 certifiable 算法的最优性证书 - SE-Sync 正是利用非凸 QCQP 的 SDP 对偶来给出全局最优证书
对偶函数的详细计算示例 ⭐⭐¶
例 1：最简单的约束优化
\(\min x^2\) s.t. \(x \geq 1\)（等价于 \(-x + 1 \leq 0\)）
Lagrangian：\(L(x, \lambda) = x^2 + \lambda(-x + 1) = x^2 - \lambda x + \lambda\)
对偶函数：\(g(\lambda) = \inf_x [x^2 - \lambda x + \lambda]\)
求导令零：\(2x - \lambda = 0 \Rightarrow x = \lambda/2\)
代回：\(g(\lambda) = \lambda^2/4 - \lambda^2/2 + \lambda = -\lambda^2/4 + \lambda\)
对偶问题：\(\max_{\lambda \geq 0} -\lambda^2/4 + \lambda\)
求导令零：\(-\lambda/2 + 1 = 0 \Rightarrow \lambda^* = 2\)
\(d^* = g(2) = -1 + 2 = 1 = p^*\)（\(x^* = 1\) 时 \(f = 1\)）。强对偶成立！
验证 KKT：\(x^* = 1\), \(\lambda^* = 2\)。 1. 原可行：\(-x^* + 1 = 0 \leq 0\) ✓ 2. 对偶可行：\(\lambda^* = 2 \geq 0\) ✓ 3. 互补松弛：\(\lambda^*(-x^*+1) = 2 \cdot 0 = 0\) ✓ 4. 稳定性：\(2x^* - \lambda^* = 2 - 2 = 0\) ✓
例 2：两个不等式约束
\(\min x_1^2 + x_2^2\) s.t. \(x_1 + x_2 \geq 1\)，\(x_1 \geq 0\)
Lagrangian：\(L = x_1^2 + x_2^2 + \lambda_1(-x_1-x_2+1) + \lambda_2(-x_1)\)
对偶函数： $\(\frac{\partial L}{\partial x_1} = 2x_1 - \lambda_1 - \lambda_2 = 0 \Rightarrow x_1 = (\lambda_1+\lambda_2)/2\)$ $\(\frac{\partial L}{\partial x_2} = 2x_2 - \lambda_1 = 0 \Rightarrow x_2 = \lambda_1/2\)$
代回：\(g(\lambda_1, \lambda_2) = -(\lambda_1+\lambda_2)^2/4 - \lambda_1^2/4 + \lambda_1\)
对偶问题：\(\max_{\lambda_1, \lambda_2 \geq 0} g(\lambda_1, \lambda_2)\)
求解得 \(\lambda_1^* = 1\)，\(\lambda_2^* = 0\)，\(x^* = (1/2, 1/2)\)，\(p^* = 1/2\)。
第二个约束 inactive（\(x_1^* = 1/2 > 0\)），故 \(\lambda_2^* = 0\)（互补松弛）。
例 3：等式约束的对偶
\(\min \|x\|^2\) s.t. \(Ax = b\)
Lagrangian：\(L(x, \nu) = \|x\|^2 + \nu^\top(Ax - b)\)
对偶函数：\(\nabla_x L = 2x + A^\top\nu = 0 \Rightarrow x = -A^\top\nu/2\)
\(g(\nu) = \|A^\top\nu/2\|^2 - \nu^\top A A^\top\nu/2 - \nu^\top b = -\nu^\top AA^\top\nu/4 - \nu^\top b\)
对偶问题：\(\max_\nu -\frac{1}{4}\nu^\top AA^\top\nu - b^\top\nu\)（无约束！）
求导令零：\(-AA^\top\nu/2 - b = 0 \Rightarrow \nu^* = -2(AA^\top)^{-1}b\)
\(x^* = -A^\top\nu^*/2 = A^\top(AA^\top)^{-1}b = A^\dagger b\)（Moore-Penrose 伪逆！）
本质洞察：最小范数最小二乘解 \(A^\dagger b\) 可以通过对偶理论自然地推导出来——它不是"凑出来的"，而是对偶最优条件的直接结果。
练习¶
- 对 \(\min x^2\) s.t. \(x \geq 1\)，写出 Lagrangian，计算对偶函数 \(g(\lambda)\)，验证弱对偶（已在上面解答，请独立复现）。
- 对 \(\min c^\top x\) s.t. \(Ax = b, x \geq 0\)（LP 标准形式），推导其对偶问题。验证 LP 对偶的标准形式。
- 对二次规划 \(\min \frac{1}{2}x^\top P x + q^\top x\) s.t. \(Ax \leq b\)，写出对偶函数的闭式解。
- 对 \(\min \|x\|_1\) s.t. \(Ax = b\)，推导对偶问题（提示：\(\|\cdot\|_1\) 的共轭是 \(\delta_{\|\cdot\|_\infty \leq 1}\)）。
3.4 强对偶与 Slater 条件 ⭐⭐¶
动机¶
弱对偶总是成立的，但"下界 = 最优值"（强对偶）何时成立？这个问题的答案决定了：(1) 对偶方法何时能精确求解原问题；(2) KKT 条件何时是充要的；(3) certifiable 算法何时能提供全局最优证书。
Slater 条件¶
定义 3.4.1（Slater 条件）：凸优化问题满足 Slater 条件，如果存在严格可行点 \(\tilde{x}\)：
注意：对仿射不等式约束 \(a_i^\top x \leq b_i\)，不需要严格满足（只需 \(\leq\)）。这被称为 sharpened Slater 条件，在实际中经常简化验证。
强对偶定理¶
定理 3.4.2：若凸优化问题满足 Slater 条件，则强对偶成立：\(d^* = p^*\)。且对偶最优被取到（即存在 \(\lambda^*, \nu^*\) 使 \(g(\lambda^*, \nu^*) = p^*\)）。
证明核心思想 ⭐⭐⭐¶
几何证明路径（Boyd §5.3.2 的思想）：
定义集合 \(\mathcal{A} \subset \mathbb{R}^{m+1}\)： $\(\mathcal{A} = \{(u, t) \mid \exists x : f_i(x) \leq u_i, h_j(x) = 0, f_0(x) \leq t\}\)$
\(\mathcal{A}\) 是凸集（因为 \(f_i\) 凸，\(h_j\) 仿射）。
\(p^*\) 的几何含义：\(p^* = \inf\{t \mid (0, t) \in \mathcal{A}\}\)。
定义集合 \(\mathcal{B} = \{(0, s) \mid s < p^*\}\)（\(\mathcal{A}\) 的"下方"）。
关键：\(\mathcal{A} \cap \mathcal{B} = \emptyset\)（因为不存在 \(x\) 使约束可行且 \(f_0(x) < p^*\)）。
由分离超平面定理，存在非零 \((\tilde\lambda, \mu) \neq 0\)（\(\tilde\lambda \in \mathbb{R}^m, \mu \in \mathbb{R}\)）使得：
可以证明 \(\mu > 0\)（利用 Slater 条件）和 \(\tilde\lambda \geq 0\)。
令 \(\lambda = \tilde\lambda / \mu\)，则分离条件给出 \(g(\lambda, \nu) \geq p^*\)。结合弱对偶 \(g \leq p^*\)，得 \(g(\lambda, \nu) = p^*\)。
Slater 条件的作用：它保证了 \(\mu > 0\)（分离超平面不是"水平的"），从而可以正规化得到有限的对偶变量。如果没有 Slater，\(\mu\) 可能为 0，强对偶可能失败。
为什么 \(\mu > 0\)——Slater 条件的关键作用 ⭐⭐⭐¶
让我们详细解释证明中"\(\mu > 0\)"这一步，因为它是整个强对偶证明的关键。
假设 \(\mu = 0\)。则分离超平面的法向量为 \((\tilde\lambda, 0)\)（\(\tilde\lambda \in \mathbb{R}^m\)），分离条件变为： $\(\tilde\lambda^\top u \geq 0, \quad \forall (u, t) \in \mathcal{A}\)$
这意味着 \(\tilde\lambda^\top u \geq 0\) 对所有可行的松弛向量 \(u\) 成立。
但由 Slater 条件，存在严格可行点 \(\tilde{x}\) 使 \(f_i(\tilde{x}) < 0\)。令 \(\tilde{u} = (f_1(\tilde{x}), ..., f_m(\tilde{x})) < 0\)，则 \((\tilde{u}, f_0(\tilde{x})) \in \mathcal{A}\)。
分离条件要求 \(\tilde\lambda^\top \tilde{u} \geq 0\)。但 \(\tilde\lambda \geq 0\)（可以证明）且 \(\tilde{u} < 0\)，故 \(\tilde\lambda^\top \tilde{u} \leq 0\)，等号仅在 \(\tilde\lambda = 0\) 时成立。
但法向量 \((\tilde\lambda, \mu)\) 非零，若 \(\mu = 0\) 则 \(\tilde\lambda \neq 0\)，矛盾。因此 \(\mu > 0\)。
本质洞察：Slater 条件的几何含义是——可行域有"厚度"（不是贴着约束边界的薄片）。这保证了分离超平面不能是"水平的"（\(\mu = 0\)），从而目标函数的值在分离中起作用，使得对偶变量有限。
强对偶失败的例子¶
例 1（正对偶间隙）：考虑以下非凸问题（Boyd & Vandenberghe 5.2.4 改编）：
可行域是圆盘 \(\{(x_1,x_2): (x_1+1)^2 + x_2^2 \leq 1\}\) 与半平面 \(\{x_1 \geq 0\}\) 的交集，即单点 \(\{(0,0)\}\)，故 \(p^* = 0\)。
将第二个约束改写为 \(-x_1 \leq 0\)。Lagrangian： $\(\mathcal{L} = x_1 + \lambda_1[(x_1+1)^2 + x_2^2 - 1] + \lambda_2(-x_1)\)$ 对偶函数 \(g(\lambda_1, \lambda_2) = \inf_{x} \mathcal{L}\)： - 当 \(\lambda_1 > 0\) 时，对 \(x_2\) 求 inf 得 \(x_2 = 0\)；对 \(x_1\) 求 inf 得 \(x_1 = -(1-\lambda_2)/(2\lambda_1) - 1\)，代回得 \(g = -\frac{(1-\lambda_2)^2}{4\lambda_1} + \lambda_1 \cdot 0 - \lambda_1 = -\frac{(1-\lambda_2)^2}{4\lambda_1} - \lambda_1\)。 - 对 \(\lambda_1 > 0, \lambda_2 \geq 0\) 优化，可证 \(d^* = \sup g(\lambda_1, \lambda_2) = -1 < 0 = p^*\)。
因此对偶间隙 \(= p^* - d^* = 1 > 0\)。Slater 条件在这里失败——约束交集退化为单点，没有严格可行的相对内点。
例 2（对偶最优不可达，但无间隙）：考虑一个相关但不同的现象：\(\min x_1\) s.t. \(x_1^2 + x_2^2 \leq 0\)。可行域只有原点，\(p^* = 0\)。计算对偶函数 \(g(\lambda) = \inf_x \{x_1 + \lambda(x_1^2+x_2^2)\}\)：当 \(\lambda > 0\) 时，\(g(\lambda) = -1/(4\lambda) \to 0^-\)（当 \(\lambda \to \infty\)），故 \(d^* = 0 = p^*\)。这里**没有对偶间隙**，但对偶最优值不可达（没有有限的 \(\lambda^*\) 实现 \(g(\lambda^*) = 0\)）。此时 KKT 乘子不存在。
警告：这两种现象经常被混淆。"对偶间隙 > 0"（例 1）和"对偶最优不可达"（例 2）都导致 KKT 条件无法正常使用，但它们是**不同的失败模式**。Slater 条件保证两者同时不发生。
教训：Slater 条件不是"花哨的技术条件"——它是强对偶成立（零间隙 + 对偶可达）的实质性要求。没有它，整个 KKT 理论都可能失效。
⚠️ 常见陷阱¶
💡 概念误区：混淆 LICQ、MFCQ、Slater 的适用范围 - LICQ（线性独立约束品性）和 MFCQ 是**一般 NLP** 的约束品性（Nocedal-Wright 语境） - Slater 是**凸问题专用**的约束品性 - 对凸问题：Slater \(\approx\) MFCQ（不含等式约束时等价） - LICQ 比 Slater 更强且对凸问题不自然
约束品性条件的完整体系 ⭐⭐⭐¶
不同类型的优化问题需要不同的约束品性条件来保证 KKT 的必要性和强对偶。
| 约束品性 | 适用范围 | 条件内容 | 强度 |
|---|---|---|---|
| Slater | 凸优化 | 存在严格可行点 | 最弱（凸问题专用） |
| LICQ | 一般 NLP | active 约束梯度线性无关 | 较强 |
| MFCQ | 一般 NLP | active 不等式梯度正线性组合 + 等式梯度满秩 | 中等 |
| ACQ | 一般 NLP | 线性化锥等于切锥 | 最弱的 CQ（但难验证） |
| SC | 一般 NLP | 约束函数在最优解附近的曲率条件 | 用于二阶条件 |
对凸问题的简化： - 只有不等式约束：Slater = 存在 \(\bar{x}\) 使 \(f_i(\bar{x}) < 0\)（\(\forall i\)） - 仿射不等式 + 一般凸不等式：仿射约束只需 \(\leq\)，凸约束需要 \(<\)（sharpened Slater） - 只有仿射约束：不需要 Slater，只要可行域非空就有强对偶
反事实推理：如果不检查约束品性会怎样？ - 可能写出 KKT 条件但找不到满足 KKT 的点（因为 KKT 需要 CQ 作为必要条件的前提） - 可能在求解器中得到"primal infeasible"的错误报告（实际上是 CQ 失败，不是真的不可行） - 可能得到不正确的影子价格（对偶变量在 CQ 失败时可能不是唯一的或不存在的）
练习¶
- 验证 LP \(\min c^\top x\) s.t. \(Ax \leq b, Cx = d\) 的 Slater 条件等价于什么（答案：可行域有相对内部点）。
- 构造一个满足 Slater 条件的 SOCP，并验证强对偶成立。
- 解释为什么"凸问题 + 仿射约束"不需要 Slater 即有强对偶（sharpened Slater）。
- 构造一个不满足 LICQ 但满足 Slater 的例子（提示：两个约束在最优解处的梯度方向相同）。
3.5 KKT 条件 ⭐⭐¶
动机¶
KKT 条件是约束优化的"终极检验"——满足 KKT 的点就是最优解（在适当条件下）。MPC 求解器（OSQP/qpOASES）的终止条件就是 KKT 残差足够小。
KKT 四组件¶
定理 3.5.1（KKT 条件）：设原问题是凸的且满足 Slater 条件。\(x^*\) 是最优解，\((\lambda^*, \nu^*)\) 是对偶最优解，当且仅当以下四组条件同时成立：
1. 原始可行性（Primal feasibility）： $\(f_i(x^*) \leq 0, \quad h_j(x^*) = 0\)$
2. 对偶可行性（Dual feasibility）： $\(\lambda_i^* \geq 0\)$
3. 互补松弛（Complementary slackness）： $\(\lambda_i^* f_i(x^*) = 0, \quad \forall i\)$
4. 稳定性 / 梯度条件（Stationarity）： $\(\nabla f_0(x^*) + \sum_i \lambda_i^* \nabla f_i(x^*) + \sum_j \nu_j^* \nabla h_j(x^*) = 0\)$
即 \(0 \in \partial_{x} L(x^*, \lambda^*, \nu^*)\)。
各条件的直觉¶
**互补松弛**的含义：对每个不等式约束，要么约束是 active 的（\(f_i(x^*) = 0\)），要么其对偶变量为零（\(\lambda_i^* = 0\)）。
经济学解释：如果资源没有用尽（\(f_i(x^*) < 0\)），那么这个约束"不值钱"（\(\lambda_i^* = 0\)）。只有用尽的资源才有"影子价格"。
**稳定性条件**的几何含义：在最优解处，目标函数的负梯度方向可以表示为 active 约束法向量的锥组合（非负线性组合）。直觉上：如果目标函数的"下降方向"不在约束法锥中，就意味着存在可行下降方向，\(x^*\) 不是最优的。
KKT 在凸问题中的充要性 ⭐⭐¶
定理 3.5.2：对凸问题 + Slater 条件：
证明（充分性）：设 KKT 成立。由稳定性条件，\(x^*\) 最小化 \(L(\cdot, \lambda^*, \nu^*)\)（因为 \(L\) 关于 \(x\) 凸，梯度为零即为全局最小）。
即 \(p^* \geq f_0(x^*)\)。又 \(x^*\) 可行故 \(f_0(x^*) \geq p^*\)。因此 \(f_0(x^*) = p^*\)，\(x^*\) 最优。
证明（必要性）：由强对偶（Slater 保证），\(d^* = p^*\) 且对偶最优被取到。利用 \(g(\lambda^*, \nu^*) = p^* = f_0(x^*)\) 推出 \(x^*\) 最小化 \(L(\cdot, \lambda^*, \nu^*)\)（稳定性），以及互补松弛。
KKT 的必要性完整证明 ⭐⭐⭐¶
定理：设凸问题满足 Slater 条件，\(x^*\) 是最优解。则存在 \((\lambda^*, \nu^*)\) 使 KKT 成立。
证明：
Step 1：由 Slater → 强对偶成立，即 \(d^* = p^*\) 且对偶最优被取到于 \((\lambda^*, \nu^*)\)。
Step 2：由 \(g(\lambda^*, \nu^*) = d^* = p^* = f_0(x^*)\)： $\(\inf_x L(x, \lambda^*, \nu^*) = f_0(x^*)\)$
又 \(L(x^*, \lambda^*, \nu^*) = f_0(x^*) + \sum_i \lambda_i^* f_i(x^*) + \sum_j \nu_j^* h_j(x^*) \leq f_0(x^*)\)
（因为 \(\lambda_i^* \geq 0\), \(f_i(x^*) \leq 0\), \(h_j(x^*) = 0\)）
结合 \(\inf_x L \leq L(x^*)\) 和 \(\inf_x L = f_0(x^*)\)：
因此 \(L(x^*, \lambda^*, \nu^*) = f_0(x^*)\)。
Step 3：从 \(L(x^*, \lambda^*, \nu^*) = f_0(x^*)\) 推出 \(\sum_i \lambda_i^* f_i(x^*) = 0\)。
由 \(\lambda_i^* \geq 0\) 和 \(f_i(x^*) \leq 0\)，每项 \(\lambda_i^* f_i(x^*) \leq 0\)。和为零要求每项为零：\(\lambda_i^* f_i(x^*) = 0\)。
这就是**互补松弛**。
Step 4：由 \(x^*\) 最小化 \(L(\cdot, \lambda^*, \nu^*)\)（因为 \(L(x^*, \lambda^*, \nu^*) = \inf_x L\)），且 \(L\) 关于 \(x\) 凸，由 Fermat 规则：
当所有函数可微时：\(\nabla f_0(x^*) + \sum_i \lambda_i^* \nabla f_i(x^*) + \sum_j \nu_j^* \nabla h_j(x^*) = 0\)。
这就是**稳定性条件**。
小结：原始可行（\(x^*\) 可行）+ 对偶可行（\(\lambda^* \geq 0\)）+ 互补松弛（Step 3）+ 稳定性（Step 4）= KKT。
敏感性分析：对偶变量 = 影子价格 ⭐⭐¶
定理 3.5.3（敏感性定理）：设原问题的最优值为 \(p^*(u)\)，其中 \(u_i\) 是约束的松弛量（\(f_i(x) \leq u_i\)）。若强对偶成立：
完整证明：
考虑扰动问题：\(p^*(u) = \inf \{f_0(x) : f_i(x) \leq u_i, h_j(x) = 0\}\)。
由强对偶：\(p^*(u) = \sup_{\lambda \geq 0, \nu} \inf_x [f_0(x) + \sum_i \lambda_i(f_i(x) - u_i) + \sum_j \nu_j h_j(x)]\)
\(= \sup_{\lambda \geq 0, \nu} [g(\lambda, \nu) - \lambda^\top u]\)
其中 \(g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)\) 是原始（\(u=0\)时）的对偶函数。
因此 \(p^*(u) = \sup_{\lambda \geq 0, \nu} [g(\lambda, \nu) - \lambda^\top u]\)。
这是一族仿射函数 \(g(\lambda,\nu) - \lambda^\top u\)（关于 \(u\) 仿射）的 supremum，故 \(p^*(u)\) 是 \(u\) 的**凸函数**！
关键步骤：由 \(p^*(u)\) 凸且在 \(u=0\) 有次梯度 \(-\lambda^* \in \partial p^*(0)\)：
\(p^*(u) \geq p^*(0) + (-\lambda^*)^\top u = p^* - \lambda^{*\top} u\)
即 \(p^*(u) \geq p^* - \lambda^{*\top} u\)。这正是影子价格的含义：放松第 \(i\) 个约束 \(u_i\) 个单位，最优值至多下降 \(\lambda_i^*\) 个单位。
含义：第 \(i\) 个约束的对偶变量 \(\lambda_i^*\) 等于该约束松弛一个单位时，最优值的改善量。
反事实推理：如果不做敏感性分析会怎样？你可能会花大量时间调试一个"不活跃"的约束（\(\lambda_i^* = 0\)），而忽略了真正限制性能的约束（\(\lambda_i^*\) 很大）。对偶变量就是一个"约束重要性排名"。
MPC 中的应用：在 MPC-QP 中，约束的对偶变量告诉你"哪个约束最紧、放松它能获得多大性能提升"。这对调试和约束软化设计非常有用。
数值例子：考虑 \(\min x_1^2 + x_2^2\) s.t. \(x_1 + x_2 \leq 1\)，\(x_1 \leq 0.3\)。
完整求解过程：
假设两个约束都 active：\(x_1 + x_2 = 1\)，\(x_1 = 0.3\)。
则 \(x_1 = 0.3\)，\(x_2 = 0.7\)，\(f = 0.09 + 0.49 = 0.58\)。
KKT 稳定性：\(2x_1 + \lambda_1 + \lambda_2 = 0\) → \(0.6 + \lambda_1 + \lambda_2 = 0\) \(2x_2 + \lambda_1 = 0\) → \(1.4 + \lambda_1 = 0\) → \(\lambda_1 = -1.4\)
但 \(\lambda_1 \geq 0\) 要求不满足！重新检查约束方向。
实际上约束写为 \(x_1 + x_2 - 1 \leq 0\) 和 \(x_1 - 0.3 \leq 0\)。
KKT 稳定性：\(2x_1 + \lambda_1 + \lambda_2 = 0\)，\(2x_2 + \lambda_1 = 0\)
\(\lambda_1 = -2x_2 = -1.4\)... 仍然是负的。
这说明无约束最优解 \(x^* = (0, 0)\) 在可行域内（\(0 + 0 = 0 \leq 1\)，\(0 \leq 0.3\)），因此所有约束都 inactive，\(\lambda_1^* = \lambda_2^* = 0\)，\(x^* = (0, 0)\)，\(p^* = 0\)。
修正例子：\(\min (x_1-1)^2 + (x_2-1)^2\) s.t. \(x_1 + x_2 \leq 1\)，\(x_1 \leq 0.3\)。
无约束最优 \((1, 1)\) 不可行。假设第一个约束 active：\(x_1+x_2=1\)，第二个 inactive。
KKT：\(2(x_1-1) + \lambda_1 = 0\)，\(2(x_2-1) + \lambda_1 = 0\) → \(x_1 = x_2 = 1 - \lambda_1/2\)
\(x_1+x_2 = 1\) → \(2-\lambda_1 = 1\) → \(\lambda_1 = 1\)，\(x^* = (0.5, 0.5)\)。
检查第二个约束：\(x_1 = 0.5 > 0.3\) → 第二个约束也 active！
假设两个都 active：\(x_1 = 0.3\)，\(x_2 = 0.7\)。
KKT：\(2(0.3-1) + \lambda_1 + \lambda_2 = 0\) → \(-1.4 + \lambda_1 + \lambda_2 = 0\) \(2(0.7-1) + \lambda_1 = 0\) → \(-0.6 + \lambda_1 = 0\) → \(\lambda_1 = 0.6\)，\(\lambda_2 = 0.8\)。
\(\lambda_1 = 0.6 \geq 0\)，\(\lambda_2 = 0.8 \geq 0\) ✓。\(p^* = 0.49 + 0.09 = 0.58\)。
影子价格解释：\(\lambda_1^* = 0.6\)：放松 \(x_1+x_2 \leq 1\) 到 \(\leq 1.01\)，最优值改善约 \(0.006\)。\(\lambda_2^* = 0.8\)：放松 \(x_1 \leq 0.3\) 到 \(\leq 0.31\)，最优值改善约 \(0.008\)。第二个约束更"有价值"——应该优先考虑放松 \(x_1\) 的上界。
⚠️ 常见陷阱¶
💡 概念误区：把 KKT 当作万能充分条件 - 非凸问题的 KKT 点可能是局部极大、鞍点或伪最优 - KKT 作为**充分条件**只在凸问题中成立 - KKT 作为**必要条件**需要约束品性（LICQ/MFCQ/Slater） - CBF-QP 是凸的所以 KKT 充分，但一般 NMPC 的 SQP 内层只满足必要
⚠️ 编程陷阱：对偶变量的符号约定 - 不等式约束 \(f_i(x) \leq 0\) 的对偶变量 \(\lambda_i \geq 0\) - 等式约束 \(h_j(x) = 0\) 的对偶变量 \(\nu_j\) 无符号约束 - 不同教材/求解器的符号约定可能不同（有的定义 \(L = f_0 - \sum \lambda_i f_i\)） - 使用求解器时务必对照文档确认符号
练习¶
- 对 \(\min x_1^2 + x_2^2\) s.t. \(x_1 + x_2 \geq 1\)，写出 KKT 条件并求解。
- 对 OSQP 格式的 QP \(\min \frac{1}{2}x^\top Px + q^\top x\) s.t. \(l \leq Ax \leq u\)，写出完整的 KKT 系统。
- （敏感性分析）对上述 QP，解释为什么 OSQP 返回的对偶变量 \(y\) 可以用来判断"哪个约束最值得放松"。
3.6 SDP 对偶与锥对偶 ⭐⭐⭐¶
动机¶
SDP 是机器人学研究前沿中越来越重要的工具。Certifiable SLAM、LMI 控制综合、SOS 多项式验证——都需要 SDP 及其对偶理论。
SDP 的原对偶对¶
原问题： $\(\min \langle C, X \rangle \quad \text{s.t. } \langle A_i, X \rangle = b_i, \; X \succeq 0\)$
对偶问题： $\(\max b^\top y \quad \text{s.t. } C - \sum_i y_i A_i \succeq 0\)$
等价地写为：\(\max b^\top y\) s.t. \(S = C - \sum_i y_i A_i \succeq 0\)（\(S\) 是对偶松弛变量）。
SDP 强对偶条件¶
定理 3.6.1（SDP 的 Slater 条件）：若存在严格可行的 \(\tilde{X} \succ 0\)（正定，不仅半正定）满足 \(\langle A_i, \tilde{X} \rangle = b_i\)，则强对偶成立。
注意：SDP 的强对偶比 LP 微妙。SDP 可以有有限正对偶间隙（Ramana 经典例子），而 LP 只要一方可行有界就有强对偶。
机器人应用：SE-Sync 的对偶证书 ⭐⭐⭐¶
SE-Sync（Rosen-Carlone 2019）把 3D SLAM 的旋转同步问题写成 QCQP：
这是非凸的（正交约束）。通过 Shor 松弛，把 \(X = RR^\top\) 替代，得到 SDP：
对偶证书：若 SDP 松弛是 tight 的（松弛最优解的秩等于 3），则对偶变量 \(\Lambda^*\) 满足 \(M(\Lambda^*) = Q - \sum_i \Lambda_i^* \otimes E_{ii} \succeq 0\)——这就是全局最优证书。
直觉：对偶 PSD 条件 \(M(\Lambda^*) \succeq 0\) 的物理含义是"不存在使目标更小的可行方向"——这正是全局最优性的数学表达。
SE-Sync 的工程实现要点 ⭐⭐⭐¶
为什么 SE-Sync 能在大规模 SLAM 中工作：
-
不直接解 SDP：SE-Sync 不用 MOSEK/SCS 解 SDP（太慢）。它用 Riemannian optimization 在低秩流形上搜索，等价于解松弛问题的低秩版本。
-
Riemannian Staircase：从秩 \(p = d\)（\(d\) 是旋转维度，3D 时 \(d=3\)）开始搜索。如果找到的解满足 \(M(\Lambda^*) \succeq 0\)，则是全局最优。否则增加 \(p\)，重新搜索。
-
Certifiable by construction：每次找到解后，自动计算对偶证书。如果证书通过（\(M \succeq 0\)，检查最小特征值 \(\geq 0\)），保证全局最优。
-
实际表现：在标准 SLAM 数据集上，SE-Sync 的 SDP 松弛几乎总是 tight（即使有中等噪声）。只有极端噪声下才需要增大秩。
Certifiable perception 的一般框架：
与传统方法的对比：
| 方法 | 全局最优保证 | 速度 | 适用场景 |
|---|---|---|---|
| Gauss-Newton (g2o/GTSAM) | 否（局部最优） | 最快 | 良好初始化 |
| 分支定界 | 是 | 极慢（指数） | 小规模 |
| SE-Sync | 是（多项式 + 证书） | 中等 | SLAM 后端 |
| TEASER++ | 是（certifiable） | 快 | 点云配准 |
| GNC | 近似（continuation） | 快 | 鲁棒估计 |
SDP 的数值注意事项：
- \(n > 200\) 时标准 IPM（MOSEK）很慢。替代方案：SCS（一阶 ADMM 方法），或 Riemannian methods
- 低秩最优解的提取需要截断 SVD：\(X^* = UDV^\top\)，取前 \(d\) 个奇异值对应的列
- 松弛 tight 的判据：\(\sigma_{d+1}(X^*) / \sigma_d(X^*) \ll 1\)（第 \(d+1\) 个奇异值远小于第 \(d\) 个）
Schur 互补与 LMI ⭐⭐¶
引理 3.6.2（Schur 互补）：对分块矩阵 \(M = \begin{pmatrix} A & B \\ B^\top & C \end{pmatrix}\)：
当 \(A \succ 0\) 时简化为：\(M \succeq 0 \Leftrightarrow C - B^\top A^{-1} B \succeq 0\)。
Schur 互补的完整证明（\(A \succ 0\) 情形）：
\((\Rightarrow)\)：设 \(M \succeq 0\)。取 \(v = \begin{pmatrix}-A^{-1}Bw \\ w\end{pmatrix}\)：
由 \(M \succeq 0\)，\(v^\top Mv \geq 0\) 对所有 \(w\)，故 \(C - B^\top A^{-1}B \succeq 0\)。
\((\Leftarrow)\)：令 \(S = C - B^\top A^{-1}B \succeq 0\)。分解： $\(M = \begin{pmatrix}I & 0 \\ B^\top A^{-1} & I\end{pmatrix}\begin{pmatrix}A & 0 \\ 0 & S\end{pmatrix}\begin{pmatrix}I & A^{-1}B \\ 0 & I\end{pmatrix}\)$
由 \(A \succ 0\) 和 \(S \succeq 0\)，中间的块对角矩阵 PSD，故 \(M \succeq 0\)。
应用 1：Lyapunov 稳定性。闭环系统 \(\dot{x} = (A+BK)x\) 稳定 \(\Leftrightarrow\) 存在 \(P \succ 0\) 使 \((A+BK)^\top P + P(A+BK) \prec 0\)。
直接优化 \((K, P)\) 是双线性的（非凸）。但令 \(Y = KP^{-1}\)，\(Q = P^{-1}\)，通过 Schur 互补和换元，可以转化为关于 \((Q, Y)\) 的 LMI → SDP。
应用 2：鲁棒控制。参数不确定的系统 \(A(\delta)\)（\(\delta\) 在某集合中），要求所有 \(\delta\) 下 Lyapunov 稳定 → 多个 LMI 同时满足 → SDP。
应用 3：SOCP → SDP 的转化。\(\|Ax+b\| \leq c^\top x + d\) 通过 Schur 互补写成： $\(\begin{pmatrix}(c^\top x + d)I & Ax+b \\ (Ax+b)^\top & c^\top x + d\end{pmatrix} \succeq 0\)$
这证明了 SOCP \(\subset\) SDP。
SDP 对偶的推导 ⭐⭐⭐¶
让我们从 Lagrangian 角度完整推导 SDP 的对偶。
原问题：\(\min \langle C, X \rangle\) s.t. \(\langle A_i, X \rangle = b_i\), \(X \succeq 0\)。
Step 1：把 \(X \succeq 0\) 写成无穷多不等式：\(v^\top X v \geq 0\), \(\forall v\)。但更自然的方式是用锥对偶。
Step 2：Lagrangian（锥规划形式）： $\(L(X, y, S) = \langle C, X \rangle + \sum_i y_i(b_i - \langle A_i, X \rangle) - \langle S, X \rangle\)$
其中 \(S \succeq 0\) 是对偶松弛矩阵（对应 \(X \succeq 0\) 的约束）。
Step 3：对偶函数 \(g(y, S) = \inf_{X} L(X, y, S)\)。
若 \(C - \sum_i y_i A_i - S \neq 0\)，取 \(X\) 沿着使 \(\langle C - \sum_i y_i A_i - S, X \rangle\) 趋于 \(-\infty\) 的方向，得 \(g = -\infty\)。
若 \(C - \sum_i y_i A_i - S = 0\)（即 \(S = C - \sum_i y_i A_i\)），得 \(g(y, S) = b^\top y\)。
Step 4：对偶问题 \(\max b^\top y\) s.t. \(S = C - \sum_i y_i A_i \succeq 0\)。
即 \(\max b^\top y\) s.t. \(C - \sum_i y_i A_i \succeq 0\)。
对偶互补松弛：\(\langle S, X \rangle = \text{tr}(SX) = 0\)，其中 \(S, X \succeq 0\)。
由 \(S, X \succeq 0\) 且 \(\text{tr}(SX) = 0\) 推出 \(SX = 0\)——这是 SDP 的互补松弛条件。
几何含义：\(S\) 和 \(X\) 的列空间互补——\(X\) 的列空间在 \(S\) 的零空间中，\(S\) 的列空间在 \(X\) 的零空间中。这与 LP 的互补松弛（\(\lambda_i x_i = 0\)）是同一思想的矩阵推广。
⚠️ 常见陷阱¶
💡 概念误区：以为"SDP 松弛总是 tight" - 噪声足够大时松弛会松（最优解秩 > 3） - 此时需要 Riemannian Staircase 增大秩 \(p\) 或局部搜索 - Tightness 的判定就是检查对偶 PSD 证书 \(M(\Lambda^*) \succeq 0\)
SDP 强对偶失败的经典反例 ⭐⭐⭐⭐¶
Ramana 的例子：
原问题： $\(\min X_{11} \quad \text{s.t.} \quad X = \begin{pmatrix} x_{11} & x_{12} \\ x_{12} & 0 \end{pmatrix} \succeq 0\)$
\(X \succeq 0\) 且 \(X_{22} = 0\) 要求 \(X_{12} = 0\)（否则 \(\det X < 0\)）。因此可行域是 \(X = \text{diag}(x_{11}, 0)\)，\(x_{11} \geq 0\)。
\(p^* = 0\)（\(X = 0\)）。
对偶问题：\(\max 0 \cdot y\) s.t. \(\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} - y\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \succeq 0\)
即 \(\begin{pmatrix} 1 & 0 \\ 0 & -y \end{pmatrix} \succeq 0\)，需要 \(y \leq 0\)。
\(d^* = 0\)... 实际上这个例子没有间隙。更精细的 Ramana 例子需要 3x3 矩阵。
要点：SDP 的强对偶比 LP 微妙。LP 只要原/对偶任一可行有界就有强对偶。SDP 的 Slater 条件需要**严格**可行（\(X \succ 0\)，不仅是 \(X \succeq 0\)）。如果可行域"退化"到半正定锥的边界（如上例中 \(X_{22} = 0\)），Slater 可能不满足。
SDP 在 LMI 控制综合中的应用 ⭐⭐⭐¶
问题：设计状态反馈控制器 \(u = Kx\) 使闭环系统 \(\dot{x} = (A+BK)x\) 稳定。
Lyapunov 方法：存在 \(P \succ 0\) 使 \((A+BK)^\top P + P(A+BK) \prec 0\)。
困难：这是关于 \((P, K)\) 的双线性矩阵不等式（BMI），不是 LMI。
变量替换：令 \(Q = P^{-1}\)，\(Y = KQ\)。原条件变为： $\(QA^\top + AQ + Y^\top B^\top + BY \prec 0, \quad Q \succ 0\)$
这是关于 \((Q, Y)\) 的 LMI！可以用 SDP 求解。解出后 \(K = YQ^{-1}\)。
为什么这很重要：通过巧妙的变量替换，非凸的控制器设计问题变成了凸的 SDP——这使得最优控制器可以在**全局**意义上计算（不依赖初始猜测）。
\(H_\infty\) 控制综合：更复杂的鲁棒控制问题（如 \(H_\infty\) 控制）也可以写成 LMI/SDP。这是 LMI 控制综合（1990s Scherer, Boyd 等人的工作）的核心思想——把控制器设计"统一"为 SDP。
练习¶
- 对 2D 旋转同步（3 个节点，2 条边），列出 QCQP、其 SDP 松弛，并用 CVXPY + SCS 求解。检查松弛是否 tight（\(\text{rank}(X^*) = 2\)）。
- 写出 Lyapunov 稳定性 LMI \(A^\top P + PA \prec 0, P \succ 0\) 的 SDP 对偶。
- 构造一个 SDP 使 Slater 条件不满足，并验证是否存在正对偶间隙。
- 对 \(A = \begin{pmatrix} 0 & 1 \\ -2 & -3 \end{pmatrix}\)，\(B = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\)，用 LMI 方法设计状态反馈 \(K\)。用 CVXPY 求解并验证闭环稳定性（特征值在左半平面）。
- 比较 LMI 设计的控制器与 LQR 设计的控制器——它们是否相同？解释原因。
3.7 互补松弛与 Active-Set 方法 ⭐⭐¶
动机¶
互补松弛 \(\lambda_i^* f_i(x^*) = 0\) 不仅是理论条件——它是 active-set 方法（如 qpOASES）的算法基础。理解互补松弛的几何含义能让你更好地调试 MPC 系统。
互补松弛的几何含义 ⭐⭐¶
互补松弛 \(\lambda_i^* f_i(x^*) = 0\) 等价于：对每个约束，要么约束是 active 的（\(f_i = 0\)），要么其"价格"为零（\(\lambda_i = 0\)）。
经济学解释（加深版）： - 约束 active（\(f_i = 0\)）：资源完全用尽。价格 \(\lambda_i > 0\) 反映了额外一单位资源的边际价值。 - 约束 inactive（\(f_i < 0\)）：资源有剩余。价格 \(\lambda_i = 0\)，因为资源不稀缺，多给一些不会改善目标。
几何解释：在最优解 \(x^*\) 处，目标函数的负梯度 \(-\nabla f_0(x^*)\) 必须在 active 约束法向量的锥组合中： $\(-\nabla f_0(x^*) = \sum_{i \in \mathcal{A}} \lambda_i^* \nabla f_i(x^*)\)$
只有 active 约束"参与"了这个分解——inactive 约束的法向量不出现（因为 \(\lambda_i = 0\)）。
反事实推理：如果一个 inactive 约束的 \(\lambda_i > 0\) 会怎样？这意味着我们在一个不紧的约束上"浪费"了对偶资源——把这个 \(\lambda_i\) 设为零并重新分配给 active 约束，可以得到更好的下界。矛盾。
Active set 的概念¶
定义 3.7.1：在最优解 \(x^*\) 处，约束 \(f_i(x^*) = 0\) 的下标集合 \(\mathcal{A}(x^*) = \{i \mid f_i(x^*) = 0\}\) 称为 active set。
由互补松弛：\(\lambda_i^* > 0 \Rightarrow f_i(x^*) = 0\)（约束 active）。
反过来不成立：\(f_i(x^*) = 0\) 不要求 \(\lambda_i^* > 0\)。\(f_i = 0\) 且 \(\lambda_i = 0\) 的约束称为**退化约束**——它恰好 active 但"不贡献"。退化是数值方法的主要困难来源之一。
Active-set 方法的完整流程 ⭐⭐¶
算法（Active-Set QP Solver）：
初始化: 选择可行点 x_0 和初始工作集 W_0 (W_0 是 {1,...,m} 的子集)
for k = 0, 1, 2, ...:
1. 解等式约束子问题:
min (1/2)*d'*P*d + (P*x_k + q)'*d
s.t. a_i'*d = 0, i in W_k
得到搜索方向 d_k 和对偶变量 lambda_k
2. if d_k = 0: # 当前工作集下已最优
if all lambda_i >= 0 for i in W_k:
STOP: x_k 是最优解
else:
找 j = argmin_{i in W_k} lambda_i
W_{k+1} = W_k \ {j} # 移除最负的乘子对应的约束
3. else: # d_k != 0, 沿 d_k 方向走
计算最大步长 alpha_max = min_{i not in W_k, a_i'*d_k>0} (b_i - a_i'*x_k)/(a_i'*d_k)
x_{k+1} = x_k + alpha_k * d_k
if 某个约束变 active:
W_{k+1} = W_k union {该约束}
复杂度：最坏情况指数（组合爆炸），但实际中通常多项式。warm-start 时每步只需 1-3 次 pivoting。
在 MPC 中的应用：qpOASES 用 active-set 方法解参数化 QP，利用上一时步的 active set 作为热启动——这使得连续 MPC 循环中每步只需要少量 pivoting 操作（微秒级）。
Active-Set vs Interior-Point vs ADMM 的对比¶
| 特征 | Active-Set (qpOASES) | Interior-Point (HPIPM) | ADMM (OSQP) |
|---|---|---|---|
| 每步复杂度 | 低（rank-1 更新） | 中（Cholesky 分解） | 低（矩阵-向量乘） |
| warm-start | 极好（连续 QP） | 差（新初始点） | 好（迭代初始化） |
| 精度 | 机器精度 | 机器精度 | 中等（需 polishing） |
| 大规模 | 差（>1000 变量） | 好（利用结构） | 最好（稀疏性） |
| 嵌入式 | 可以 | 困难 | 最适合 |
| 适用场景 | 小规模参数化 QP | 大规模 MPC (acados) | 通用 MPC |
与 LP 的关系¶
LP 中：最优解在多面体顶点取到 \(\Leftrightarrow\) 恰好有 \(n\) 个 active 约束 \(\Leftrightarrow\) 对偶可行基本解。
单纯形法就是在顶点之间"行走"，每步改变 active set 中的一个约束。
本质洞察：互补松弛不只是一个"条件"——它编码了最优解的**组合结构**。知道 active set 等价于知道最优解——这就是为什么猜对 active set 的 active-set 方法在热启动下极快（只需验证和微调），而 interior-point 方法从"内部"逼近无法利用这种组合结构。
练习¶
- 对 \(\min (x-2)^2\) s.t. \(x \geq 0, x \leq 1\)，确定 active set 和 KKT 点。计算对偶变量并验证互补松弛。
- 解释为什么 qpOASES 在参数化 MPC 中比 OSQP 更快（提示：warm-start + active set 连续变化）。
- 对 \(\min x_1^2 + x_2^2\) s.t. \(x_1 \geq 0, x_2 \geq 0, x_1 + x_2 \leq 1\)，画出可行域，标出最优解，确定 active set，验证 KKT 的所有四个条件。
- 构造一个退化的 QP 例子（某个 active 约束的 \(\lambda^* = 0\)），解释这对 active-set 方法造成什么困难。
3.8 Fenchel 对偶与 Lagrange 对偶的统一 ⭐⭐⭐¶
动机¶
前面共轭函数章节介绍了 Fenchel 对偶（\(\inf[f(x) + g(Ax)]\) 的对偶是 \(\sup[-f^*(-A^\top y) - g^*(y)]\)），本章介绍了 Lagrange 对偶。它们是什么关系？
统一视角¶
Lagrange 对偶是 Fenchel 对偶的特例。考虑约束问题 \(\min f_0(x)\) s.t. \(f_i(x) \leq 0\)。
将约束写成指示函数：\(\min f_0(x) + \sum_i \delta_{\{t \leq 0\}}(f_i(x))\)。
这是 \(\min [f_0(x) + g(F(x))]\) 的形式，其中 \(F(x) = (f_1(x), ..., f_m(x))\)，\(g = \sum_i \delta_{(-\infty, 0]}\)。
\(g\) 的共轭：\(g^*(\lambda) = \sup_u [\lambda^\top u - g(u)] = \sup_{u \leq 0} \lambda^\top u = \begin{cases} 0 & \lambda \geq 0 \\ +\infty & \text{otherwise} \end{cases} = \delta_{\mathbb{R}^m_+}(\lambda)\)
Fenchel 对偶：\(\sup_{\lambda \geq 0} [-f_0^*(-\text{something}) - 0]\)...
更精确地说：Lagrange 对偶可以从 Fenchel 对偶框架通过 perturbation function 推导。Rockafellar §31 给出了这个统一。
核心等价：在适当条件下，Lagrange 对偶和 Fenchel 对偶给出相同的对偶问题和相同的强对偶条件。
为什么这个统一重要¶
- 它解释了为什么 ADMM（基于 Fenchel 对偶分解）和 Lagrange 松弛方法等价
- 它让你能在两种语言之间自由切换——遇到结构化问题用 Fenchel，遇到一般约束用 Lagrange
- 它是 proximal splitting 算法理论的最终统一框架
从统一视角看 MPC 求解¶
回顾：MPC 每步解 QP：\(\min \frac{1}{2}x^\top Px + q^\top x\) s.t. \(l \leq Ax \leq u\)。
Lagrange 视角：引入对偶变量 \(\lambda^+, \lambda^-\)： $\(L = \frac{1}{2}x^\top Px + q^\top x + \lambda^{+\top}(Ax - u) + \lambda^{-\top}(l - Ax)\)$
对偶函数：\(g(\lambda^+, \lambda^-) = \inf_x L = -\frac{1}{2}(q + A^\top(\lambda^+-\lambda^-))^\top P^{-1}(q + A^\top(\lambda^+-\lambda^-)) - u^\top\lambda^+ + l^\top\lambda^-\)
Fenchel 视角：写成 \(\min f(x) + g(Ax)\)，\(f(x) = \frac{1}{2}x^\top Px + q^\top x\)，\(g(z) = \delta_{[l,u]}(z)\)。
Fenchel 对偶：\(\max -f^*(-A^\top y) - g^*(y) = \max -\frac{1}{2}(A^\top y - q)^\top P^{-1}(A^\top y - q) - \sigma_{[l,u]}(y)\)。
两者给出同一个对偶问题——证实了统一性。
OSQP 的视角：OSQP 同时维护原始变量 \(x\) 和对偶变量 \(y\)，通过 ADMM 迭代使 KKT 残差趋于零。终止时的 \((x^*, y^*)\) 就是原问题和对偶问题的同时最优解。
本质洞察：三种视角（Lagrange、Fenchel、ADMM）描述的是同一个数学对象。Lagrange 给出了对偶的"经济学"解释，Fenchel 给出了"函数变换"解释，ADMM 给出了"算法"解释。掌握三种语言能让你在不同场景下选择最自然的表述。
练习¶
- 对 LASSO \(\min \frac{1}{2}\|Ax-b\|^2 + \lambda\|x\|_1\)，分别用 Lagrange 对偶和 Fenchel 对偶推导其对偶问题，验证一致性。
- 解释 ADMM 中的 augmented Lagrangian \(L_\rho(x,z,y) = f(x) + g(z) + y^\top(Ax+Bz-c) + \frac{\rho}{2}\|Ax+Bz-c\|^2\) 中各项的对偶含义。
3.9 求解器生态与工程选型 ⭐⭐¶
动机¶
理论告诉我们"问题有解"，但实际把解算出来需要选对求解器。不同场景对速度、精度、可嵌入性的要求不同。
选型决策树¶
问题类型？
├── LP → HiGHS / Gurobi / CPLEX
├── 凸 QP
│ ├── 嵌入式实时（<100 us）→ TinyMPC / DAQP
│ ├── MPC（~1ms）→ OSQP / HPIPM+acados
│ ├── 参数化 warm-start → qpOASES
│ └── 全身控制 → ProxQP
├── SOCP → ECOS / Clarabel
├── SDP
│ ├── 高精度 → MOSEK
│ └── 大规模低精度 → SCS
├── 通用 NLP → Ipopt
└── 原型/教学 → CVXPY（自动选后端）
求解器的内部原理 ⭐⭐¶
理解求解器的内部工作原理有助于选择合适的求解器和调试参数。
Interior-Point Method（内点法） 的核心思想：
把不等式约束 \(f_i(x) \leq 0\) 用对数障碍函数替代： $\(\min f_0(x) - \frac{1}{t}\sum_i \log(-f_i(x))\)$
当 \(t \to \infty\) 时，对数障碍项趋于 \(0\)（可行区域内部）或 \(+\infty\)（约束边界），逼近原问题。
内点法的每步都在可行域**内部**移动（不触碰约束边界），通过逐步增大 \(t\) 来逼近最优解。每步需要解 Newton 系统，复杂度 \(O(n^3)\)。
内点法 vs Active-Set 的本质区别：
| 特征 | 内点法 | Active-Set |
|---|---|---|
| 解的路径 | 从内部逼近边界 | 在边界上移动 |
| 每步复杂度 | \(O(n^3)\)（Newton） | \(O(n^2)\)（rank-1 更新） |
| 总迭代数 | \(O(\sqrt{n})\)（理论） | 视 active set 变化 |
| warm-start | 差 | 极好 |
| 大规模 | 利用结构性稀疏 | 困难 |
为什么 OSQP 选择 ADMM 而不是内点法：
- 嵌入式部署：ADMM 不需要矩阵分解（或只需一次预分解），内存可控
- 中等精度足够：MPC 不需要 \(10^{-12}\) 精度，\(10^{-3}\) 到 \(10^{-6}\) 足够
- warm-start：ADMM 的 warm-start 简单且有效（直接用上步的 \(x, z, u\)）
- 鲁棒性：ADMM 不要求严格可行性，可以检测不可行
OSQP 的对偶视角¶
OSQP 求解 \(\min \frac{1}{2}x^\top P x + q^\top x\) s.t. \(l \leq Ax \leq u\)。
其内部 ADMM 迭代维护原始变量 \(x\) 和对偶变量 \(y\)。终止条件是： - 原残差 \(\|Ax - z\| \leq \epsilon_{\text{pri}}\) - 对偶残差 \(\|P x + q + A^\top y\| \leq \epsilon_{\text{dual}}\)
这正是 KKT 条件的数值逼近。OSQP 还能检测**原不可行**和**对偶不可行**（通过对偶间隙的发散方向）。
⚠️ 常见陷阱¶
⚠️ 编程陷阱：忘记检查求解器精度 - OSQP/SCS 的 ADMM 默认精度 ~1e-3（对嵌入式 MPC 够用） - 对 certifiable SLAM 需要高精度（~1e-8），需要 MOSEK 或开 polishing - 反过来在嵌入式场景，过高精度浪费算力和时间
求解器生态的完整分析 ⭐⭐¶
开源 vs 商业：
| 类别 | 代表 | 优势 | 劣势 |
|---|---|---|---|
| 开源 ADMM | OSQP, SCS | 免费，可嵌入，warm-start | 中等精度 |
| 开源 IPM | ECOS, Clarabel | 高精度，稳定 | 不支持 warm-start |
| 商业 IPM | MOSEK, Gurobi | 最高性能，技术支持 | 付费，学术免费 |
| 嵌入式 | TinyMPC, DAQP | 超小内存，确定性时间 | 问题规模受限 |
| 通用 NLP | Ipopt, SNOPT | 处理非凸，一般约束 | 只保证局部最优 |
CVXPY 的工作原理：
CVXPY 不是求解器——它是一个**建模工具**，把用户的高层描述转换为求解器能理解的标准形式。
工作流程：
1. 用户写 cp.Problem(cp.Minimize(expr), constraints)
2. CVXPY 用 DCP 规则验证凸性
3. CVXPY 把问题编译为标准 cone program（\(\min c^\top x\) s.t. \(Ax + s = b\), \(s \in K\)）
4. 把标准形式传给后端求解器（OSQP/ECOS/MOSEK/SCS）
5. 把求解器的结果解码回用户的变量
DCP（Disciplined Convex Programming）规则：
DCP 是一套组合规则，用于自动验证表达式的凸性：
| 规则 | 条件 | 结论 |
|---|---|---|
| 凸 + 凸 | — | 凸 |
| 凸 * 正常数 | — | 凸 |
| 凸 ∘ 仿射 | — | 凸 |
| 凸不减(凸) | — | 凸 |
| 凸不增(凹) | — | 凸 |
# DCP 能验证的
f1 = cp.norm(A @ x - b) # 凸 ∘ 仿射
f2 = cp.quad_form(x, P) # 凸 atom
f3 = cp.maximum(f1, f2) # max(凸, 凸) = 凸
# DCP 不能验证的（需要手动变换）
# f4 = cp.sqrt(cp.quad_form(x, P)) # DCP 拒绝
f4_equiv = cp.norm(P_sqrt @ x) # 等价但 DCP 接受
为什么 DCP 必要：它把"验证凸性"这个困难问题（一般来说是 NP-hard 的）变成了一个简单的语法检查。代价是 DCP 有时会拒绝实际上凸的表达式——但这种"保守性"保证了通过 DCP 的表达式一定凸。
TinyMPC 与嵌入式 MPC ⭐⭐¶
TinyMPC (2023) 是专为嵌入式系统设计的 MPC 求解器： - 代码量 < 1000 行 C - 内存 < 10 KB（足以放入单片机 SRAM） - 固定迭代次数 → 确定性执行时间 - 基于 ADMM，但针对 MPC 结构做了优化
为什么 MPC 可以做得这么小：MPC-QP 的 Hessian \(P + \rho A^\top A\) 的结构是 band-diagonal 的（由 Riccati 递推产生），可以用 \(O(N n^2)\) 而不是 \(O(N^3 n^3)\) 的复杂度分解（\(N\) 是 horizon，\(n\) 是状态维度）。
CVXPY 实战示例 ⭐⭐¶
import cvxpy as cp
import numpy as np
# 示例 1: Portfolio Optimization (QP)
n = 5 # 资产数
np.random.seed(42)
mu = np.random.randn(n) # 预期收益
Sigma = np.random.randn(n, n)
Sigma = Sigma.T @ Sigma / n # 协方差矩阵
x = cp.Variable(n)
ret = mu @ x
risk = cp.quad_form(x, Sigma)
prob = cp.Problem(
cp.Maximize(ret - 0.5 * risk),
[cp.sum(x) == 1, x >= 0]
)
prob.solve()
print(f"最优组合权重: {x.value}")
print(f"预期收益: {ret.value:.4f}, 风险: {risk.value:.4f}")
# 打印对偶变量（影子价格）
for i, c in enumerate(prob.constraints):
print(f"约束 {i} 的对偶变量: {c.dual_value}")
# 示例 2: SOCP - 摩擦锥约束
f_t = cp.Variable(2) # 切向力
f_n = cp.Variable() # 法向力
mu_fric = 0.5 # 摩擦系数
prob2 = cp.Problem(
cp.Minimize(cp.norm(f_t - np.array([1.0, 0.5]))),
[cp.norm(f_t) <= mu_fric * f_n, f_n >= 0, f_n <= 100]
)
prob2.solve()
print(f"最优接触力: f_t={f_t.value}, f_n={f_n.value}")
练习¶
- 用 CVXPY 求解 Markowitz portfolio 问题，分别指定 OSQP 和 ECOS 作为后端，比较结果精度和求解时间。
- 用 OSQP 的 Python API 直接求解一个 3 变量 QP，打印对偶变量并解释其含义。用影子价格分析找出最紧的约束。
- 比较同一 MPC-QP 在 OSQP（ADMM）和 qpOASES（active-set）下的求解时间。尝试 warm-start 和不 warm-start 两种情况。
- 用 CVXPY 求解一个摩擦锥约束的力分配问题（给定接触点数量和目标扳手），验证 SOCP 约束的正确性。
本章知识地图¶
凸优化问题与对偶理论
├── 问题分类 (§3.1-3.2)
│ ├── 标准形式 → 凸目标 + 凸约束 + 仿射等式
│ ├── Epigraph 变换 → 非光滑 → 光滑
│ └── 六大家族: LP ⊂ QP ⊂ SOCP ⊂ SDP
├── 对偶理论 (§3.3-3.4)
│ ├── Lagrangian → 约束软化
│ ├── 对偶函数 → 永远凹 (inf 保凹)
│ ├── 弱对偶 → g ≤ p* (恒成立)
│ ├── Slater → 强对偶 (分离定理证明)
│ └── 影子价格 → λ* = -∂p*/∂u
├── KKT 条件 (§3.5)
│ ├── 四组件: 可行+对偶可行+互补松弛+稳定性
│ ├── 凸问题充要性 (Slater 条件下)
│ └── 从 Fermat 规则推导 KKT
├── 锥对偶 (§3.6)
│ ├── SDP 原对偶对 → Certifiable SLAM
│ ├── Schur 互补 → LMI 控制综合
│ └── 锥互补松弛 → SX = 0
├── 算法视角 (§3.7-3.8)
│ ├── Active-set → qpOASES / 单纯形
│ ├── Interior-point → MOSEK / HPIPM
│ ├── ADMM → OSQP / SCS
│ └── Fenchel-Lagrange 统一
└── 工程选型 (§3.9)
└── 问题类型 → 求解器选择 → 参数调优
跨章综合练习¶
📝 综合练习（需要三章知识的综合）
-
从凸集到 KKT： 回顾 Ch1 的分离超平面定理。解释为什么 KKT 的稳定性条件 \(\nabla f_0 + \sum \lambda_i \nabla f_i = 0\) 本质上是 epigraph 的分离超平面条件的代数形式。
-
从共轭到对偶问题： 回顾 Ch2 的 Fenchel-Young 不等式。证明弱对偶 \(g(\lambda, \nu) \leq p^*\) 可以直接从 Fenchel-Young 推出（不需要引入 Lagrangian）。
-
完整 MPC-QP 求解链路： 对 \(\min \frac{1}{2}x^\top Px + q^\top x\) s.t. \(l \leq Ax \leq u\)： (a) 识别问题类型（Ch3 §3.2） (b) 写出 KKT 条件（Ch3 §3.5） (c) 写出对偶问题（Ch3 §3.3） (d) 用 ADMM 求解（Ch2 §2.11），写出每步更新 (e) 用 OSQP 的 Python API 实现并验证
-
Certifiable SLAM 的数学链路： (a) 写出旋转同步的 QCQP（Ch3 §3.6） (b) 推导其 SDP 松弛 (c) 写出 SDP 的对偶问题 (d) 解释对偶 PSD 证书的含义 (e) 用 CVXPY + MOSEK 对一个 3 节点的例子求解
-
条件数与算法选择： 回顾 Ch1 的条件数 \(\kappa = L/\mu\)。对 LASSO 的 QP 对偶： (a) 计算对偶问题的条件数 (b) 利用 Ch2 的强凸-光滑对偶，解释为什么原问题（非光滑）的对偶（光滑）更适合梯度法 (c) 选择合适的求解器并解释理由
本章常见误解汇总¶
| 误解 | 正确理解 |
|---|---|
| "对偶问题只有在原问题凸时才有意义" | 对偶函数 \(g(\lambda,\nu)\) 永远是凹的（无论原问题是否凸），对偶下界在非凸问题中也有价值（如 certifiable 算法的最优性证书） |
| "强对偶 = 凸问题" | 凸性不够，还需要约束品性（Slater 条件）。SDP 可以有有限正对偶间隙（Ramana 经典例子）。仿射约束的凸问题不需要 Slater |
| "KKT 条件是万能充分条件" | KKT 作为充分条件只在凸问题中成立；作为必要条件需要约束品性（LICQ/MFCQ/Slater） |
| "LP 的强对偶和 SDP 的强对偶条件相同" | LP 只要一方可行有界就有强对偶；SDP 需要严格可行（Slater），否则可能有有限正对偶间隙 |
| "SOCP 比 QP 严格更难" | 从理论包含关系看 QP \(\subset\) SOCP，但 SOCP 的自对偶性使其理论特别干净，且在摩擦锥约束等场景中是自然建模选择 |
| "影子价格 \(\lambda_i^*\) 只是理论概念" | 影子价格直接告诉工程师"哪个约束最值得放松"，在 MPC 调参和约束软化设计中非常实用 |
| "Lagrange 对偶和 Fenchel 对偶是两套不同的理论" | Lagrange 对偶是 Fenchel 对偶框架的特例（通过 perturbation function），两者在适当条件下给出相同的对偶问题 |
| "内点法比 ADMM 更好（或反之）" | 没有"更好"之说，只有"更适合"：中小规模高精度选 IPM，大规模中精度选 ADMM，参数化 warm-start 选 active-set |
本章小结¶
| 概念 | 核心陈述 | 难度 | 关键应用 |
|---|---|---|---|
| 凸问题标准形式 | \(\min f_0\) s.t. \(f_i \leq 0\), \(h_j = 0\) | ⭐ | 问题识别 |
| 六大家族 | LP⊂QP⊂SOCP⊂SDP | ⭐⭐ | 求解器选型 |
| Lagrangian | \(L = f_0 + \sum\lambda_i f_i + \sum\nu_j h_j\) | ⭐⭐ | 对偶构造 |
| 弱对偶 | \(g(\lambda,\nu) \leq p^*\) 恒成立 | ⭐⭐ | 下界/证书 |
| Slater + 强对偶 | 严格可行 → \(d^* = p^*\) | ⭐⭐ | KKT 充要性前提 |
| KKT 四组件 | 可行+对偶可行+互补松弛+稳定性 | ⭐⭐ | 求解器终止条件 |
| 影子价格 | \(\lambda_i^* = -\partial p^*/\partial u_i\) | ⭐⭐ | 敏感性分析 |
| SDP 对偶 | \(\max b^\top y\) s.t. \(C-\sum y_iA_i \succeq 0\) | ⭐⭐⭐ | Certifiable SLAM |
| 对偶证书 | \(M(\Lambda^*) \succeq 0\) → 全局最优 | ⭐⭐⭐ | SE-Sync |
| Fenchel-Lagrange 统一 | Lagrange 是 Fenchel 的特例 | ⭐⭐⭐ | ADMM 理论 |
| 锥规划统一 | LP ⊂ QP ⊂ SOCP ⊂ SDP ⊂ Conic LP | ⭐⭐ | 求解器选型 |
| Active-set | 猜 active 约束 → 解等式 QP | ⭐⭐ | qpOASES / 微秒级 |
| Interior-point | 对数障碍 + Newton | ⭐⭐⭐ | MOSEK / HPIPM |
| ADMM for QP | \(x\)-步(线性系统) + \(z\)-步(box投影) | ⭐⭐ | OSQP |
| KKT 线性系统 | 鞍点系统 / Riccati 递推 | ⭐⭐ | MPC 结构利用 |
| Certifiable perception | SDP 松弛 + 对偶证书 | ⭐⭐⭐ | SE-Sync / TEASER |
| Pontryagin 最大原理 | 连续时间 KKT | ⭐⭐⭐ | DDP / 轨迹优化 |
| DCP 规则 | 自动凸性验证 | ⭐⭐ | CVXPY 建模 |
累积项目：本章新增模块¶
项目：对偶理论验证工具 & MPC-QP 求解器对比
本章新增： - 用 CVXPY 验证强对偶（比较 primal 和 dual value） - 实现 KKT 残差检验（稳定性 + 原可行 + 对偶可行 + 互补松弛） - 实现影子价格分析（约束松弛的敏感性） - 对 MPC-QP 比较三种求解器（OSQP / qpOASES / CVXPY） - 实现简单的 SDP 松弛（2D 旋转同步的 toy example）
import cvxpy as cp
import numpy as np
def verify_strong_duality(problem):
"""验证 CVXPY 问题的强对偶"""
problem.solve()
primal_val = problem.value
# CVXPY 自动计算对偶值
# 对偶间隙应接近零
print(f"Primal value: {primal_val:.6f}")
for constr in problem.constraints:
print(f" Dual variable: {constr.dual_value}")
return primal_val
def kkt_residual(P, q, A, l, u, x, y):
"""计算 OSQP 格式 QP 的 KKT 残差"""
# 稳定性：Px + q + A'y = 0
stationarity = np.linalg.norm(P @ x + q + A.T @ y)
# 原可行性：l <= Ax <= u
Ax = A @ x
primal_feas = np.linalg.norm(
np.maximum(l - Ax, 0) + np.maximum(Ax - u, 0)
)
# 对偶可行性（隐含在 y 的符号中）
# 互补松弛：y_i * (Ax - u)_i = 0 和 y_i * (l - Ax)_i = 0
comp_slack_upper = np.linalg.norm(
np.maximum(y, 0) * (Ax - u)
)
comp_slack_lower = np.linalg.norm(
np.minimum(y, 0) * (l - Ax)
)
return stationarity, primal_feas, comp_slack_upper + comp_slack_lower
def shadow_price_analysis(problem, constraints, delta=1e-4):
"""敏感性分析：估计每个约束的影子价格"""
# 解原问题
problem.solve()
p_star = problem.value
print(f"原问题最优值: {p_star:.6f}")
# 对每个约束做微扰
for i, constr in enumerate(constraints):
dual_val = constr.dual_value
print(f" 约束 {i}: 对偶变量 = {dual_val}")
print(f" 含义: 放松此约束 delta 个单位, 最优值改善约 {np.abs(dual_val)*delta:.6f}")
def solve_rotation_sync_sdp(R_measurements, edges, n_nodes=3):
"""2D 旋转同步的 SDP 松弛（toy example）"""
n = n_nodes
# 决策变量: X (2n x 2n) PSD 矩阵
X = cp.Variable((2*n, 2*n), symmetric=True)
# 目标: min tr(Q @ X) (Q 由测量值构成)
Q = np.zeros((2*n, 2*n))
for (i, j), R_ij in zip(edges, R_measurements):
# 贡献 ||R_i - R_ij R_j||^2 到 Q
for a in range(2):
for b in range(2):
Q[2*i+a, 2*i+b] += 1.0 if a == b else 0.0
Q[2*j+a, 2*j+b] += R_ij.T @ R_ij[a, b] if a == b else 0.0
Q[2*i+a, 2*j+b] -= R_ij[a, b]
Q[2*j+a, 2*i+b] -= R_ij[b, a]
objective = cp.Minimize(cp.trace(Q @ X))
# 约束: X_ii = I_2 (对角块是单位矩阵)
constraints_list = [X >> 0] # PSD
for i in range(n):
constraints_list.append(X[2*i:2*i+2, 2*i:2*i+2] == np.eye(2))
prob = cp.Problem(objective, constraints_list)
prob.solve(solver=cp.SCS)
return X.value, prob.value
3.10 对偶理论的实践指南 ⭐⭐¶
何时使用对偶¶
| 场景 | 使用对偶的理由 | 不使用对偶的理由 |
|---|---|---|
| LASSO | 对偶是光滑 QP，比原问题（非光滑）更容易解 | 原问题用 FISTA 已足够快 |
| LP | 对偶提供最优性证书和影子价格 | 现代求解器同时求原-对偶 |
| SDP 松弛 | 对偶 PSD 证书验证全局最优 | 松弛不紧时无意义 |
| 分布式优化 | 对偶分解使子问题独立可解 | 对偶间隙收敛慢 |
| 敏感性分析 | 对偶变量 = 影子价格 = 约束重要性 | 需要强对偶保证 |
写对偶的标准流程¶
- 写 Lagrangian：\(L(x, \lambda, \nu) = f_0 + \sum \lambda_i f_i + \sum \nu_j h_j\)
- 对 \(x\) 最小化：\(g(\lambda, \nu) = \inf_x L\)。若 \(f_0\) 可微，求导令零得 \(x^*(\lambda, \nu)\)
- **代回**得到 \(g(\lambda, \nu)\) 的闭式
- 写对偶约束：\(\lambda \geq 0\)，加上使 \(\inf_x\) 有限的额外条件
- 验证 Slater：检查是否有严格可行点
- 解对偶问题：通常是无约束或简单约束的凹最大化
对偶在机器人学各方向的应用总结¶
| 方向 | 对偶理论的应用 |
|---|---|
| MPC | KKT = 求解器终止条件；影子价格 = 约束调试 |
| WBC/TSID | QP 对偶变量 = 接触力；互补松弛 = 接触/非接触 |
| SLAM | SDP 对偶 = 全局最优证书；松弛紧度检验 |
| 轨迹优化 | Pontryagin 最大原理 = 连续时间的 KKT；costate = 对偶变量 |
| RL | LP 对偶 = value function 的线性规划形式 |
| 安全控制 | CBF-QP 的对偶 = 安全裕度的量化 |
从 Pontryagin 到 KKT：连续与离散对偶 ⭐⭐⭐¶
最优控制的 Pontryagin 最大原理（PMP）可以看作连续时间的 KKT 条件。
连续时间问题：\(\min \int_0^T L(x, u)\,dt\) s.t. \(\dot{x} = f(x, u)\)
PMP：Hamilton 函数 \(H(x, u, p) = L(x, u) + p^\top f(x, u)\)
最优条件： - \(\dot{x} = \frac{\partial H}{\partial p} = f(x, u)\)（原动力学） - \(\dot{p} = -\frac{\partial H}{\partial x}\)（对偶/costate 动力学） - \(\frac{\partial H}{\partial u} = 0\)（稳定性）
与离散 KKT 的对应： - \(x_k\) ↔ \(x(t)\)（原变量） - \(\lambda_k\) ↔ \(p(t)\)（对偶变量/costate） - KKT 稳定性 ↔ PMP \(\partial H/\partial u = 0\) - KKT 互补松弛 ↔ PMP 的状态约束切换条件
DDP（Differential Dynamic Programming）正是通过离散化 PMP 来求解的——每步的 backward pass 计算 costate（对偶变量），forward pass 更新原变量。这正是"对偶-原始"交替迭代的思想。
本质洞察：KKT 条件和 Pontryagin 最大原理是同一个数学思想的两种表现形式——有限维（静态优化）和无穷维（动态优化）。理解了 KKT，就理解了 PMP 的 80%。
3.14 对偶理论的历史与知识演进 ⭐¶
对偶思想的发展历程¶
| 年代 | 里程碑 | 意义 |
|---|---|---|
| 1788 | Lagrange 乘子 | 等式约束优化的开端 |
| 1939 | LP 的 von Neumann 对偶 | 线性对偶的发现（零和博弈） |
| 1947 | 单纯形法 | Dantzig 发明 LP 求解算法 |
| 1951 | KKT 条件 | 非线性约束优化的一阶必要条件 |
| 1956 | Pontryagin 最大原理 | 连续时间的"KKT" |
| 1958 | Fenchel 对偶 | 共轭函数视角的对偶 |
| 1970 | Rockafellar 统一框架 | 凸分析 + 共轭 + 对偶的完整理论 |
| 1984 | Karmarkar 内点法 | LP 的多项式时间算法 |
| 1996 | SDP 综述 (Vandenberghe-Boyd) | 半正定规划进入主流 |
| 2004 | Boyd-Vandenberghe 教材 | 凸优化成为工程标准工具 |
| 2011 | ADMM 综述 | 对偶分裂方法的工程化 |
| 2016 | SE-Sync | 对偶证书用于 SLAM |
| 2020 | TEASER/TEASER++ | 对偶证书用于点云配准 |
| 2023 | TinyMPC | 对偶理论嵌入微控制器 |
三代研究者的贡献：
- 数学家（Lagrange, Fenchel, Rockafellar）：建立了对偶理论的数学基础
- 运筹学家（Dantzig, Karmarkar）：发明了高效的求解算法
- 工程师（Boyd, Stellato, Carlone）：把理论变成了可用的工具和软件
本教程的三章覆盖了这三个层面：Ch1 是数学基础，Ch2 是算法工具，Ch3 是工程应用。
向后指向：从对偶理论到后续章节¶
本章建立的对偶理论将在整个机器人学课程中反复使用：
| 本章概念 | 后续应用 |
|---|---|
| QP 及其 KKT | MPC：每步解 QP，终止条件 = KKT 残差 |
| Active-set 方法 | WBC/TSID：接触力分配，active contact 切换 |
| SOCP 对偶 | 摩擦锥约束：接触力在摩擦锥内 |
| SDP 松弛与证书 | Certifiable SLAM：SE-Sync 的对偶证书 |
| 影子价格 | MPC 约束调试：哪个约束最"值钱" |
| Pontryagin 原理 | DDP / iLQR：连续时间最优控制 |
| Lagrange 乘子 | 约束学习：CBF 的对偶变量 = 安全裕度 |
| Fenchel 对偶 | ADMM：OSQP 的内部算法 |
| 条件数分析 | 预处理：SLAM Hessian 的条件数改善 |
凸优化三部曲的总结¶
三章内容构成一个完整的体系：
Ch1: 凸分析基础 ─── 回答 "什么是好的优化问题？"
│ ├── 凸集/凸函数 → 可行域和目标的结构
│ ├── 分离定理 → KKT/对偶的几何根源
│ ├── 次梯度 → 非光滑函数的微分工具
│ └── 强凸/光滑 → 算法收敛的定量保证
│
Ch2: 共轭与 Proximal ─── 回答 "如何把问题变得可解？"
│ ├── 共轭函数 → 原-对偶空间的桥梁
│ ├── Proximal 算子 → 非光滑优化的计算核心
│ ├── Moreau 包络 → 非光滑 → 光滑的通用工具
│ └── ADMM → 把大问题拆成小问题
│
Ch3: 对偶理论 ─── 回答 "如何利用问题结构？"
├── Lagrange/Fenchel 对偶 → 下界/证书
├── KKT → 最优性的统一判据
├── 锥规划层级 → 问题分类/求解器选型
└── Certifiable perception → 全局最优保证
三章的知识树根在 Ch1（凸性），主干在 Ch2（共轭/proximal），枝叶在 Ch3（对偶/应用）。理解这个递进关系，就理解了"为什么要先学凸分析，再学共轭，最后学对偶"的教学设计。
延伸阅读¶
| 资源 | 难度 | 说明 |
|---|---|---|
| Boyd & Vandenberghe Ch 4-5 | ⭐⭐ | 问题分类+对偶的工程标准，免费PDF |
| Ben-Tal & Nemirovski "Modern Convex Optimization" | ⭐⭐⭐⭐ | 锥规划最系统的处理 |
| Bertsekas "Convex Optimization Theory" Ch 4-5 | ⭐⭐⭐⭐ | Min Common/Max Crossing 统一视角，几何极强 |
| Nocedal & Wright Ch 12 | ⭐⭐⭐ | 非凸 NLP 的 KKT + 约束品性 |
| Vandenberghe & Boyd "SDP" (SIAM Review 1996) | ⭐⭐⭐ | SDP 权威综述 |
| Carlone 2015 IROS + SE-Sync IJRR 2019 | ⭐⭐⭐⭐ | Certifiable SLAM 的对偶理论 |
| Stellato et al. "OSQP" (Math. Prog. Comp. 2020) | ⭐⭐⭐ | OSQP 的算法和实现细节 |
| Borrelli, Bemporad, Morari "Predictive Control" Ch 5 | ⭐⭐⭐ | MPC-QP 的对偶理论和 active-set 方法 |
| Rockafellar "Convex Analysis" §28-§31 | ⭐⭐⭐⭐⭐ | 对偶理论的数学圣经 |
| 文再文《最优化：建模、算法与理论》Ch 7-8 | ⭐⭐⭐ | 中文对偶理论最好的现代教材 |
| Acikmese & Ploen "Lossless Convexification" (2007) | ⭐⭐⭐⭐ | 火箭着陆凸化的对偶证明 |
推荐学习路线¶
根据你的应用方向，推荐的深入学习路线：
MPC 方向（足式控制）： 1. 本章 §3.1-3.5（QP + KKT）→ 2. Boyd Ch 4-5 → 3. OSQP/HPIPM 文档 → 4. Borrelli MPC 教材 Ch 5
SLAM 方向（视觉/激光）： 1. 本章 §3.6（SDP 对偶）→ 2. Carlone SE-Sync 论文 → 3. TEASER++ 论文 → 4. Vandenberghe SDP 综述
RL 方向（策略优化）： 1. 本章 §3.3-3.4（对偶理论）→ 2. Boyd Ch 5 → 3. LP 对偶 → 4. Bubeck "Convex Optimization" Ch 6（mirror descent）
控制综合方向： 1. 本章 §3.6（LMI）→ 2. Boyd "Linear Matrix Inequalities" → 3. Scherer 鲁棒控制 LMI → 4. SOS/Sum-of-Squares
对偶理论核心定理依赖图¶
凸集分离定理 (Ch1)
├── Farkas 引理 → LP 强对偶
│ └── 单纯形法终止条件
├── 弱对偶定理
│ ├── 对偶函数 g ≤ p*（恒成立）
│ └── 对偶下界 → Certifiable 算法
├── Slater 条件 → 强对偶
│ ├── μ > 0 → 分离超平面不水平
│ └── 强对偶 → KKT 充要性
├── KKT 四组件
│ ├── 互补松弛 → Active-set 方法
│ ├── 稳定性 → 求解器终止条件
│ └── 影子价格 → 敏感性分析
└── SDP 对偶
├── 矩阵互补松弛 XS = 0
├── 对偶 PSD 证书
└── Certifiable SLAM (SE-Sync)
对偶理论的统一视角¶
回顾三章的联系：
- Ch1 分离定理 → 保证了"凸集外的点可以被线性不等式排除"
- Ch2 Fenchel-Moreau → 保证了"共轭变换可逆"
- Ch3 强对偶 → 保证了"对偶问题等价于原问题"
三个定理的共同核心是**闭凸性**： - 分离定理需要闭凸集 - Fenchel-Moreau 需要闭凸函数 - 强对偶需要 Slater 条件保证值函数 \(p(u)\) 的闭凸性
本质洞察："闭凸"是整个凸优化理论的基石。它保证了"局部等于全局"（凸性）且"极限行为良好"（闭性）。没有闭凸性，分离定理、对偶理论、KKT 条件——所有核心工具都可能失效。
本质洞察：对偶理论的终极价值不只是"给出下界"或"提供算法"——它把**约束优化**这个本质困难的问题（约束可能使可行域形状复杂）转化为**无约束优化**（对偶函数关于对偶变量无约束或约束简单）。这种"从有约束到无约束"的转化是对偶理论最深刻的思想贡献。
给初学者的建议¶
学完这三章凸优化基础后，你已经具备了以下能力：
- 判断凸性：给定任何优化问题，能判断它是否凸，属于哪一类（LP/QP/SOCP/SDP）
- 写对偶：对凸问题写出 Lagrange/Fenchel 对偶，判断强对偶是否成立
- 选求解器：根据问题类型和规模选择合适的求解器
- 验证最优性：通过 KKT 残差和对偶间隙验证解的质量
- 调试约束：通过影子价格（对偶变量）定位最紧的约束
- 凸化问题：对非凸问题尝试凸松弛（SDP/核范数）
这些能力将在后续的 MPC、WBC、SLAM、轨迹优化等章节中反复使用。凸优化理论是机器人学优化方法的"操作系统"——你可能不需要每天重新推导对偶定理，但每天都在使用它的结论。
下一步学习：建议在具体应用（如 MPC 章节）中回来查阅本章的 QP 对偶和 KKT 条件，在 SLAM 章节中回来查阅 SDP 松弛和对偶证书。理论和应用的结合是最有效的学习方式——学了理论后不要急着"全部记住"，而是在用到时回来复习，每次复习都会有更深的理解。
最终检验：学完三章后，尝试回答以下问题来验证理解程度： - 为什么凸优化的局部最优一定是全局最优？（Ch1 分离定理 → 一阶条件充要） - 为什么 OSQP 用 ADMM 而不用内点法？（Ch2 prox 的高效性 + 嵌入式约束） - 为什么 SE-Sync 能保证 SLAM 的全局最优？（Ch3 SDP 对偶证书） - 为什么加 \(\ell_2\) 正则化能改善 LASSO 的收敛速度？（Ch1 强凸性 + Ch2 条件数不变性）
🔧 故障排查手册¶
| 症状 | 可能原因 | 排查步骤 | 相关章节 |
|---|---|---|---|
| OSQP 返回 "primal infeasible" | 约束不相容 | 1. 检查 \(l \leq u\) 2. 松弛约束看能否可行 3. 用对偶不可行性证书诊断 | §3.5 |
| 对偶间隙不为零 | Slater 条件不满足 | 1. 检查是否存在严格可行点 2. 检查约束是否退化 3. 尝试微小扰动约束 | §3.4 |
| CVXPY 报 "problem not DCP" | 建模不满足 DCP 规则 | 1. 分解目标/约束为 DCP atom 2. 用 epigraph 变换 3. 检查 CVXPY DCP 规则文档 | §3.2 |
| SDP 求解精度差 | 用了低精度求解器 | 1. 换 MOSEK（高精度 IPM）2. 开 SCS 的 polishing 3. 检查问题条件数 | §3.6, §3.9 |
| KKT 点不是最优 | 问题非凸或 CQ 不满足 | 1. 验证凸性 2. 检查 Slater/LICQ 3. 如果非凸，KKT 只是必要条件 | §3.5 |
| 对偶变量全为零 | 约束全部 inactive | 1. 检查约束是否真的不紧 2. 可能问题无约束也能解 3. 考虑是否需要这些约束 | §3.5, §3.7 |
| QP 解不满足约束 | 求解器精度不够或问题建模有误 | 1. 检查 KKT 残差 2. 提高求解器精度 3. 检查约束矩阵 \(A\) 和边界 \(l, u\) | §3.5, §3.9 |
| ADMM 的原对偶残差不平衡 | \(\rho\) 选择不当 | 1. 原残差 \(\gg\) 对偶残差 → 增大 \(\rho\) 2. 原残差 \(\ll\) 对偶残差 → 减小 \(\rho\) 3. 使用自适应 \(\rho\) | §3.9 |
| LP 求解器报 "unbounded" | 目标函数在可行域上无下界 | 1. 检查是否有约束遗漏 2. 对偶不可行 → 原问题无界 3. 添加 box 约束 \(\|x\| \leq M\) | §3.3 |
| SDP 求解时间过长 | 问题规模太大或结构未利用 | 1. 检查是否能用 SOCP 替代 2. 利用稀疏性 3. 用低精度 SCS 替代高精度 MOSEK | §3.6, §3.9 |
故障排查的数值验证方法¶
验证 1：KKT 残差检查
# 对 OSQP 的解检查 KKT 残差
stationarity = np.linalg.norm(P @ x + q + A.T @ y)
primal_feas = np.max(np.maximum(l - A @ x, 0) + np.maximum(A @ x - u, 0))
print(f"稳定性残差: {stationarity:.2e}")
print(f"原可行残差: {primal_feas:.2e}")
# 应该都 < 1e-3 (OSQP 默认精度)
验证 2：强对偶检查
# 用 CVXPY 检查
prob.solve()
primal = prob.value
dual = sum(c.dual_value @ c.residual for c in prob.constraints)
gap = abs(primal - dual) / max(1, abs(primal))
print(f"相对对偶间隙: {gap:.2e}")
# 强对偶成立时应 < 1e-6
验证 3：影子价格的数值验证
# 微扰第 i 个约束，检查最优值变化
delta = 1e-4
# 原始最优值
prob_original.solve()
p_star = prob_original.value
# 松弛后最优值
constraints_relaxed[i] = constraint_i + delta
prob_relaxed.solve()
p_star_relaxed = prob_relaxed.value
# 数值影子价格
numerical_shadow = (p_star - p_star_relaxed) / delta
# 与对偶变量比较
print(f"对偶变量: {lambda_i_star:.4f}")
print(f"数值影子价格: {numerical_shadow:.4f}")
3.11 LP 对偶的完整理论 ⭐⭐¶
动机¶
线性规划的对偶理论是最简单也最完整的——强对偶不需要 Slater 条件，只要原问题可行有界就成立。LP 对偶是理解一般对偶理论的最佳起点。
LP 原-对偶对¶
原问题（标准形式）：\(\min c^\top x\) s.t. \(Ax = b\), \(x \geq 0\)
对偶问题：\(\max b^\top y\) s.t. \(A^\top y \leq c\)
证明（从 Lagrangian 推导）：
\(L(x, \lambda, y) = c^\top x + y^\top(b - Ax) + \lambda^\top(-x) = (c - A^\top y - \lambda)^\top x + b^\top y\)
其中 \(\lambda \geq 0\)（对应 \(x \geq 0\)）。
\(g(y, \lambda) = \inf_x [(c - A^\top y - \lambda)^\top x + b^\top y]\)
若 \(c - A^\top y - \lambda \neq 0\)，取 \(x\) 使 inf 为 \(-\infty\)。
若 \(c - A^\top y - \lambda = 0\)，即 \(\lambda = c - A^\top y \geq 0\)：\(g = b^\top y\)。
对偶问题：\(\max b^\top y\) s.t. \(A^\top y \leq c\)（\(\lambda = c - A^\top y \geq 0\)）。
LP 强对偶定理¶
定理（LP 强对偶）：若 LP 原问题可行且有界，则对偶也可行且有界，且 \(p^* = d^*\)。
证明思路：可以用 Farkas 引理（分离定理的代数版本）直接证明，不需要 Slater。
LP 强对偶的特殊性在于：LP 的可行域是多面体，多面体的闭凸性保证了 \(p(u)\)（值函数）的闭凸性，从而 \(p^{**}(0) = p(0)\)——强对偶自动成立。
LP 互补松弛的组合意义¶
LP 的互补松弛 \(\lambda_i^* x_i^* = 0\)（\(\lambda = c - A^\top y\)）意味着：
对每个变量 \(x_i\)： - \(x_i^* > 0\)（变量"active"，取正值）\(\Rightarrow\) \(\lambda_i^* = 0\)（对偶约束 \(A_i^\top y = c_i\) 取等号） - \(x_i^* = 0\)（变量"inactive"，在边界上）\(\Rightarrow\) \(\lambda_i^* \geq 0\)（对偶约束可以是不等式）
这就是单纯形法的基本-非基本划分：基本变量 \(x_B > 0\) 对应的对偶约束取等号，非基本变量 \(x_N = 0\) 对应的对偶约束是不等式。
练习¶
- 对 LP \(\min [1, 2, 3]^\top x\) s.t. \(x_1+x_2+x_3 = 1\), \(x \geq 0\)，写出对偶问题并验证强对偶。
- 解释为什么 LP 的对偶的对偶等于原问题（LP 对偶是对合的）。
- 用 Farkas 引理证明：\(Ax \leq b\) 无解 \(\Leftrightarrow\) 存在 \(y \geq 0\) 使 \(A^\top y = 0\), \(b^\top y < 0\)。
3.12 QP 的 KKT 系统与线性代数 ⭐⭐¶
动机¶
QP 是机器人学中最常见的优化问题（MPC、WBC、IK）。QP 的 KKT 条件可以写成一个线性系统——理解这个系统的结构对于选择合适的求解器和调优至关重要。
QP 的 KKT 线性系统¶
考虑等式约束 QP：\(\min \frac{1}{2}x^\top Px + q^\top x\) s.t. \(Ax = b\)。
KKT 条件： $\(Px + q + A^\top\nu = 0, \quad Ax = b\)$
写成线性系统（KKT 系统）： $\(\begin{pmatrix} P & A^\top \\ A & 0 \end{pmatrix}\begin{pmatrix} x \\ \nu \end{pmatrix} = \begin{pmatrix} -q \\ b \end{pmatrix}\)$
这是一个**鞍点系统**（saddle-point system）——左上块正定、右下块零，使得整体矩阵不定。
KKT 矩阵的性质¶
KKT 矩阵 \(K = \begin{pmatrix} P & A^\top \\ A & 0 \end{pmatrix}\) 的性质：
- 对称但不定：特征值有正有负
- 可逆条件：\(P \succ 0\) 且 \(A\) 满行秩 → \(K\) 可逆
- Schur 互补：消去 \(x\) 得 \(AP^{-1}A^\top \nu = AP^{-1}q + b\)（正规方程）
- 稀疏性：在 MPC 中，\(P\) 和 \(A\) 是带状/块对角的，\(K\) 也是稀疏的
求解 KKT 系统的方法¶
| 方法 | 适用条件 | 复杂度 | 求解器 |
|---|---|---|---|
| LDL 分解 | 一般 KKT 矩阵 | \(O(n^3)\) | QDLDL (OSQP) |
| Cholesky（正规方程） | \(P \succ 0\) | \(O(n^3)\) | 多数求解器 |
| Riccati 递推 | MPC 结构 | \(O(Nn^3)\) | HPIPM, acados |
| 迭代法（CG） | 大规模稀疏 | \(O(n \cdot \text{nnz})\) per iter | Ceres |
MPC 中的 Riccati 递推 ⭐⭐⭐¶
MPC-QP 的 KKT 矩阵有特殊结构——它是 block-tridiagonal 的（由系统动力学 \(x_{k+1} = Ax_k + Bu_k\) 产生）。
Riccati 递推利用这个结构，在 \(O(N \cdot (n_x + n_u)^3)\) 时间内求解——比一般的 \(O((N(n_x+n_u))^3)\) 快 \(N^2\) 倍。
这就是 HPIPM 和 acados 比通用 QP 求解器快得多的原因——它们利用了 MPC 的时序结构。
不等式约束的 Active-Set 降维 ⭐⭐¶
对不等式约束 QP：\(\min \frac{1}{2}x^\top Px + q^\top x\) s.t. \(Gx \leq h\), \(Ax = b\)。
如果我们知道 active set \(\mathcal{A}\)，问题简化为： $\(\min \frac{1}{2}x^\top Px + q^\top x \quad \text{s.t. } G_\mathcal{A} x = h_\mathcal{A}, \quad Ax = b\)$
这是一个等式约束 QP，可以用上面的 KKT 系统求解！
Active-set 方法的核心就是：通过迭代"猜测"active set，每步解一个等式约束 QP。
练习¶
- 对 \(P = \text{diag}(1, 2)\)，\(q = [-1, -2]^\top\)，\(A = [1, 1]\)，\(b = 1\)，手动构造和求解 KKT 系统。
- 解释为什么 MPC 的 KKT 矩阵是 block-tridiagonal 的。
- 对 \(N = 5\) 步的 MPC，比较一般 LDL 分解和 Riccati 递推的计算量。
3.13 对偶理论在 Certifiable Perception 中的应用 ⭐⭐⭐¶
动机¶
传统 SLAM 和 perception 算法只给出一个"最好猜测"的解——但无法保证这个解是全局最优的。Certifiable perception 利用对偶理论，在解的同时提供**全局最优性证书**。
基本框架¶
- 原问题（非凸）：\(\min f(x)\) s.t. \(x \in \mathcal{M}\)（\(\mathcal{M}\) 是非凸流形，如 \(SO(3)^N\)）
- 凸松弛（SDP）：把非凸约束 \(x \in \mathcal{M}\) 松弛为 \(X \succeq 0\)（矩阵提升）
- 对偶问题（SDP 对偶）：\(\max b^\top y\) s.t. \(C - \sum y_i A_i \succeq 0\)
- 最优性证书：如果 SDP 松弛是 tight 的（\(\text{rank}(X^*) = r\)），对偶变量 \(y^*\) 就是全局最优性证书
证书的含义¶
对偶 PSD 条件 \(M(y^*) = C - \sum y_i^* A_i \succeq 0\) 的含义是：
即对偶值是原问题最优值的全局下界。如果松弛 tight，\(f(x^*) = b^\top y^*\)——我们找到的解恰好达到了全局下界，因此是全局最优的。
在具体问题中的应用¶
| 问题 | 原非凸约束 | SDP 松弛 | 松弛紧度 |
|---|---|---|---|
| 旋转同步 | \(R_i^\top R_i = I\) | \(X \succeq 0\), \(X_{ii} = I\) | 低噪声时 tight |
| PnP | \(R \in SO(3)\) | 同上 | 通常 tight |
| 点云配准 | \(R \in SO(3)\), \(t \in \mathbb{R}^3\) | Shor 松弛 | 中等噪声 tight |
| 手眼标定 | \(R_1, R_2 \in SO(3)\) | 同上 | 通常 tight |
当松弛不紧时怎么办 ⭐⭐⭐⭐¶
如果 SDP 松弛最优解的秩 > \(r\)（目标秩），松弛是松的：
- Riemannian Staircase（Boumal 2015）：增大提升的秩 \(p\)，在更高维的搜索空间中寻找低秩解
- GNC + 对偶证书：用 GNC 从凸松弛出发逐步过渡到原非凸问题
- 局部搜索 + 对偶下界：用 Gauss-Newton 局部搜索，用对偶值判断与全局最优的间隙
练习¶
- 对 2D 旋转同步（\(R \in SO(2)\)，3 个节点，3 条边），写出 QCQP、SDP 松弛和 SDP 对偶，用 CVXPY 求解。
- 在上述例子中增加噪声水平，观察何时 SDP 松弛变得不紧。
- 实现对偶证书检查：验证 \(M(y^*) \succeq 0\) 且 \(\text{rank}(X^*) = 2\)（2D 旋转的目标秩）。
3.14 等价变换的实际应用 ⭐⭐¶
\(\ell_\infty\) 最小化 → LP¶
\(\min_x \|Ax - b\|_\infty = \min_x \max_i |a_i^\top x - b_i|\)
引入 \(t\)：\(\min t\) s.t. \(-t \leq a_i^\top x - b_i \leq t\)（\(\forall i\)）
原来的 minimax 非光滑问题变成了标准 LP。
\(\ell_1\) 最小化 → LP¶
\(\min_x \|Ax - b\|_1 = \min_x \sum_i |a_i^\top x - b_i|\)
引入 \(u_i, v_i \geq 0\)：\(a_i^\top x - b_i = u_i - v_i\)，\(|a_i^\top x - b_i| = u_i + v_i\)
\(\min \sum(u_i + v_i)\) s.t. \(Ax - b = u - v\), \(u, v \geq 0\)——标准 LP。
Robust LP → SOCP 的完整推导¶
\(\min c^\top x\) s.t. \((a_i + \delta_i)^\top x \leq b_i\)（\(\|\delta_i\| \leq \rho_i\)）
worst-case 约束：\(\max_{\|\delta\| \leq \rho} (a_i + \delta)^\top x \leq b_i\)
\(\max_{\|\delta\| \leq \rho} \delta^\top x = \rho\|x\|\)（Cauchy-Schwarz 等号条件：\(\delta = \rho x/\|x\|\)）
因此：\(a_i^\top x + \rho_i\|x\| \leq b_i\)，即 \(\rho_i\|x\| \leq b_i - a_i^\top x\)——SOC 约束。
反事实推理：如果不做等价变换会怎样？你会试图直接处理 minimax 或非光滑问题——需要次梯度法（\(O(1/\sqrt{k})\) 收敛），而不是 LP/SOCP 的内点法（多项式时间，高精度）。等价变换把"硬"问题变成"软"问题。
Markowitz Portfolio → QP¶
\(\min_w w^\top \Sigma w\) s.t. \(\mu^\top w \geq r\), \(\mathbf{1}^\top w = 1\), \(w \geq 0\)
这是标准 QP（\(\Sigma \succeq 0\)）。对偶变量的含义： - \(\lambda_r\)（收益约束）：收益要求提高一个单位，风险至少增加 \(\lambda_r\) - \(\nu\)（预算约束）：无风险收益率的"代理"
SVM → QP¶
支持向量机的对偶：\(\max_\alpha \sum \alpha_i - \frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j K(x_i,x_j)\) s.t. \(0 \leq \alpha_i \leq C\), \(\sum \alpha_i y_i = 0\)
这是 box 约束 QP。KKT 互补松弛决定了哪些样本是"支持向量"（\(0 < \alpha_i < C\)）。
练习¶
- 把 Chebyshev center 问题（最大内接球）\(\max r\) s.t. \(a_i^\top x + r\|a_i\| \leq b_i\) 识别为哪类问题。
- 把 basis pursuit \(\min \|x\|_1\) s.t. \(Ax = b\) 化为 LP。
- 对机器人的力分配问题 \(\min \sum \|f_i - f_{i,d}\|^2\) s.t. \(\|f_{i,t}\| \leq \mu_i f_{i,n}\), \(f_{i,n} \geq 0\), \(\sum J_i^\top f_i = \tau_d\)，识别问题类型（SOCP），并用 CVXPY 建模。
等价变换的选择指南¶
面对一个优化问题时，按以下优先级尝试等价变换：
- 能否化为 LP？ 若目标和约束都可以线性化（如 \(\ell_1\)、\(\ell_\infty\)），LP 最快
- 能否化为 QP？ 若目标二次、约束线性 → QP 有极高效的求解器
- 能否化为 SOCP？ 若有范数约束（摩擦锥、鲁棒性）→ SOCP
- 能否化为 SDP？ 若有矩阵不等式约束 → SDP（但规模限制严）
- 以上都不行？ 使用一般凸优化方法（proximal gradient / ADMM）或非凸方法（SQP / Ipopt）
黄金法则：能用更简单的类型就不用更复杂的。LP < QP < SOCP < SDP < General Convex < NLP。越简单的类型，求解器越快、越稳定、可扩展性越好。
符号表¶
| 符号 | 含义 | 首次出现 |
|---|---|---|
| \(f_0(x)\) | 凸优化问题的目标函数 | §3.1 |
| \(f_i(x)\) | 第 \(i\) 个不等式约束函数 | §3.1 |
| \(h_j(x)\) | 第 \(j\) 个等式约束函数（仿射） | §3.1 |
| \(L(x, \lambda, \nu)\) | Lagrangian 函数 | §3.3 |
| \(\lambda_i\) | 不等式约束的 Lagrange 乘子（\(\lambda_i \geq 0\)） | §3.3 |
| \(\nu_j\) | 等式约束的 Lagrange 乘子 | §3.3 |
| \(g(\lambda, \nu)\) | 对偶函数 \(\inf_x L(x, \lambda, \nu)\) | §3.3 |
| \(p^*\) | 原问题最优值 | §3.3 |
| \(d^*\) | 对偶问题最优值 | §3.3 |
| \(\mathbb{S}^n_+\) | \(n \times n\) 半正定矩阵锥 | §前置自测 |
| \(\mathcal{K}\) | 广义不等式的锥（LP/SOCP/SDP 统一框架） | §3.2 |
| \(\kappa\) | 条件数（\(\kappa = L/\mu\)） | §3.1 |