第14章 半正定规划（SDP）与凸松弛：从组合问题到可解优化

1. 开篇与学习目标

计算机视觉的核心往往归结为组合优化问题（Combinatorial Optimization）。

• 分割：每个像素是属于“前景”还是“背景”？（离散二值选择）
• 配准：点云 A 中的第 $i$ 个点是对应点云 B 中的第 $j$ 个点，还是第 $k$ 个点？（置换矩阵）
• SLAM/SfM：在噪声观测下，如何推断出一组全局一致的相机位姿？（非凸群上的优化）

这些问题直接求解通常是 NP-难（NP-Hard）的，因为解空间随着变量数量指数级爆炸。传统的解决方法包括贪心算法、模拟退火或谱方法（Spectral Relaxation）。

半正定规划（Semidefinite Programming, SDP） 代表了当前凸松弛技术的“最高水准”。相比于线性规划（LP）松弛，SDP 能捕捉变量之间的高阶相关性（Pairwise Correlations），提供极其紧致的下界。甚至在很多特定噪声条件下，SDP 能够以高概率恢复出原问题的精确全局最优解（Exact Recovery）。

本章学习目标：

1. 几何直觉：理解半正定锥（PSD Cone）的几何形状，以及为什么它比多面体更“高级”。
2. 建模能力：掌握“提升（Lifting）”技巧，将二次非凸问题转化为线性矩阵凸问题。
3. 视觉场景：深入理解 SDP 在图割（Graph Cut）、旋转同步（Rotation Synchronization）和特征匹配中的应用。
4. 求解策略：面对大规模视觉数据，如何跨越 $O(N^6)$ 的复杂度障碍（从内点法到 Burer-Monteiro 分解）。

2. 核心论述

2.1 什么是 SDP？—— 矩阵空间上的线性规划

线性规划（LP）是在非负象限（第一象限）切蛋糕（多面体），而 SDP 是在半正定矩阵锥上切蛋糕。

2.1.1 标准形式

一个标准的 SDP 问题通常写作：

$$ \begin{aligned} \min_{X \in \mathbb{S}^n} \quad & \langle C, X \rangle \\ \text{s.t.} \quad & \langle A_i, X \rangle = b_i, \quad i=1,\dots,m \\ & X \succeq 0 \end{aligned} $$

• 变量：$X$ 是一个 $n \times n$ 的对称矩阵。
• 目标：线性函数 $\langle C, X \rangle = \text{tr}(C^T X) = \sum_{ij} C_{ij} X_{ij}$。
• 约束：
  • 仿射约束 $\langle A_i, X \rangle = b_i$：这些是定义在矩阵元素上的线性方程（例如规定对角线为1，或者某些元素之和为0）。
  • 锥约束 $X \succeq 0$：$X$ 必须是半正定矩阵（所有特征值 $\lambda_i \ge 0$）。

2.1.2 几何直觉：Spectrahedron

半正定锥 $\mathbb{S}_+^n$ 是一个凸集，但它不是多面体，它的边界是弯曲的（由行列式 $\det(X)=0$ 定义）。

       ASCII Art: 2x2 矩阵的半正定锥切片
       Let X = [ x   y ]
               [ y   z ]
       条件: x>=0, z>=0, xz - y^2 >= 0

              ^ z (对角元素1)
             /
            /      /
           /     /   <-- 锥体内部 (PSD)
          /    /
         /   /      边界是圆锥面 (xz = y^2)
        /__/________> x (对角元素2)
       /
      y (非对角元素)

    当添加线性约束 (如 x+z=1) 时，
    截面看起来像是一个椭圆的一部分。
    这个截面被称为 "Spectrahedron"。

2.2 核心技巧：提升（Lifting）与松弛（Relaxation）

这是将视觉中的“硬”问题变成 SDP 的通用三步走套路。

