基于线性规划的图最大割问题的半定规划松弛与随机舍入算法求解示例

字数 4982 2025-12-11 00:09:32

基于线性规划的图最大割问题的半定规划松弛与随机舍入算法求解示例

1. 问题描述

我们考虑一个经典的最优化问题：最大割问题。

给定一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集（假设有 \(n\) 个顶点），\(E\) 是边集，每条边 \((i, j) \in E\) 有一个非负权重 \(w_{ij}\)。目标是找到一个将顶点集 \(V\) 划分成两个互不相交的子集 \(S\) 和 \(V \setminus S\) 的方法，使得连接两个子集的所有边（即“割”边）的权重之和最大化。

例如，一个社交网络可以建模为一个图，边的权重表示用户之间的连接强度。最大割问题可以用于识别两个差异性最大的社区。

2. 整数规划建模

我们首先将问题建模为一个二次整数规划。

引入决策变量 \(x_i \in \{-1, +1\}\)，对于每个顶点 \(i \in V\)：

\(x_i = +1\) 表示顶点 \(i\) 属于集合 \(S\)。
\(x_i = -1\) 表示顶点 \(i\) 属于集合 \(V \setminus S\)。

对于一条边 \((i, j)\)，如果 \(x_i \neq x_j\)，那么这条边就在割中，贡献权重 \(w_{ij}\)；如果 \(x_i = x_j\)，则贡献为 0。注意，当 \(x_i\) 和 \(x_j\) 的取值相反时，乘积 \(x_i x_j = -1\)；相同时，乘积 \(x_i x_j = +1\)。因此，边 \((i, j)\) 是否在割中可以用表达式 \(\frac{1 - x_i x_j}{2}\) 来精确刻画：

当 \(x_i x_j = -1\) 时，表达式值为 \(\frac{1 - (-1)}{2} = 1\)。
当 \(x_i x_j = +1\) 时，表达式值为 \(\frac{1 - 1}{2} = 0\)。

于是，最大割问题可以表示为如下二次整数规划：

\[\max \sum_{(i, j) \in E} w_{ij} \cdot \frac{1 - x_i x_j}{2} \]

\[ \text{s.t.} \quad x_i \in \{-1, +1\}, \quad \forall i \in V. \]

由于目标函数是求最大值，且 \(w_{ij} \ge 0\)，\(\frac{1 - x_i x_j}{2}\) 非负，这确实是在最大化割边的总权重。

3. 半定规划松弛

二次整数规划通常是 NP 难的。我们通过一个巧妙的变量变换将其转化为一个更容易处理的问题。

3.1 变量变换
引入一个新的 \(n \times n\) 的对称矩阵 \(Y\)，其元素 \(y_{ij} = x_i x_j\)。注意，\(x_i \in \{-1, +1\}\)，因此：

对角线元素 \(y_{ii} = x_i^2 = 1\)。
矩阵 \(Y\) 可以表示为向量 \(\mathbf{x} = (x_1, \dots, x_n)^T\) 的外积：\(Y = \mathbf{x} \mathbf{x}^T\)。
\(Y\) 是秩为 1 的对称半正定矩阵。

于是，原目标函数可以重新写成：

\[\max \frac{1}{2} \sum_{(i, j) \in E} w_{ij} (1 - y_{ij})。 \]

3.2 松弛条件
原问题中 \(Y = \mathbf{x} \mathbf{x}^T\) 有两个关键性质：

\(Y \succeq 0\)（半正定）。
\(\text{diag}(Y) = \mathbf{1}\)（对角线元素全为 1）。
\(\text{rank}(Y) = 1\)。

条件 3 是使得问题难解的核心。半定规划松弛 的核心思想是：去掉这个秩为 1 的约束，只保留前两个条件。于是我们得到如下半定规划问题：

\[\begin{aligned} \text{(SDP)} \quad & \max \frac{1}{2} \sum_{(i, j) \in E} w_{ij} (1 - y_{ij}) \\ \text{s.t.} \quad & y_{ii} = 1, \quad \forall i \in V, \\ & Y \succeq 0. \end{aligned} \]

