图的半定规划松弛

字数 1583 2025-12-02 02:50:54

图的半定规划松弛

图论中的许多组合优化问题（如最大割、着色数、独立集等）是NP-难的，难以直接求解。半定规划（SDP）松弛是一种强大的工具，通过将离散优化问题转化为连续的凸优化问题，提供原问题最优值的上界或下界。以下将逐步介绍其核心思想与应用。

1. 问题背景：从线性规划到半定规划

线性规划（LP）松弛：早期方法将整数规划问题松弛为线性规划，例如用变量 \(x_i \in [0,1]\) 表示顶点是否属于独立集。但LP的约束能力有限，无法捕捉图结构中的复杂关系（如边之间的相关性）。
半定规划的优势：SDP允许变量为半正定矩阵，其约束条件能更精细地描述组合问题中的非线性关系（例如要求某些向量之间的内积非负），从而得到更紧的松弛界。

2. 半定规划的基本形式

一个标准SDP问题可表示为：

\[\text{最小化} \quad \langle C, X \rangle \quad \text{满足} \quad \langle A_i, X \rangle = b_i \ (i=1,\dots,m), \quad X \succeq 0 \]

其中：

\(X\) 是 \(n \times n\) 实对称矩阵，\(X \succeq 0\) 表示 \(X\) 是半正定的（即所有特征值非负）。
\(\langle C, X \rangle = \sum_{i,j} C_{ij} X_{ij}\) 是矩阵内积。
约束条件为线性等式，但整体可行域是凸的，可用内点法高效求解。

3. 图问题中的SDP建模示例：最大割问题

问题描述：给定无向图 \(G=(V,E)\) 与边权 \(w_{ij}\)，将顶点划分为两组，使两组间的边权和最大。
整数规划形式：令 \(x_i \in \{-1, +1\}\) 表示顶点分组，目标为 \(\max \frac{1}{2} \sum_{i。
SDP松弛：
1. 引入矩阵变量 \(Y\)，其中 \(Y_{ij} = x_i x_j\)，则 \(Y\) 的秩为1且对角线元素为1。
2. 松弛掉秩为1的约束，保留 \(Y \succeq 0\) 和 \(Y_{ii}=1\)，得到SDP：

\[ \max \frac{1}{2} \sum_{i

著名结果：Goemans-Williamson算法利用SDP解随机舍入得到近似解，近似比达0.878，优于任何LP方法。

4. SDP在图着色中的应用

向量着色模型：将着色问题转化为给每个顶点分配单位向量，要求相邻顶点的向量夹角足够大（例如k着色对应最小夹角 \(\arccos(-1/(k-1))\)）。
SDP形式：最小化 \(t\) 使得对任意边 \((i,j)\)，有 \(\langle v_i, v_j \rangle \le t\)，且向量模长为1。此SDP的解给出色数的下界（如Lovász θ函数）。

5. 算法实现与复杂性

内点法：SDP可在多项式时间内求解，但实际计算成本高于LP，适用于中等规模问题。
随机舍入：将SDP解（向量）通过随机超平面舍入为离散解，是近似算法的核心技巧。

6. 扩展与前沿

层次松弛：通过增加秩约束或更多线性条件（如Lasserre层次），可逐步逼近原问题最优解。
量子图论：SDP与量子纠缠中的非局部性存在深刻联系，例如用量子关联性改进经典界限。

SDP松弛将图论与凸优化紧密结合，为NP-难问题提供了理论保证的近似算法，是现代组合优化的重要工具。

图的半定规划松弛图论中的许多组合优化问题（如最大割、着色数、独立集等）是NP-难的，难以直接求解。半定规划（SDP）松弛是一种强大的工具，通过将离散优化问题转化为连续的凸优化问题，提供原问题最优值的上界或下界。以下将逐步介绍其核心思想与应用。 1. 问题背景：从线性规划到半定规划线性规划（LP）松弛：早期方法将整数规划问题松弛为线性规划，例如用变量 \(x_ i \in [ 0,1 ]\) 表示顶点是否属于独立集。但LP的约束能力有限，无法捕捉图结构中的复杂关系（如边之间的相关性）。半定规划的优势：SDP允许变量为半正定矩阵，其约束条件能更精细地描述组合问题中的非线性关系（例如要求某些向量之间的内积非负），从而得到更紧的松弛界。 2. 半定规划的基本形式一个标准SDP问题可表示为： \[ \text{最小化} \quad \langle C, X \rangle \quad \text{满足} \quad \langle A_ i, X \rangle = b_ i \ (i=1,\dots,m), \quad X \succeq 0 \] 其中： \(X\) 是 \(n \times n\) 实对称矩阵，\(X \succeq 0\) 表示 \(X\) 是半正定的（即所有特征值非负）。 \(\langle C, X \rangle = \sum_ {i,j} C_ {ij} X_ {ij}\) 是矩阵内积。约束条件为线性等式，但整体可行域是凸的，可用内点法高效求解。 3. 图问题中的SDP建模示例：最大割问题问题描述：给定无向图 \(G=(V,E)\) 与边权 \(w_ {ij}\)，将顶点划分为两组，使两组间的边权和最大。整数规划形式：令 \(x_ i \in \{-1, +1\}\) 表示顶点分组，目标为 \(\max \frac{1}{2} \sum_ {i<j} w_ {ij} (1 - x_ i x_ j)\)。 SDP松弛：引入矩阵变量 \(Y\)，其中 \(Y_ {ij} = x_ i x_ j\)，则 \(Y\) 的秩为1且对角线元素为1。松弛掉秩为1的约束，保留 \(Y \succeq 0\) 和 \(Y_ {ii}=1\)，得到SDP： \[ \max \frac{1}{2} \sum_ {i<j} w_ {ij} (1 - Y_ {ij}) \quad \text{s.t.} \quad Y \succeq 0, \ Y_ {ii}=1. \] 著名结果：Goemans-Williamson算法利用SDP解随机舍入得到近似解，近似比达0.878，优于任何LP方法。 4. SDP在图着色中的应用向量着色模型：将着色问题转化为给每个顶点分配单位向量，要求相邻顶点的向量夹角足够大（例如k着色对应最小夹角 \(\arccos(-1/(k-1))\)）。 SDP形式：最小化 \(t\) 使得对任意边 \((i,j)\)，有 \(\langle v_ i, v_ j \rangle \le t\)，且向量模长为1。此SDP的解给出色数的下界（如Lovász θ函数）。 5. 算法实现与复杂性内点法：SDP可在多项式时间内求解，但实际计算成本高于LP，适用于中等规模问题。随机舍入：将SDP解（向量）通过随机超平面舍入为离散解，是近似算法的核心技巧。 6. 扩展与前沿层次松弛：通过增加秩约束或更多线性条件（如Lasserre层次），可逐步逼近原问题最优解。量子图论：SDP与量子纠缠中的非局部性存在深刻联系，例如用量子关联性改进经典界限。 SDP松弛将图论与凸优化紧密结合，为NP-难问题提供了理论保证的近似算法，是现代组合优化的重要工具。