半正定规划(SDP)在Max-Cut近似算法中的松弛与随机舍入

定义Max-Cut问题并构建整数规划

1. 描述问题：给定一个无向图 G = (V, E)，每条边 (i, j) 有权重 w_{ij}（通常为非负）。Max-Cut的目标是将顶点集 V 分割成两个部分 S 和 V \ S，使得两端分别位于不同部分的边的权重之和最大。这是一个经典的NP-难组合优化问题。

2. 建立整数规划模型：为每个顶点 i 引入一个变量 x_i \in \{+1, -1\}，其中 x_i = +1 表示顶点 i 属于集合 S，x_i = -1 表示属于补集。那么，边 (i, j) 被割开的条件是 x_i \neq x_j，即 x_i x_j = -1。因此，割的权重可以用公式表示为：
   $$ \frac{1}{2} \sum_{(i,j) \in E} w_{ij} (1 - x_i x_j) $$
   因为当 x_i x_j = -1 时，(1 - x_i x_j) = 2，再乘 1/2 得 w_{ij}；当 x_i x_j = 1 时为0。于是，Max-Cut等价于：
   $$ \max \frac{1}{2} \sum_{i<j} w_{ij} (1 - x_i x_j) \quad \text{s.t.} \quad x_i \in \{+1, -1\}, \; \forall i $$

将整数规划松弛为半正定规划（SDP）

1. 观察目标函数：它依赖于 x_i x_j 的乘积。将标量 x_i 替换为向量 v_i \in \mathbb{R}^n（n = |V|），并令 v_i \cdot v_j 代替 x_i x_j。约束 x_i \in \{+1, -1\} 等价于 x_i^2 = 1，在向量版本中变为 \|v_i\|_2^2 = 1。于是得到向量规划：
   $$ \max \frac{1}{2} \sum_{(i,j)} w_{ij} (1 - v_i \cdot v_j) \quad \text{s.t.} \quad \|v_i\|_2^2 = 1, \; \forall i $$

2. 转化为标准SDP：定义矩阵 Y 为所有 v_i 之间的内积矩阵，即 Y_{ij} = v_i \cdot v_j。那么 Y 是对称的、半正定的（因为它是Gram矩阵），且对角线元素 Y_{ii}=1。目标函数变为：
   $$ \frac{1}{2} \sum_{i,j} w_{ij} (1 - Y_{ij}) = \frac{1}{2} \sum_{i,j} w_{ij} - \frac{1}{2} \sum_{i,j} w_{ij} Y_{ij} $$
   其中第一个求和是常数（所有边的总权重和 W_total），因此最大化原目标等价于最小化 \sum_{i,j} w_{ij} Y_{ij}。最终SDP形式为：
   $$ \begin{aligned} \text{minimize} & \quad \sum_{(i,j)} w_{ij} Y_{ij} \\ \text{subject to} & \quad Y_{ii} = 1, \quad \forall i \\ & \quad Y \succeq 0 \quad (\text{半正定}) \end{aligned} $$
   实际应用中，我们直接求解这个SDP，获得最优解 Y^* 以及对应的向量表示 \{v_i\}。

通过随机舍入将SDP解转化为可行割

1. 提取向量表示：从SDP解 Y^* 中分解出向量 v_i \in \mathbb{R}^n，满足 \|v_i\|=1 且 v_i \cdot v_j = Y^*_{ij}。这可以通过Cholesky分解或特征值分解完成。

2. 随机超平面舍入：生成一个随机单位向量 r \in \mathbb{R}^n（均匀分布在单位球面上）。对于每个顶点 i，计算点积 v_i \cdot r。如果 v_i \cdot r \geq 0，则将 i 归入 S 集合（x_i = +1）；否则归入补集（x_i = -1）。这个过程等价于用一个随机超平面（法向量为 r，过原点）将单位球面分成两半。

3. 解释概率：由于 v_i 和 v_j 都是单位向量，随机超平面分割它们的概率只取决于它们之间的夹角 \theta_{ij} = \arccos(v_i \cdot v_j)。具体地，两个顶点被分到不同侧的概率为 \theta_{ij} / \pi。因此，边 (i,j) 被割开的期望贡献为 w_{ij} \cdot (\theta_{ij} / \pi)。

4. 计算期望割值：随机算法的期望割大小为：
   $$ E[\text{cut}] = \sum_{(i,j)} w_{ij} \cdot \frac{\theta_{ij}}{\pi} $$
   注意 \theta_{ij} = \arccos(Y_{ij})，其中 Y_{ij} 来自SDP最优解。

分析近似比：证明0.87856-近似

1. 关键不等式：对于任意 t \in [-1, 1]，令 \theta = \arccos(t)，则恒有：
   $$ \frac{\theta}{\pi} \geq \alpha \cdot \frac{1 - t}{2} $$
   其中常数 \alpha = \min_{t \in [-1,1]} \frac{2\theta}{\pi (1-t)} \approx 0.87856。该最小值在 t = -1 附近达到（严格来说 t = -0.689 左右？经典结果为 t 使 \frac{2\theta}{\pi (1-t)} 取最小值，数值约为0.87856）。实际上Goemans-Williamson使用 \alpha \approx 0.878567。

2. 联系SDP目标：回顾SDP最小化目标是 \sum w_{ij} Y_{ij}，而最优割的整数解对应的目标表达式为 \frac{1 - x_i x_j}{2}。对于最优整数解 x^*，我们有：
   $$ \text{OPT} = \frac{1}{2} \sum w_{ij} (1 - x_i^* x_j^*) $$
   而SDP松弛的可行域更大，所以SDP最优值 SDP^* = \min \sum w_{ij} Y_{ij} 满足 \sum w_{ij} Y_{ij}^* \leq \sum w_{ij} (x_i^* x_j^*)。但注意这里的符号：SDP最小化，整数也对应某个 x_i x_j 值，所以 SDP^* 不大于整数对应的 \sum w_{ij} (x_i^* x_j^*)。

3. 推导期望近似比：
   $$ \begin{aligned} E[\text{cut}] &= \sum w_{ij} \frac{\theta_{ij}}{\pi} \\ &\geq \alpha \cdot \sum w_{ij} \frac{1 - Y_{ij}^*}{2} \quad (\text{代入不等式}) \\ &= \alpha \cdot \left( \frac{1}{2} \sum w_{ij} - \frac{1}{2} \sum w_{ij} Y_{ij}^* \right) \\ &= \alpha \cdot \frac{1}{2} \sum w_{ij} - \frac{\alpha}{2} \cdot SDP^* \\ &\geq \alpha \cdot \frac{1}{2} \sum w_{ij} - \frac{\alpha}{2} \cdot \sum w_{ij} (x_i^* x_j^*) \quad (\text{因为 }SDP^* \leq \sum w_{ij} (x_i^* x_j^*)) \\ &= \alpha \cdot \frac{1}{2} \sum w_{ij} (1 - x_i^* x_j^*) \\ &= \alpha \cdot \text{OPT} \end{aligned} $$
   因此，随机舍入算法保证期望割值至少为最优值的 \alpha \approx 0.878 倍。这是目前理论上最好的常数近似比（除非 P=NP，否则无法改进到 \alpha + \epsilon 以上）。

4. 执行输出：运行一次随机舍入可能得到较差结果，但可以 重复多次（例如 O(n^2) 次）并 选取 其中最大的割值，这样能以高概率得到近似比为 \alpha - o(1) 的解。实际实现中，只需取若干次随机超平面，挑一个最优即可。