基于线性规划的顶点加权最大团问题的半定规划松弛与随机舍入算法求解示例
字数 6381 2025-12-11 16:00:19

基于线性规划的顶点加权最大团问题的半定规划松弛与随机舍入算法求解示例

我来为您讲解这个关于线性规划及其相关算法在组合优化问题中的一个应用。

问题描述

顶点加权最大团问题（Maximum Weight Clique Problem, MWCP）：给定一个无向图 \(G = (V, E)\)，其中每个顶点 \(v \in V\) 有一个非负权重 \(w_v\)。一个“团”是指顶点集的一个子集 \(C \subseteq V\)，使得 \(C\) 中任意两个顶点之间都有一条边（即 \(C\) 的导出子图是完全图）。目标是找到一个团 \(C\)，使得其总权重 \(\sum_{v \in C} w_v\) 达到最大。

这个问题是经典的最大团问题的推广（当所有权重为1时即为最大团问题）。最大团问题是NP-难问题，因此MWCP也是NP-难的。我们无法在多项式时间内求出精确最优解（除非P=NP）。在这里，我们将探讨如何利用半定规划（Semidefinite Programming, SDP）松弛和随机舍入（Randomized Rounding） 技术，设计一个近似算法来获得一个质量有理论保证的近似解。

解题步骤详解

步骤1：整数二次规划（Integer Quadratic Programming, IQP）建模

首先，我们需要将MWCP表示成一个数学优化模型。为每个顶点 \(v\) 引入一个0-1决策变量 \(x_v\)：

  • \(x_v = 1\) 表示顶点 \(v\) 被选入团 \(C\)。
  • \(x_v = 0\) 表示顶点 \(v\) 未被选入。

团的定义要求：对于图中每一对不相邻的顶点 \((u, v) \notin E\)，它们不能同时被选中（即 \(x_u\) 和 \(x_v\) 不能同时为1）。这可以表示为约束 \(x_u + x_v \leq 1\)。对于相邻的顶点则无此限制。

因此，MWCP可以建模为以下整数二次规划（实际上是一个线性整数规划，因为约束和目标都是线性的，但通常为了后续松弛，我们采用另一种等价形式）：

\[\begin{aligned} \text{最大化:} & \sum_{v \in V} w_v x_v \\ \text{满足:} & x_u + x_v \leq 1, \quad \forall (u, v) \notin E \\ & x_v \in \{0, 1\}, \quad \forall v \in V \end{aligned} \]

然而，为了应用更强大的半定规划松弛，我们采用一个等价的二次整数规划形式。考虑向量 \(\mathbf{v}_v \in \mathbb{R}^n\)（其中 \(n = |V|\)），并令 \(x_v = \frac{1 + \mathbf{v}_0 \cdot \mathbf{v}_v}{2}\)，其中我们引入一个额外的单位向量 \(\mathbf{v}_0\)，并且要求所有向量 \(\mathbf{v}_0, \mathbf{v}_v\) 都是单位向量（即 \(\|\mathbf{v}\|_2 = 1\)）。在这种表示下：

  • \(x_v = 1\) 对应于 \(\mathbf{v}_0 \cdot \mathbf{v}_v = 1\)（即 \(\mathbf{v}_v = \mathbf{v}_0\)）。
  • \(x_v = 0\) 对应于 \(\mathbf{v}_0 \cdot \mathbf{v}_v = -1\)（即 \(\mathbf{v}_v = -\mathbf{v}_0\)）。

不相邻顶点 \(u, v\) 不能同时被选中的约束 \(x_u + x_v \leq 1\) 可以转化为：

\[\frac{1 + \mathbf{v}_0 \cdot \mathbf{v}_u}{2} + \frac{1 + \mathbf{v}_0 \cdot \mathbf{v}_v}{2} \leq 1 \implies \mathbf{v}_0 \cdot \mathbf{v}_u + \mathbf{v}_0 \cdot \mathbf{v}_v \leq 0. \]

