半正定规划松弛

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

Max-Cut 例子 ​

对非负权 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$。

边界 ​

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

另一种用途不必把矩阵舍入成离散解。Lovász theta 函数理路Lovász theta 函数与零错误容量上界Lovász theta function · Lovász number用非邻点正交表示和单位柄向量证明容量上界，再给半正定原对偶及乘积证书，精确算出五边形的√5容量。通过非边正交表示与半正定原对偶，直接给所有块长的零错误码大小上界；五边形的显式几何与矩阵证书共同得到 $\sqrt{5}$。这里零位置和迹归一化不同于 Max-Cut，不能沿用单位对角约束。

另一个必须分清的接口是一元区间非负性理路Markov–Lukács 区间非负多项式证书Markov–Lukács theorem · Lukács interval positivity · 区间非负多项式的平方表示用带准确次数界的端点加权平方表示刻画整个实区间上的非负多项式，转成有限Gram恒等式，并认证可达到的全局最小值。：在非退化紧区间上，端点加权的两个PSD Gram矩阵与多项式非负严格等价。因此对 $p-\tau$ 配系数并最大化 $\tau$，得到可达到的真实最小值，而不是去掉某个秩约束后的松弛界。虽然定理也存在单平方表示，Gram可行域不必另加秩一约束；这个特定结论不能推广为任意多元平方和或任意SDP都无间隙。

Rank-one 原问题 ​

在上述 $n\ge 1$ 的符号二次模型中，原符号向量 $x$ 对应 $X=x{x}^{\mathrm{\top }}$，它 PSD、对角为 1 且 rank 1。反过来，满足这三项的矩阵可恢复一维单位向量，即符号解。这个实例唯一放松的是 rank 约束；一般 SDP 松弛还可能改变其他非凸约束。这个观察给出任何离散解都嵌入 SDP 可行域，因而最优值方向正确。

解矩阵到随机割的接口 ​

锥规划的对偶与证书理路锥规划的对偶与证书Conic programming certificates · Conic duality用对偶锥统一最优性与不可行性证书，并以二阶半正定规划区分零间隙、最优值可达和弱不可行。用迹内积构造半正定松弛的对偶界；核验原、对偶可行性后，目标差给出连续松弛的求解误差上界，舍入保证则仍需单独分析。

数值求解器返回的对称矩阵可能略微违反半正定或对角约束。可先做特征分解，将微小负特征值截为零，再由 Gram 分解取得向量；各向量范数非零时，将它们归一化为单位向量。修正后应核对可行残差，并把目标变化与求解误差计入近似保证。

取得 ${\mathbb{R}}^d$ 中的单位向量后，抽取联合标准高斯向量理路多元正态分布Multivariate normal distribution · Multivariate Gaussian distribution · Jointly Gaussian vector以所有线性组合都正态刻画联合高斯向量，并由特征函数连接线性构造、退化支撑、全维密度与条件分布。 $g\sim N_d(0,I_d)$，即各坐标独立服从标准正态分布，按 $\mathrm{sign}⟨g,v_i⟩$ 分边，就得到一个随机割。

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

再与 SDP 边贡献比较得到近似比理路近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。。独立重复舍入并保留最好结果可提高达到指定质量阈值的概率；重复次数取决于该阈值下的单次成功概率。

总算法成本还包括 SDP 求解、矩阵分解和 $O(n^2)$ 的稠密矩阵存储，以及每次舍入和评估割值的工作。