半正定规划松弛

离散符号只能取一条直线的两个方向，SDP 允许它们展开成球面上的向量，并用内积保留成对相关性。去掉 rank-one 条件扩大可行域，Gram 矩阵的半正定约束又让这份几何放松保持凸性；舍入再把角度关系变回离散选择。

Max-Cut 例子 ​

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

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 的期望舍入值可以逐边写成

再与 SDP 边贡献比较得到近似比公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。。这里只给一个随机割；要高概率得到接近期望的最好割，可独立重复舍入并取目标值最大者。

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