半正定规划松弛

从符号到向量 ​

许多二次离散问题有 $x_i\in \{-1,+1\}$ 和乘积 $x_i{x}_j$。把每个符号换成单位向量 $v_i$，乘积换成内积 $⟨v_i,v_j⟩$；令半正定 Gram 矩阵公理库正定与半正定矩阵Positive definite matrix · Positive semidefinite matrix · PSD matrix由二次能量严格为正或非负定义的实对称与复 Hermitian 矩阵。 $X_{ij}=⟨v_i,v_j⟩$，约束等价为

$$X⪰0,X_{ii}=1.$$

去掉 rank-one 条件 $X=x{x}^{\mathrm{\top }}$ 后可行域变大且凸；最大化问题的 SDP 最优值是原最优值上界，最小化方向相反。

Max-Cut 例子 ​

符号表示割两侧，边 $(i,j)$ 被切开指标为

$$\frac{1-x_i{x}_j}{2}.$$

SDP 把它改为 $(1-⟨v_i,v_j⟩)/2$。随机取过原点超平面，以向量落在哪侧决定符号；两向量被分开的概率是夹角除以 $\pi$，比较该概率与 SDP 边贡献得到 Goemans–Williamson 比率。

几何与数值接口 ​

$X⪰0$ 表示所有向量 $z$ 有 $z^{\mathrm{\top }}Xz\ge 0$，不是每个元素都非负；负内积正是表达相反割侧。任意 PSD 矩阵都有 Gram 分解，向量维数可取 rank$(X)\le n$。实际算法只能近似求 SDP，目标精度和可行残差需留进最终近似误差。

边界 ​

松弛值本身不是离散解，必须给舍入及其期望/高概率分析。不同 min/max 问题的上、下界方向不能照抄。LP 松弛只保留标量线性约束，SDP 额外保留成对相关几何；代价是求解更重，并非所有问题都获得更好 integrality gap。

Rank-one 原问题 ​

原符号向量 $x$ 对应 $X=x{x}^{\mathrm{\top }}$，它 PSD、对角为 1 且 rank 1。反过来，满足这三项的矩阵可恢复一维单位向量，即符号解；SDP 唯一放松的是 rank 约束。这个观察给出任何离散解都嵌入 SDP 可行域，因而最优值方向正确。

随机超平面舍入需要从 Gram 分解得到向量。数值矩阵若有微小负特征值，应先投影/容差处理并量化目标变化，不能把不精确 PSD 当作严格可行证书。

解矩阵到随机割的接口 ​

数值求解器返回近似 PSD 矩阵 $X$ 后，先做特征分解或 Cholesky 型分解得到向量 $v_i$，再抽随机高斯向量 $g$，按 $\mathrm{sign}⟨g,v_i⟩$ 分边。两个向量夹角为 $\theta$ 时，被随机超平面分开的概率是 $\theta /\pi$。

因此 Max-Cut 的期望舍入值可以逐边写成

$$\sum _{(i,j)}{w}_{ij}\frac{\arccos ⟨v_i,v_j⟩}{\pi },$$

再与 SDP 边贡献比较得到近似比。这里只给一个随机割；要高概率得到接近期望的最好割，可独立重复舍入并取目标值最大者。

浮点解可能轻微违反 $X⪰0$ 或 $X_{ii}=1$，实现需投影、归一化并记录容差。SDP 求解时间和矩阵 $O(n^2)$ 存储也是总算法成本，不能只报告舍入的线性扫描。

参考资料

• Michel Goemans, David Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, JACM, 1995.
• Yurii Nesterov, Semidefinite Relaxation and Nonconvex Quadratic Optimization, Optimization Methods and Software, 1998.