第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）。
本章学习目标：
- 几何直觉：理解半正定锥（PSD Cone）的几何形状，以及为什么它比多面体更“高级”。
- 建模能力：掌握“提升（Lifting）”技巧，将二次非凸问题转化为线性矩阵凸问题。
- 视觉场景：深入理解 SDP 在图割（Graph Cut）、旋转同步（Rotation Synchronization）和特征匹配中的应用。
- 求解策略：面对大规模视觉数据，如何跨越 $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}\)
性质：
- $G \succeq 0$。
- $G_{ii} = I_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. 线性约束}\)
- 性质：
- 非凸了：这就变回了一个非凸优化问题（定义在流形上）。
- 极快：变量数从 $n^2$ 降到了 $nk$。只需要做简单的梯度下降或黎曼流形梯度下降。
- 良态非凸 (Benign Non-convexity)：理论证明显示，对于许多视觉 SDP 问题（如同步、聚类），只要噪声不是特别大，这个非凸地貌没有虚假的局部最优解（Spurious Local Minima）。梯度下降能直接收敛到全局最优。
- 常用库：Manopt (Matlab), SE-Sync, Teaser++ (C++ 库核心算法)。
5. 本章小结
- 强力松弛：SDP 通过提升变量维度（$x \to X$），将离散的组合约束转化为连续的几何约束（半正定锥），提供了比线性规划更紧的界。
- 通用模板：大多数视觉二次问题都可以套用
Lifting -> Relaxing Constraints -> Rounding 的流程。
- Schur 补：是将非线性/分式项转化为 LMI 约束的瑞士军刀。
- 计算鸿沟：直接解 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 是对二次问题的“平均”松弛？
提示
利用 $\text{tr}(AB) = \text{tr}(BA)$。$\text{tr}(Q x x^T) = \text{tr}(x^T Q x)$，因为 $x^T Q x$ 是标量。
SDP 允许解 $X$ 的秩大于1，相当于允许解是多个可能向量 $v_i$ 的概率混合。
Q2. 对角约束的物理意义
在图割问题中，松弛变量 $X$ 满足 $X_{ii}=1$。
(a) 这对应于向量 $x$ 的什么几何约束？
(b) 如果去掉这个约束，只保留 $X \succeq 0$，对于最小化问题 $\min \langle L, X \rangle$ 会发生什么？
提示
(a) 对应 $x$ 位于单位超球面上（Spherical constraint）。对于二值问题 $x \in \{-1,1\}$，它必定位于球面上。
(b) 若去掉 $X_{ii}=1$，且 $L$ 半正定（如拉普拉斯矩阵），最优解将是 $X=0$（平凡解），没有任何意义。对角约束起到了“归一化”和防止解坍缩的作用。
Q3. Schur 补实战
将约束 $x^T x \le y z$ (其中 $y,z > 0$) 写成线性矩阵不等式 (LMI) 的形式。
提示
重写为 $y - x^T z^{-1} x \ge 0$ (假设 $z$ 为标量) 或利用 $M = \begin{bmatrix} yI & x \\ x^T & zI \end{bmatrix} \succeq 0$ (需调整系数)。
标准形式：$\begin{bmatrix} y & x^T \\ x & z \end{bmatrix} \succeq 0$ (当 $x$ 是标量)。如果 $x$ 是向量，需小心维度匹配。
挑战题
Q4. Max-Cut 的随机舍入 (Randomized Rounding)
著名的 Goemans-Williamson 算法是 SDP 史上的里程碑。
给定 SDP 最优解 $X^*$（秩可能不为1），如何生成二值解 $x \in {-1, 1}^n$？
算法步骤：
- 对 $X^$ 做 Cholesky 分解得 $X^ = V^T V$，其中 $V = [v_1, \dots, v_n]$ 是列向量。
- 随机选取一个单位向量 $r$（随机超平面）。
- 令 $x_i = \text{sign}(v_i^T r)$。
问题：请直观解释为什么 $v_i$ 和 $v_j$ 夹角越小，被切分到同一类的概率越大？
提示
$x_i$ 和 $x_j$ 符号相同意味着它们在随机超平面 $r$ 的同一侧。
两个向量夹角越小，中间被随机平面切开的概率就越低。概率与角度成正比 ($\text{Pr} \propto \arccos(v_i^T v_j)$)。
Q5. 紧度与对偶间隙 (Duality Gap)
在视觉应用中，怎么判断 SDP 得到的解是否就是原问题的最优解（Exact Recovery）？
如果是，矩阵 $X^*$ 应该具有什么秩？如果秩不满足要求，我们能相信这个解吗？
提示
如果 $\text{rank}(X^*) = 1$（对于向量问题）或 $\text{rank}(X^*) = d$（对于 $d$ 维几何问题），则松弛是紧的（Tight），我们得到了精确解。
如果秩过高，说明松弛失效（Gap > 0），此时解只是下界。但在同步问题中，通常只要 $X^*$ 的前 $d$ 个特征值显著大于其余特征值，就可以通过强行投影获得非常好的近似解。
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 的。直接取第一主成分即可。