目标函数为 \(\sum_v w_v \frac{1 + \mathbf{v}_0 \cdot \mathbf{v}_v}{2}\)。最大化此目标等价于最大化 \(\sum_v w_v (\mathbf{v}_0 \cdot \mathbf{v}_v)\)。

因此，我们得到等价的向量形式整数规划：

\[\begin{aligned} \text{最大化:} & \sum_{v \in V} w_v (\mathbf{v}_0 \cdot \mathbf{v}_v) \\ \text{满足:} & \mathbf{v}_0 \cdot \mathbf{v}_u + \mathbf{v}_0 \cdot \mathbf{v}_v \leq 0, \quad \forall (u, v) \notin E \\ & \|\mathbf{v}_0\| = 1, \quad \|\mathbf{v}_v\| = 1, \quad \forall v \in V \\ & \mathbf{v}_v \in \mathbb{R}^{n+1}, \quad \forall v \in \{0\} \cup V. \end{aligned} \]

这仍然是一个难解的问题。

步骤2：半定规划（SDP）松弛

半定规划松弛的核心思想是将“每个变量是一个单位向量”的条件，转化为一个关于向量内积的矩阵条件。

我们构造一个对称矩阵 \(Y\)，其行和列对应索引 \(0, 1, 2, ..., n\)（其中索引0对应 \(\mathbf{v}_0\)，索引 \(i\) 对应顶点 \(v_i\)）。定义 \(Y_{ij} = \mathbf{v}_i \cdot \mathbf{v}_j\)（内积）。矩阵 \(Y\) 被称为Gram矩阵，它具有以下关键性质：

  1. \(Y\) 是半正定（Positive Semidefinite, PSD） 的，记作 \(Y \succeq 0\)。
  2. 由于每个向量是单位向量，所以 \(Y_{ii} = \mathbf{v}_i \cdot \mathbf{v}_i = 1\) 对所有 \(i\) 成立。

现在，用矩阵 \(Y\) 的元素重写我们的问题：

  • 目标函数：\(\sum_{v} w_v (\mathbf{v}_0 \cdot \mathbf{v}_v) = \sum_{i=1}^{n} w_i Y_{0i}\)。
  • 约束 \(\mathbf{v}_0 \cdot \mathbf{v}_u + \mathbf{v}_0 \cdot \mathbf{v}_v \leq 0\) 变为：\(Y_{0u} + Y_{0v} \leq 0\)。

于是，我们得到了MWCP的半定规划松弛：

\[\begin{aligned} \text{最大化:} & \sum_{i=1}^{n} w_i Y_{0i} \\ \text{满足:} & Y_{0u} + Y_{0v} \leq 0, \quad \forall (u, v) \notin E \\ & Y_{ii} = 1, \quad \forall i \in \{0, 1, ..., n\} \\ & Y \succeq 0, \quad Y \text{ 是对称矩阵}. \end{aligned} \]

为什么这是“松弛”？
在原整数规划中，我们要求 \(Y_{ij} = \mathbf{v}_i \cdot \mathbf{v}_j\)，并且每个 \(\mathbf{v}_i\) 是单位向量。这隐含了一个更强的条件：矩阵 \(Y\) 的秩必须为1（因为它可以分解为 \(Y = \mathbf{v}^T \mathbf{v}\)，其中 \(\mathbf{v}\) 是拼接所有向量的行向量）。在半定规划中，我们移除了“秩为1”这个约束，只保留了 \(Y \succeq 0\) 和 \(Y_{ii}=1\)。可行解集变大了，因此最优值 \(SDP^*\) 是原问题最优值 \(OPT\) 的一个上界（即 \(SDP^* \geq OPT\)）。

步骤3：求解半定规划

半定规划属于凸优化范畴，可以在多项式时间内（精确或任意精度近似地）求解。有成熟的内点法算法和软件包（如SeDuMi, SDPA, CVX等）可以用于求解此SDP模型。我们假设通过求解器得到了最优解矩阵 \(Y^*\)。