场景：二值二次规划 (Binary Quadratic Programming, BQP) 很多视觉能量函数可以写成： $$ \min_{x \in \{-1, 1\}^n} x^T Q x + c^T x $$ Step 1: 齐次化与提升 (Homogenization & Lifting) 为了处理线性项 $c^T x$，通常引入辅助变量 $x_{n+1}=1$，令 $\tilde{x} = [x; 1]$。 问题变为纯二次形式：$\min \tilde{x}^T \tilde{Q} \tilde{x}$。 定义矩阵变量 $X = \tilde{x} \tilde{x}^T$。这个矩阵 $X$ 包含了所有二次项的信息 ($X_{ij} = \tilde{x}_i \tilde{x}_j$)。

Step 2: 转化约束

• 目标函数：$\tilde{x}^T \tilde{Q} \tilde{x} = \text{tr}(\tilde{Q} \tilde{x} \tilde{x}^T) = \langle \tilde{Q}, X \rangle$ （线性化了！）。
• 二值约束：$x_i \in \{-1, 1\} \iff x_i^2 = 1 \iff X_{ii} = 1$ （对角线固定）。
• 结构约束：$X = \tilde{x} \tilde{x}^T \iff X \succeq 0 \text{ AND } \text{rank}(X)=1$。

Step 3: 丢弃秩约束 (The Relaxation) $\text{rank}(X)=1$ 是唯一的非凸约束，也是问题的难点所在。SDP 松弛直接扔掉这个约束。 $$ \text{SDP Relaxation}: \quad \min_{X} \langle \tilde{Q}, X \rangle \quad \text{s.t.} \quad X_{ii}=1, \ X \succeq 0 $$ 这个凸问题我们可以求解。如果求出的最优解 $X^*$ 恰好秩为 1，我们就精确还原了原问题的解（Tightness）。

2.3 重要的构造工具：Schur 补 (Schur Complement)

在建模中，我们经常遇到非线性的分式形式，如何将其转为 LMI（线性矩阵不等式）？

引理： 对于对称分块矩阵 $M = \begin{bmatrix} A & B \\ B^T & C \end{bmatrix}$，若 $C \succ 0$，则： $$ M \succeq 0 \iff A - B C^{-1} B^T \succeq 0 $$ 应用示例：最小化范数 假设我们要优化变量 $x$，约束为 $f(x) \le t$（$t$ 也要最小化），其中 $f(x) = y^T x^T x y$。 这等价于 $t - y^T x^T I^{-1} x y \ge 0$。 利用 Schur 补，可以写成 SDP 约束： $$ \begin{bmatrix} t & (xy)^T \\ xy & I \end{bmatrix} \succeq 0 $$ 这使得我们可以把原本出现在分母或二次项里的变量，放到大矩阵里变成线性约束。

3. 计算机视觉中的典型应用

3.1 图割与分割 (Graph Cuts & Segmentation)

经典的 Normalized Cut (N-Cut) 也是一种谱松弛，但它只松弛到了实数值向量，忽略了 $x_i \in \{-1, 1\}$ 的二值特性。 SDP 松弛（如 Max-Cut SDP）能更好地保持离散结构。

• 模型： $$ \min \sum_{i,j} w_{ij} (1 - x_i x_j) $$ 这等价于最大化 $\sum w_{ij} x_i x_j$。

• SDP 形式： $$ \min \langle -W, X \rangle \quad \text{s.t.} \quad X_{ii}=1, \ X \succeq 0 $$ 这里 $W$ 是邻接矩阵。

• 优势：在包含“必须连(Must-link)”和“不能连(Cannot-link)”约束时，SDP 可以轻松将这些约束作为 $X_{ij}=1$ 或 $X_{ij}=-1$ 加入，而谱聚类很难硬性处理这些约束。

3.2 旋转同步 (Rotation Synchronization)

这是现代 SfM (Structure from Motion) 和 SLAM 的基石。 问题：已知成对相对旋转 $R_{ij} \approx R_i R_j^T$，求全局旋转 $R_1, \dots, R_N \in SO(3)$。

• 非凸性：$SO(3)$ 是一个弯曲的流形（非凸）。