这里 \(Y \succeq 0\) 表示 \(Y\) 是半正定矩阵（即所有特征值非负）。这是一个凸优化问题，可以在多项式时间内求解（例如，使用内点法）。

设 SDP 的最优目标值为 \(\text{OPT}_{\text{SDP}}\)，而原整数规划的最优值为 \(\text{OPT}_{\text{IP}}\)。由于我们放松了约束，所以有 \(\text{OPT}_{\text{SDP}} \ge \text{OPT}_{\text{IP}}\)。

4. 随机舍入算法

得到半定规划的最优解矩阵 \(Y^*\) 后，我们需要将其转换回一个可行的割划分。由于 \(Y^*\) 是半正定的，它可以进行 Cholesky 分解（或等价地，利用其特征向量）得到一组向量表示。

4.1 从矩阵到向量
因为 \(Y^* \succeq 0\)，存在一个矩阵 \(V \in \mathbb{R}^{n \times n}\) 使得 \(Y^* = V^T V\)。记 \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n \in \mathbb{R}^n\) 为 \(V\) 的列向量（或行向量，取决于分解方式，不影响结果），则有 \(y_{ij}^* = \mathbf{v}_i \cdot \mathbf{v}_j\)。并且，由于 \(y_{ii}^* = 1\)，这些向量都是单位向量：\(\|\mathbf{v}_i\| = 1\)。

这些单位向量位于一个高维单位球面上。我们的目标是将其映射回 \(\{-1, +1\}\) 的决策。

4.2 随机超平面舍入法
经典的随机舍入策略由 Goemans 和 Williamson 提出：

随机均匀地选取一个单位向量 \(\mathbf{r} \in \mathbb{R}^n\)（即从 \(n\) 维单位球面上均匀随机采样）。
对于每个顶点 \(i\)，根据向量 \(\mathbf{v}_i\) 与 \(\mathbf{r}\) 的点积符号决定其划分：