步骤4：随机舍入（Goemans-Williamson风格）

得到半正定矩阵 \(Y^*\) 后，我们需要将它“舍入”成一个合法的团（即0-1解）。这里我们采用经典的随机超平面舍入技术。

  1. Cholesky分解/向量构造：由于 \(Y^* \succeq 0\)，我们可以对它进行Cholesky分解（或特征值分解），得到一组向量 \(\mathbf{v}_0^*, \mathbf{v}_1^*, ..., \mathbf{v}_n^* \in \mathbb{R}^m\)（通常 \(m \leq n+1\)），满足 \(Y_{ij}^* = \mathbf{v}_i^* \cdot \mathbf{v}_j^*\)，且 \(\|\mathbf{v}_i^*\| = 1\)。

    • 向量 \(\mathbf{v}_0^*\) 对应我们引入的“特殊向量”。
    • 向量 \(\mathbf{v}_i^*\) 对应原图的顶点 \(i\)。
    • 这些向量分布在单位球面上。

  2. 随机超平面舍入：

    • 在 \(m\) 维单位球面上均匀随机地选取一个方向向量 \(\mathbf{r}\)（即 \(\mathbf{r}\) 是一个随机单位向量）。
    • 定义团 \(C\) 的候选集合为：所有满足 \(\mathbf{v}_0^* \cdot \mathbf{v}_i^* \geq 0\) 且 \(\text{sign}(\mathbf{v}_0^* \cdot \mathbf{r}) = \text{sign}(\mathbf{v}_i^* \cdot \mathbf{r})\) 的顶点 \(i\)。
    • 更常见的等效操作（易于分析）：
      a. 将每个向量 \(\mathbf{v}_i^*\) 投影到由 \(\mathbf{v}_0^*\) 定义的“参考方向”上。令 \(z_i = \mathbf{v}_0^* \cdot \mathbf{v}_i^* \in [-1, 1]\)。
      b. 随机选取一个阈值 \(\theta \in [0, 1]\)，然后定义 \(C = \{ i : z_i \geq \theta \}\)。但直接这样选取可能不满足团的定义。
      c. 修正以保证团的定义：从集合 \(\{ i : z_i > 0 \}\) 开始（因为 \(z_i > 0\) 意味着顶点 \(i\) 倾向于被选，对应 \(x_i > 0.5\)）。但其中可能包含不相邻的顶点对。为了得到一个合法团，我们可以采用贪心策略：对候选顶点按 \(z_i\) 降序排序，然后依次检查，仅当加入该顶点后当前集合仍然构成团时才将其加入。
      d. 更简单的随机舍入（理论分析常用）：在单位球面上随机选取一个超平面（法向量为 \(\mathbf{r}\)）。将顶点 \(i\) 选入候选集当且仅当 \(\text{sign}(\mathbf{v}_0^* \cdot \mathbf{r}) = \text{sign}(\mathbf{v}_i^* \cdot \mathbf{r})\)。然后，对这个候选集进行极大团扩展（例如，去掉其中不相邻的点对中权重较小的一个，或采用贪心法找到一个包含该候选集的团）。这样得到的集合一定是一个团。

  3. 算法流程：

    • 求解上述SDP，得到最优解 \(Y^*\) 和对应的向量 \(\mathbf{v}_0^*, \{ \mathbf{v}_i^* \}\)。
    • 重复多次（例如 \(K = 100\ln n\) 次）：
      a. 生成一个随机单位向量 \(\mathbf{r}\)。
      b. 计算集合 \(S = \{ i : \text{sign}(\mathbf{v}_0^* \cdot \mathbf{r}) = \text{sign}(\mathbf{v}_i^* \cdot \mathbf{r}) \}\)。
      c. 对 \(S\) 应用极大团启发式（例如，将 \(S\) 中的顶点按权重降序排列，然后贪心地构建一个团：依次尝试加入顶点，如果加入后与已选顶点都相邻，则加入）。
    • 从所有重复试验产生的团中，选择权重最大的那个作为最终输出。