• SDP 建模： 定义大矩阵 $G$ 为 Block Matrix，其中第 $(i,j)$ 块为 $R_i R_j^T$。 $$ G = \begin{bmatrix} R_1 \\ \vdots \\ R_N \end{bmatrix} \begin{bmatrix} R_1^T & \dots & R_N^T \end{bmatrix} $$ 性质：

  1. $G \succeq 0$。
  2. $G_{ii} = I_3$ （对角块是单位阵）。
  3. $\text{rank}(G) = 3$ （如果是 3D 旋转）。 * 松弛：丢弃秩约束，保留 $G \succeq 0$ 和 $G_{ii} = I_3$。 * 结果：即使在噪声很大的情况下，这种方法也能恢复出全局最优的相机朝向，比传统的增量式（Incremental）SfM 鲁棒得多。

3.3 点集配准与置换矩阵 (Registration & Permutations)

寻找形状 A 和形状 B 的点对应关系，本质是求一个置换矩阵 $P$。

• 约束：$P$ 是正交的 ($P P^T = I$) 且元素非负 ($P_{ij} \ge 0$)。
• SDP 松弛：这也形成了一个凸包（Birkhoff Polytope 的加强版）。 通过定义 $Y = [vec(P); 1][vec(P); 1]^T$，我们可以同时松弛正交约束和行/列和约束。这在非刚体配准和图匹配（Graph Matching）中非常有效。

4. 求解方法：理想 vs 现实

SDP 理论上是多项式时间可解的，但在工程上，这是最大的陷阱。

4.1 通用内点法 (Interior Point Methods, IPM)

• 代表：CVX (Matlab), Mosek, SeDuMi, SDPT3。
• 机制：在锥内部走牛顿步（Newton Step）。
• 代价：每一步需要计算 Hessian 的逆。对于 $n \times n$ 的矩阵变量，复杂度是 $O(n^6)$ 或 $O(m n^3)$。
• 极限：$n > 100$ (即 100 个点或变量) 时基本上就跑不动了。
• 适用：理论验证、极小规模问题、骨架提取等稀疏问题。

4.2 一阶分裂方法 (First-Order Splitting)

• 代表：ADMM, Primal-Dual Hybrid Gradient (PDHG)。

• 思路：把 $X \succeq 0$ 的约束投影拆解出来。 $$ \text{Proj}_{\mathbb{S}_+}(Y) = U \max(\Lambda, 0) U^T $$

• 代价：每一步做一次特征值分解 (EVD)。复杂度 $O(n^3)$。

• 极限：$n \approx 1000$ - 2000。对于图像像素级（$n=10^4$ 以上）依然太慢。

4.3 救世主：Burer-Monteiro 分解

这是目前视觉领域解决大规模 SDP（如 $N=10^4$ 规模的同步问题）的标准做法。

• 核心思想：既然 SDP 松弛是为了丢掉 $\text{rank}=1$ 或 $\text{rank}=k$ 的约束，那我们不如显式地把低秩结构塞回去。 令 $X = Y Y^T$，其中 $Y \in \mathbb{R}^{n \times k}$，且 $k \ll n$ (例如 $k$ 取 5 或 10)。

• 新问题： $$ \min_{Y \in \mathbb{R}^{n \times k}} \langle C, Y Y^T \rangle \quad \text{s.t. 线性约束} $$

• 性质：

  1. 非凸了：这就变回了一个非凸优化问题（定义在流形上）。
  2. 极快：变量数从 $n^2$ 降到了 $nk$。只需要做简单的梯度下降或黎曼流形梯度下降。
  3. 良态非凸 (Benign Non-convexity)：理论证明显示，对于许多视觉 SDP 问题（如同步、聚类），只要噪声不是特别大，这个非凸地貌没有虚假的局部最优解（Spurious Local Minima）。梯度下降能直接收敛到全局最优。
• 常用库：Manopt (Matlab), SE-Sync, Teaser++ (C++ 库核心算法)。

5. 本章小结

1. 强力松弛：SDP 通过提升变量维度（$x \to X$），将离散的组合约束转化为连续的几何约束（半正定锥），提供了比线性规划更紧的界。
2. 通用模板：大多数视觉二次问题都可以套用 Lifting -> Relaxing Constraints -> Rounding 的流程。
3. Schur 补：是将非线性/分式项转化为 LMI 约束的瑞士军刀。
4. 计算鸿沟：直接解 SDP（内点法）不可扩展。在大规模视觉应用中，必须使用 Burer-Monteiro 分解（低秩流形优化）或专用的 ADMM 求解器。