\[ x_i' = \operatorname{sign}(\mathbf{v}_i \cdot \mathbf{r}) = \begin{cases} +1, & \text{if } \mathbf{v}_i \cdot \mathbf{r} \ge 0, \\ -1, & \text{if } \mathbf{v}_i \cdot \mathbf{r} < 0. \end{cases} \]

由此得到的 \((S, V \setminus S)\) 即为一个割划分。

4.3 性能分析（期望近似比）
我们需要分析这个随机割的期望权重。对于任意一条边 \((i, j)\)，它在割中的概率是多少？

边 \((i, j)\) 在割中当且仅当 \(\operatorname{sign}(\mathbf{v}_i \cdot \mathbf{r}) \neq \operatorname{sign}(\mathbf{v}_j \cdot \mathbf{r})\)。
几何上，这等价于随机超平面（法向量为 \(\mathbf{r}\)）将向量 \(\mathbf{v}_i\) 和 \(\mathbf{v}_j\) 分到了不同的半空间。
已知两个单位向量 \(\mathbf{v}_i\) 和 \(\mathbf{v}_j\) 之间的夹角为 \(\theta_{ij}\)，其中 \(\cos \theta_{ij} = \mathbf{v}_i \cdot \mathbf{v}_j = y_{ij}^*\)。
随机超平面将两个向量分开的概率正好与它们的夹角成正比。具体地：

\[ \Pr[(i, j) \text{ 在割中}] = \frac{\theta_{ij}}{\pi}。 \]

利用恒等式 \(\theta_{ij} = \arccos(y_{ij}^*)\)，我们有：

\[ \Pr[(i, j) \text{ 在割中}] = \frac{\arccos(y_{ij}^*)}{\pi}。 \]

4.4 与 SDP 目标的关系
SDP 目标中边 \((i, j)\) 的贡献是 \(\frac{1}{2} w_{ij} (1 - y_{ij}^*)\)。在随机舍入中，边 \((i, j)\) 对期望权重的贡献是 \(w_{ij} \cdot \frac{\arccos(y_{ij}^*)}{\pi}\)。

为了比较，我们考虑比值：

\[\alpha(y) = \frac{\frac{\arccos(y)}{\pi}}{\frac{1}{2}(1 - y)} \quad \text{for } y \in [-1, 1]。 \]

对于每条边，其实际贡献与 SDP 贡献之比的下界决定了算法的近似比。通过分析函数 \(\alpha(y)\) 在区间 \([-1, 1]\) 上的最小值，Goemans 和 Williamson 证明了：

\[\alpha(y) \ge \alpha^* \approx 0.87856。 \]

也就是说，对于每条边，有

\[w_{ij} \cdot \frac{\arccos(y_{ij}^*)}{\pi} \ge 0.87856 \cdot \frac{1}{2} w_{ij} (1 - y_{ij}^*)。 \]

将所有边累加，得到随机割的期望权重：

\[\mathbb{E}[\text{割的权重}] \ge 0.87856 \cdot \text{OPT}_{\text{SDP}} \ge 0.87856 \cdot \text{OPT}_{\text{IP}}。 \]

因此，该随机舍入算法是一个期望近似比为 0.878 的近似算法。这是最大割问题目前最好的近似算法之一（在 P ≠ NP 的假设下，不存在近似比优于 0.941 的多项式时间算法）。

5. 总结步骤

建模：将最大割问题表达为二次整数规划。
松弛：通过变量替换和去掉秩约束，将其松弛为一个半定规划。
求解 SDP：使用内点法等凸优化算法在多项式时间内求解 SDP，得到最优解矩阵 \(Y^*\)。
向量分解：对 \(Y^*\) 进行 Cholesky 分解，得到一组单位向量 \(\{\mathbf{v}_i\}\)。
随机舍入：随机选取一个超平面法向量 \(\mathbf{r}\)，根据 \(\operatorname{sign}(\mathbf{v}_i \cdot \mathbf{r})\) 将顶点划分为两个集合。
理论保证：算法产生的割的期望权重至少是原问题最优解的 0.878 倍。

这个示例展示了如何将组合优化问题（最大割）通过半定规划松弛和随机舍入，转化为具有理论性能保证的近似算法。它体现了线性/凸规划松弛与概率方法结合的强大能力。

基于线性规划的图最大割问题的半定规划松弛与随机舍入算法求解示例 1. 问题描述我们考虑一个经典的最优化问题：最大割问题。给定一个无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集（假设有 \( n \) 个顶点），\( E \) 是边集，每条边 \( (i, j) \in E \) 有一个非负权重 \( w_ {ij} \)。目标是找到一个将顶点集 \( V \) 划分成两个互不相交的子集 \( S \) 和 \( V \setminus S \) 的方法，使得连接两个子集的所有边（即“割”边）的权重之和最大化。例如，一个社交网络可以建模为一个图，边的权重表示用户之间的连接强度。最大割问题可以用于识别两个差异性最大的社区。 2. 整数规划建模我们首先将问题建模为一个二次整数规划。引入决策变量 \( x_ i \in \{-1, +1\} \)，对于每个顶点 \( i \in V \)： \( x_ i = +1 \) 表示顶点 \( i \) 属于集合 \( S \)。 \( x_ i = -1 \) 表示顶点 \( i \) 属于集合 \( V \setminus S \)。对于一条边 \( (i, j) \)，如果 \( x_ i \neq x_ j \)，那么这条边就在割中，贡献权重 \( w_ {ij} \)；如果 \( x_ i = x_ j \)，则贡献为 0。注意，当 \( x_ i \) 和 \( x_ j \) 的取值相反时，乘积 \( x_ i x_ j = -1 \)；相同时，乘积 \( x_ i x_ j = +1 \)。因此，边 \( (i, j) \) 是否在割中可以用表达式 \( \frac{1 - x_ i x_ j}{2} \) 来精确刻画：当 \( x_ i x_ j = -1 \) 时，表达式值为 \( \frac{1 - (-1)}{2} = 1 \)。当 \( x_ i x_ j = +1 \) 时，表达式值为 \( \frac{1 - 1}{2} = 0 \)。于是，最大割问题可以表示为如下二次整数规划： \[ \max \sum_ {(i, j) \in E} w_ {ij} \cdot \frac{1 - x_ i x_ j}{2} \] \[ \text{s.t.} \quad x_ i \in \{-1, +1\}, \quad \forall i \in V. \] 由于目标函数是求最大值，且 \( w_ {ij} \ge 0 \)，\( \frac{1 - x_ i x_ j}{2} \) 非负，这确实是在最大化割边的总权重。 3. 半定规划松弛二次整数规划通常是 NP 难的。我们通过一个巧妙的变量变换将其转化为一个更容易处理的问题。 3.1 变量变换引入一个新的 \( n \times n \) 的对称矩阵 \( Y \)，其元素 \( y_ {ij} = x_ i x_ j \)。注意，\( x_ i \in \{-1, +1\} \)，因此：对角线元素 \( y_ {ii} = x_ i^2 = 1 \)。矩阵 \( Y \) 可以表示为向量 \( \mathbf{x} = (x_ 1, \dots, x_ n)^T \) 的外积：\( Y = \mathbf{x} \mathbf{x}^T \)。 \( Y \) 是秩为 1 的对称半正定矩阵。于是，原目标函数可以重新写成： \[ \max \frac{1}{2} \sum_ {(i, j) \in E} w_ {ij} (1 - y_ {ij})。 \] 3.2 松弛条件原问题中 \( Y = \mathbf{x} \mathbf{x}^T \) 有两个关键性质： \( Y \succeq 0 \)（半正定）。 \( \text{diag}(Y) = \mathbf{1} \)（对角线元素全为 1）。 \( \text{rank}(Y) = 1 \)。条件 3 是使得问题难解的核心。半定规划松弛的核心思想是：去掉这个秩为 1 的约束，只保留前两个条件。于是我们得到如下半定规划问题： \[ \begin{aligned} \text{(SDP)} \quad & \max \frac{1}{2} \sum_ {(i, j) \in E} w_ {ij} (1 - y_ {ij}) \\ \text{s.t.} \quad & y_ {ii} = 1, \quad \forall i \in V, \\ & Y \succeq 0. \end{aligned} \] 这里 \( Y \succeq 0 \) 表示 \( Y \) 是半正定矩阵（即所有特征值非负）。这是一个凸优化问题，可以在多项式时间内求解（例如，使用内点法）。设 SDP 的最优目标值为 \( \text{OPT} {\text{SDP}} \)，而原整数规划的最优值为 \( \text{OPT} {\text{IP}} \)。由于我们放松了约束，所以有 \( \text{OPT} {\text{SDP}} \ge \text{OPT} {\text{IP}} \)。 4. 随机舍入算法得到半定规划的最优解矩阵 \( Y^* \) 后，我们需要将其转换回一个可行的割划分。由于 \( Y^* \) 是半正定的，它可以进行 Cholesky 分解（或等价地，利用其特征向量）得到一组向量表示。 4.1 从矩阵到向量因为 \( Y^* \succeq 0 \)，存在一个矩阵 \( V \in \mathbb{R}^{n \times n} \) 使得 \( Y^* = V^T V \)。记 \( \mathbf{v}_ 1, \mathbf{v}_ 2, \dots, \mathbf{v} n \in \mathbb{R}^n \) 为 \( V \) 的列向量（或行向量，取决于分解方式，不影响结果），则有 \( y {ij}^* = \mathbf{v}_ i \cdot \mathbf{v} j \)。并且，由于 \( y {ii}^* = 1 \)，这些向量都是单位向量：\( \|\mathbf{v}_ i\| = 1 \)。这些单位向量位于一个高维单位球面上。我们的目标是将其映射回 \( \{-1, +1\} \) 的决策。 4.2 随机超平面舍入法经典的随机舍入策略由 Goemans 和 Williamson 提出：随机均匀地选取一个单位向量 \( \mathbf{r} \in \mathbb{R}^n \)（即从 \( n \) 维单位球面上均匀随机采样）。对于每个顶点 \( i \)，根据向量 \( \mathbf{v}_ i \) 与 \( \mathbf{r} \) 的点积符号决定其划分： \[ x_ i' = \operatorname{sign}(\mathbf{v}_ i \cdot \mathbf{r}) = \begin{cases} +1, & \text{if } \mathbf{v}_ i \cdot \mathbf{r} \ge 0, \\ -1, & \text{if } \mathbf{v}_ i \cdot \mathbf{r} < 0. \end{cases} \] 由此得到的 \( (S, V \setminus S) \) 即为一个割划分。 4.3 性能分析（期望近似比）我们需要分析这个随机割的期望权重。对于任意一条边 \( (i, j) \)，它在割中的概率是多少？边 \( (i, j) \) 在割中当且仅当 \( \operatorname{sign}(\mathbf{v}_ i \cdot \mathbf{r}) \neq \operatorname{sign}(\mathbf{v}_ j \cdot \mathbf{r}) \)。几何上，这等价于随机超平面（法向量为 \( \mathbf{r} \)）将向量 \( \mathbf{v}_ i \) 和 \( \mathbf{v}_ j \) 分到了不同的半空间。已知两个单位向量 \( \mathbf{v} i \) 和 \( \mathbf{v} j \) 之间的夹角为 \( \theta {ij} \)，其中 \( \cos \theta {ij} = \mathbf{v}_ i \cdot \mathbf{v} j = y {ij}^* \)。随机超平面将两个向量分开的概率正好与它们的夹角成正比。具体地： \[ \Pr[ (i, j) \text{ 在割中}] = \frac{\theta_ {ij}}{\pi}。 \] 利用恒等式 \( \theta_ {ij} = \arccos(y_ {ij}^ ) \)，我们有： \[ \Pr[ (i, j) \text{ 在割中}] = \frac{\arccos(y_ {ij}^ )}{\pi}。 \] 4.4 与 SDP 目标的关系 SDP 目标中边 \( (i, j) \) 的贡献是 \( \frac{1}{2} w_ {ij} (1 - y_ {ij}^ ) \)。在随机舍入中，边 \( (i, j) \) 对期望权重的贡献是 \( w_ {ij} \cdot \frac{\arccos(y_ {ij}^ )}{\pi} \)。为了比较，我们考虑比值： \[ \alpha(y) = \frac{\frac{\arccos(y)}{\pi}}{\frac{1}{2}(1 - y)} \quad \text{for } y \in [ -1, 1 ]。 \] 对于每条边，其实际贡献与 SDP 贡献之比的下界决定了算法的近似比。通过分析函数 \( \alpha(y) \) 在区间 \([ -1, 1 ]\) 上的最小值，Goemans 和 Williamson 证明了： \[ \alpha(y) \ge \alpha^* \approx 0.87856。 \] 也就是说，对于每条边，有 \[ w_ {ij} \cdot \frac{\arccos(y_ {ij}^ )}{\pi} \ge 0.87856 \cdot \frac{1}{2} w_ {ij} (1 - y_ {ij}^ )。 \] 将所有边累加，得到随机割的期望权重： \[ \mathbb{E}[ \text{割的权重}] \ge 0.87856 \cdot \text{OPT} {\text{SDP}} \ge 0.87856 \cdot \text{OPT} {\text{IP}}。 \] 因此，该随机舍入算法是一个期望近似比为 0.878 的近似算法。这是最大割问题目前最好的近似算法之一（在 P ≠ NP 的假设下，不存在近似比优于 0.941 的多项式时间算法）。 5. 总结步骤建模：将最大割问题表达为二次整数规划。松弛：通过变量替换和去掉秩约束，将其松弛为一个半定规划。求解 SDP ：使用内点法等凸优化算法在多项式时间内求解 SDP，得到最优解矩阵 \( Y^* \)。向量分解：对 \( Y^* \) 进行 Cholesky 分解，得到一组单位向量 \( \{\mathbf{v}_ i\} \)。随机舍入：随机选取一个超平面法向量 \( \mathbf{r} \)，根据 \( \operatorname{sign}(\mathbf{v}_ i \cdot \mathbf{r}) \) 将顶点划分为两个集合。理论保证：算法产生的割的期望权重至少是原问题最优解的 0.878 倍。这个示例展示了如何将组合优化问题（最大割）通过半定规划松弛和随机舍入，转化为具有理论性能保证的近似算法。它体现了线性/凸规划松弛与概率方法结合的强大能力。