步骤5：近似比分析（直观理解）

对于无权情况（即最大团问题），基于SDP松弛和随机舍入的算法可以达到近似比 \(O(n(\log \log n)^2 / (\log n)^3)\) 等非平凡的上界，虽然不如某些简单算法的常数比，但在理论上具有重要意义，展示了SDP方法的力量。
对于顶点加权情况，分析更为复杂。通常，通过分析每个顶点 \(i\) 被包含在最终团 \(C\) 中的概率 \(\Pr[i \in C]\)，可以证明该概率与 \((1 - \arccos(z_i)/\pi)\) 或类似表达式成正比，其中 \(z_i = \mathbf{v}_0 \cdot \mathbf{v}_i\)。通过比较期望权重 \(\mathbb{E}[w(C)]\) 与SDP最优值 \(SDP^*\)（从而与原问题最优值 \(OPT\)），可以导出一个期望近似比。

通常，对于MWCP，这类算法不能保证常数近似比（除非图具有特殊结构），但它在许多实际算例中表现优异，并且提供了原问题最优值的一个紧上界 \(SDP^*\)，这在评估启发式算法质量时非常有用。

总结

通过本例，我们展示了：

  1. 如何将NP-难的顶点加权最大团问题建模为整数二次规划。
  2. 如何通过引入向量表示和移除秩约束，得到可高效求解的半定规划松弛。
  3. 如何利用随机超平面舍入技术，将SDP的解转化为一个合法的团。
  4. 该算法虽不能保证常数近似比，但提供了优质的上界和实用的启发式解。

这个范例体现了线性规划的高级扩展——半定规划，在处理难解组合优化问题中的强大建模能力和分析技巧。