6. 练习题

基础题

Q1. 迹的循环性质与松弛 证明 $\text{tr}(Q x x^T) = x^T Q x$。如果 $X = \sum_{i=1}^r \lambda_i v_i v_i^T$ 是 $X$ 的谱分解，说明 $\langle Q, X \rangle$ 是若干个二次型 $v_i^T Q v_i$ 的加权和。这如何解释 SDP 是对二次问题的“平均”松弛？

Q2. 对角约束的物理意义 在图割问题中，松弛变量 $X$ 满足 $X_{ii}=1$。 (a) 这对应于向量 $x$ 的什么几何约束？ (b) 如果去掉这个约束，只保留 $X \succeq 0$，对于最小化问题 $\min \langle L, X \rangle$ 会发生什么？

Q3. Schur 补实战 将约束 $x^T x \le y z$ (其中 $y,z > 0$) 写成线性矩阵不等式 (LMI) 的形式。

挑战题

Q4. Max-Cut 的随机舍入 (Randomized Rounding) 著名的 Goemans-Williamson 算法是 SDP 史上的里程碑。 给定 SDP 最优解 $X^*$（秩可能不为1），如何生成二值解 $x \in \{-1, 1\}^n$？ 算法步骤：

1. 对 $X^*$ 做 Cholesky 分解得 $X^* = V^T V$，其中 $V = [v_1, \dots, v_n]$ 是列向量。
2. 随机选取一个单位向量 $r$（随机超平面）。
3. 令 $x_i = \text{sign}(v_i^T r)$。 问题：请直观解释为什么 $v_i$ 和 $v_j$ 夹角越小，被切分到同一类的概率越大？

Q5. 紧度与对偶间隙 (Duality Gap) 在视觉应用中，怎么判断 SDP 得到的解是否就是原问题的最优解（Exact Recovery）？ 如果是，矩阵 $X^*$ 应该具有什么秩？如果秩不满足要求，我们能相信这个解吗？

7. 常见陷阱与错误 (Gotchas)

7.1 混淆 Element-wise 和 PSD

• 错误：在代码中写 X >= 0。
• 后果：这表示 $X_{ij} \ge 0$（非负矩阵），而不是 $X \succeq 0$（半正定矩阵）。
• 调试：在 CVX 等工具中，必须明确使用 X == semidefinite(n) 或者 X >= 0 (取决于语境，CVX通常重载了 >= 用于矩阵变量表示 PSD，但在普通 Numpy/PyTorch 中这是元素级比较)。

7.2 忘记 $X_{ii}=1$

• 现象：求解 Graph Cut 松弛时，得到 $X=0$ 或者 $X$ 极其微小。
• 原因：没有给解加上“尺度”约束。拉普拉斯矩阵 $L$ 也是半正定的，最小化 $\langle L, X \rangle$ 会倾向于把 $X$ 压扁。
• 修正：必须包含 $X_{ii}=1$（对于二值/归一化问题）或 $\text{tr}(X)=k$。

7.3 盲目使用 CVX 处理图像

• 现象：尝试对 $64 \times 64$ 的图像块做 SDP 去噪，Matlab 卡死。
• 原因：$N=4096$，变量数 $N^2 \approx 1.6 \times 10^7$。内点法内存爆炸。
• 建议：对于图像级任务，SDP 几乎只能用于处理特征点（稀疏数据）或超像素（Superpixels）。如果是密集像素任务，请出门左转看 第8章（原始-对偶） 或 第14章的 Burer-Monteiro 方法。

7.4 秩的数值陷阱

• 现象：理论说秩应该是 1，但数值解算出特征值是 [10.5, 0.001, 0.0001, -0.0001...]。
• 判断：这是正常的数值误差。只要主特征值显著大于第二特征值（Spectral Gap 很大），就可以认为实际上是秩-1 的。直接取第一主成分即可。