基于线性规划的顶点加权最大团问题的半定规划松弛与随机舍入算法求解示例 我来为您讲解这个关于线性规划及其相关算法在组合优化问题中的一个应用。 问题描述 顶点加权最大团问题（Maximum Weight Clique Problem, MWCP） ：给定一个无向图 \( G = (V, E) \)，其中每个顶点 \( v \in V \) 有一个非负权重 \( w_ v \)。一个“团”是指顶点集的一个子集 \( C \subseteq V \)，使得 \( C \) 中任意两个顶点之间都有一条边（即 \( C \) 的导出子图是完全图）。目标是找到一个团 \( C \)，使得其总权重 \( \sum_ {v \in C} w_ v \) 达到最大。 这个问题是经典的 最大团问题 的推广（当所有权重为1时即为最大团问题）。最大团问题是NP-难问题，因此MWCP也是NP-难的。我们无法在多项式时间内求出精确最优解（除非P=NP）。在这里，我们将探讨如何利用 半定规划（Semidefinite Programming, SDP）松弛 和 随机舍入（Randomized Rounding） 技术，设计一个近似算法来获得一个质量有理论保证的近似解。 解题步骤详解 步骤1：整数二次规划（Integer Quadratic Programming, IQP）建模 首先，我们需要将MWCP表示成一个数学优化模型。为每个顶点 \( v \) 引入一个0-1决策变量 \( x_ v \)： \( x_ v = 1 \) 表示顶点 \( v \) 被选入团 \( C \)。 \( x_ v = 0 \) 表示顶点 \( v \) 未被选入。 团的定义要求：对于图中 每一对 不相邻的顶点 \( (u, v) \notin E \)，它们不能同时被选中（即 \( x_ u \) 和 \( x_ v \) 不能同时为1）。这可以表示为约束 \( x_ u + x_ v \leq 1 \)。对于相邻的顶点则无此限制。 因此，MWCP可以建模为以下整数二次规划（实际上是一个线性整数规划，因为约束和目标都是线性的，但通常为了后续松弛，我们采用另一种等价形式）： \[ \begin{aligned} \text{最大化:} & \sum_ {v \in V} w_ v x_ v \\ \text{满足:} & x_ u + x_ v \leq 1, \quad \forall (u, v) \notin E \\ & x_ v \in \{0, 1\}, \quad \forall v \in V \end{aligned} \] 然而，为了应用更强大的半定规划松弛，我们采用一个等价的 二次整数规划 形式。考虑向量 \( \mathbf{v}_ v \in \mathbb{R}^n \)（其中 \( n = |V| \)），并令 \( x_ v = \frac{1 + \mathbf{v}_ 0 \cdot \mathbf{v}_ v}{2} \)，其中我们引入一个额外的单位向量 \( \mathbf{v}_ 0 \)，并且要求所有向量 \( \mathbf{v}_ 0, \mathbf{v}_ v \) 都是单位向量（即 \( \|\mathbf{v}\|_ 2 = 1 \)）。在这种表示下： \( x_ v = 1 \) 对应于 \( \mathbf{v}_ 0 \cdot \mathbf{v}_ v = 1 \)（即 \( \mathbf{v}_ v = \mathbf{v}_ 0 \)）。 \( x_ v = 0 \) 对应于 \( \mathbf{v}_ 0 \cdot \mathbf{v}_ v = -1 \)（即 \( \mathbf{v}_ v = -\mathbf{v}_ 0 \)）。 不相邻顶点 \( u, v \) 不能同时被选中的约束 \( x_ u + x_ v \leq 1 \) 可以转化为： \[ \frac{1 + \mathbf{v}_ 0 \cdot \mathbf{v}_ u}{2} + \frac{1 + \mathbf{v}_ 0 \cdot \mathbf{v}_ v}{2} \leq 1 \implies \mathbf{v}_ 0 \cdot \mathbf{v}_ u + \mathbf{v}_ 0 \cdot \mathbf{v}_ v \leq 0. \] 目标函数为 \( \sum_ v w_ v \frac{1 + \mathbf{v}_ 0 \cdot \mathbf{v}_ v}{2} \)。最大化此目标等价于最大化 \( \sum_ v w_ v (\mathbf{v}_ 0 \cdot \mathbf{v}_ v) \)。 因此，我们得到等价的向量形式整数规划： \[ \begin{aligned} \text{最大化:} & \sum_ {v \in V} w_ v (\mathbf{v}_ 0 \cdot \mathbf{v}_ v) \\ \text{满足:} & \mathbf{v}_ 0 \cdot \mathbf{v}_ u + \mathbf{v}_ 0 \cdot \mathbf{v}_ v \leq 0, \quad \forall (u, v) \notin E \\ & \|\mathbf{v}_ 0\| = 1, \quad \|\mathbf{v}_ v\| = 1, \quad \forall v \in V \\ & \mathbf{v}_ v \in \mathbb{R}^{n+1}, \quad \forall v \in \{0\} \cup V. \end{aligned} \] 这仍然是一个难解的问题。 步骤2：半定规划（SDP）松弛 半定规划松弛的核心思想是将“每个变量是一个单位向量”的条件，转化为一个关于向量 内积 的矩阵条件。 我们构造一个对称矩阵 \( Y \)，其行和列对应索引 \( 0, 1, 2, ..., n \)（其中索引0对应 \( \mathbf{v} 0 \)，索引 \( i \) 对应顶点 \( v_ i \)）。定义 \( Y {ij} = \mathbf{v}_ i \cdot \mathbf{v}_ j \)（内积）。矩阵 \( Y \) 被称为 Gram矩阵 ，它具有以下关键性质： \( Y \) 是 半正定（Positive Semidefinite, PSD） 的，记作 \( Y \succeq 0 \)。 由于每个向量是单位向量，所以 \( Y_ {ii} = \mathbf{v}_ i \cdot \mathbf{v}_ i = 1 \) 对所有 \( i \) 成立。 现在，用矩阵 \( Y \) 的元素重写我们的问题： 目标函数：\( \sum_ {v} w_ v (\mathbf{v} 0 \cdot \mathbf{v} v) = \sum {i=1}^{n} w_ i Y {0i} \)。 约束 \( \mathbf{v}_ 0 \cdot \mathbf{v}_ u + \mathbf{v} 0 \cdot \mathbf{v} v \leq 0 \) 变为：\( Y {0u} + Y {0v} \leq 0 \)。 于是，我们得到了MWCP的 半定规划松弛 ： \[ \begin{aligned} \text{最大化:} & \sum_ {i=1}^{n} w_ i Y_ {0i} \\ \text{满足:} & Y_ {0u} + Y_ {0v} \leq 0, \quad \forall (u, v) \notin E \\ & Y_ {ii} = 1, \quad \forall i \in \{0, 1, ..., n\} \\ & Y \succeq 0, \quad Y \text{ 是对称矩阵}. \end{aligned} \] 为什么这是“松弛”？ 在原整数规划中，我们要求 \( Y_ {ij} = \mathbf{v}_ i \cdot \mathbf{v}_ j \)，并且每个 \( \mathbf{v} i \) 是单位向量。这隐含了一个更强的条件：矩阵 \( Y \) 的秩必须为1（因为它可以分解为 \( Y = \mathbf{v}^T \mathbf{v} \)，其中 \( \mathbf{v} \) 是拼接所有向量的行向量）。在半定规划中，我们 移除了“秩为1”这个约束 ，只保留了 \( Y \succeq 0 \) 和 \( Y {ii}=1 \)。可行解集变大了，因此最优值 \( SDP^* \) 是原问题最优值 \( OPT \) 的一个 上界 （即 \( SDP^* \geq OPT \)）。 步骤3：求解半定规划 半定规划属于凸优化范畴，可以在多项式时间内（精确或任意精度近似地）求解。有成熟的内点法算法和软件包（如SeDuMi, SDPA, CVX等）可以用于求解此SDP模型。我们假设通过求解器得到了最优解矩阵 \( Y^* \)。 步骤4：随机舍入（Goemans-Williamson风格） 得到半正定矩阵 \( Y^* \) 后，我们需要将它“舍入”成一个合法的团（即0-1解）。这里我们采用经典的 随机超平面舍入 技术。 Cholesky分解/向量构造 ：由于 \( Y^* \succeq 0 \)，我们可以对它进行Cholesky分解（或特征值分解），得到一组向量 \( \mathbf{v}_ 0^ , \mathbf{v}_ 1^ , ..., \mathbf{v} n^* \in \mathbb{R}^m \)（通常 \( m \leq n+1 \)），满足 \( Y {ij}^* = \mathbf{v}_ i^* \cdot \mathbf{v}_ j^* \)，且 \( \|\mathbf{v}_ i^* \| = 1 \)。 向量 \( \mathbf{v}_ 0^* \) 对应我们引入的“特殊向量”。 向量 \( \mathbf{v}_ i^* \) 对应原图的顶点 \( i \)。 这些向量分布在单位球面上。 随机超平面舍入 ： 在 \( m \) 维单位球面上 均匀随机 地选取一个方向向量 \( \mathbf{r} \)（即 \( \mathbf{r} \) 是一个随机单位向量）。 定义团 \( C \) 的候选集合为：所有满足 \( \mathbf{v}_ 0^* \cdot \mathbf{v}_ i^* \geq 0 \) 且 \( \text{sign}(\mathbf{v}_ 0^* \cdot \mathbf{r}) = \text{sign}(\mathbf{v}_ i^* \cdot \mathbf{r}) \) 的顶点 \( i \)。 更常见的等效操作（易于分析） ： a. 将每个向量 \( \mathbf{v}_ i^* \) 投影到由 \( \mathbf{v}_ 0^* \) 定义的“参考方向”上。令 \( z_ i = \mathbf{v}_ 0^* \cdot \mathbf{v}_ i^* \in [ -1, 1 ] \)。 b. 随机选取一个阈值 \( \theta \in [ 0, 1] \)，然后定义 \( C = \{ i : z_ i \geq \theta \} \)。但直接这样选取可能不满足团的定义。 c. 修正以保证团的定义 ：从集合 \( \{ i : z_ i > 0 \} \) 开始（因为 \( z_ i > 0 \) 意味着顶点 \( i \) 倾向于被选，对应 \( x_ i > 0.5 \)）。但其中可能包含不相邻的顶点对。为了得到一个合法团，我们可以采用贪心策略：对候选顶点按 \( z_ i \) 降序排序，然后依次检查，仅当加入该顶点后当前集合仍然构成团时才将其加入。 d. 更简单的随机舍入（理论分析常用） ：在单位球面上随机选取一个超平面（法向量为 \( \mathbf{r} \)）。将顶点 \( i \) 选入候选集当且仅当 \( \text{sign}(\mathbf{v}_ 0^* \cdot \mathbf{r}) = \text{sign}(\mathbf{v}_ i^* \cdot \mathbf{r}) \)。然后， 对这个候选集进行极大团扩展 （例如，去掉其中不相邻的点对中权重较小的一个，或采用贪心法找到一个包含该候选集的团）。这样得到的集合一定是一个团。 算法流程 ： 求解上述SDP，得到最优解 \( Y^* \) 和对应的向量 \( \mathbf{v}_ 0^ , \{ \mathbf{v}_ i^ \} \)。 重复多次（例如 \( K = 100\ln n \) 次）： a. 生成一个随机单位向量 \( \mathbf{r} \)。 b. 计算集合 \( S = \{ i : \text{sign}(\mathbf{v}_ 0^* \cdot \mathbf{r}) = \text{sign}(\mathbf{v}_ i^* \cdot \mathbf{r}) \} \)。 c. 对 \( S \) 应用 极大团启发式 （例如，将 \( S \) 中的顶点按权重降序排列，然后贪心地构建一个团：依次尝试加入顶点，如果加入后与已选顶点都相邻，则加入）。 从所有重复试验产生的团中，选择 权重最大 的那个作为最终输出。 步骤5：近似比分析（直观理解） 对于无权情况（即最大团问题），基于SDP松弛和随机舍入的算法可以达到近似比 \( O(n(\log \log n)^2 / (\log n)^3) \) 等非平凡的上界，虽然不如某些简单算法的常数比，但在理论上具有重要意义，展示了SDP方法的力量。 对于顶点加权情况，分析更为复杂。通常，通过分析每个顶点 \( i \) 被包含在最终团 \( C \) 中的概率 \( \Pr[ i \in C] \)，可以证明该概率与 \( (1 - \arccos(z_ i)/\pi) \) 或类似表达式成正比，其中 \( z_ i = \mathbf{v}_ 0 \cdot \mathbf{v}_ i \)。通过比较期望权重 \( \mathbb{E}[ w(C)] \) 与SDP最优值 \( SDP^* \)（从而与原问题最优值 \( OPT \)），可以导出一个 期望近似比 。 通常，对于MWCP，这类算法不能保证常数近似比（除非图具有特殊结构），但它在许多实际算例中表现优异，并且 提供了原问题最优值的一个紧上界 \( SDP^* \) ，这在评估启发式算法质量时非常有用。 总结 通过本例，我们展示了： 如何将NP-难的顶点加权最大团问题建模为整数二次规划。 如何通过引入向量表示和移除秩约束，得到可高效求解的半定规划松弛。 如何利用随机超平面舍入技术，将SDP的解转化为一个合法的团。 该算法虽不能保证常数近似比，但提供了优质的上界和实用的启发式解。 这个范例体现了线性规划的高级扩展——半定规划，在处理难解组合优化问题中的强大建模能力和分析技巧。