9. 凸松弛

# 最大切问题

最大切问题（Max-Cut Problem）是图论中的一个经典组合优化问题，属于 NP 难问题。通过半正定松弛（Semidefinite Relaxation），可以将这一非凸问题转化为可求解的凸优化问题。

1. 半正定松弛 (Semidefinite Relaxation)

   非凸优化问题的例子

   考虑以下非凸优化问题：

   $$\begin{align*} \min \quad & x_1 - 2x_2 \\ \text{s.t.} \quad & x_1 \geq 0, \quad x_2 \geq 0 \\ & (x_1 - 1)^2 + x_2^2 \leq 1 \\ & (x_1 - 1)^2 + (x_2 - 1)^2 \geq 1 \end{align*}$$

   这不是一个凸优化问题（因为约束 $(x_1 - 1)^2 + (x_2 - 1)^2 \geq 1$ 不是凸的）。最优解为 $x^* = [0.1340, 0.5]^T$。

   半正定松弛的基本思想

   对于非凸优化问题，特别是二次优化问题，可以通过引入新的变量和约束，将问题松弛为半正定规划（SDP）问题：

   • 引入矩阵变量 $X = xx^T$，将二次项 $x_i x_j$ 替换为 $X_{ij}$
   • 添加约束 $X \succeq 0$（半正定约束）
   • 添加约束 $\text{rank}(X) = 1$（秩约束，但通常被忽略以得到凸松弛）
   • 忽略秩约束后，问题变为凸的 SDP 问题

2. 图论中的切与最大/最小切问题 (Cut in Graph Theory and Max/Min-Cut Problems)

   图的定义

   设 $G = (V, E)$ 是一个无向图，其中：

   • $V = \{1, 2, \ldots, n\}$ 是顶点集合
   • $E \subseteq V \times V$ 是边集合
   • 每条边 $(i, j) \in E$ 有权重 $w_{ij} \geq 0$

   切（Cut）的定义

   对于图 $G$ 的一个切（cut）是将顶点集合 $V$ 划分为两个不相交的子集 $S$ 和 $V \setminus S$。

   切的大小（Cut Size）

   切的大小定义为连接 $S$ 和 $V \setminus S$ 的边的权重之和：

   $$\text{cut}(S) = \sum_{i \in S, j \in V \setminus S} w_{ij}$$

   最大切问题（Max-Cut Problem）

   最大切问题是在所有可能的切中，找到使切的大小最大的切：

   $$\max_{S \subseteq V} \quad \text{cut}(S)$$

   这是一个 NP 难问题。

   最小切问题（Min-Cut Problem）

   最小切问题是找到使切的大小最小的切：

   $$\min_{S \subseteq V} \quad \text{cut}(S)$$

   最小切问题可以在多项式时间内求解（例如使用最大流最小切定理）。

3. 通过半正定松弛求解最大切问题 (Max-Cut via Semidefinite Relaxation)

   最大切问题的数学表述

   对于每个顶点 $i$，定义变量 $x_i \in \{-1, +1\}$：

   • $x_i = +1$ 表示顶点 $i$ 属于集合 $S$
   • $x_i = -1$ 表示顶点 $i$ 属于集合 $V \setminus S$

   则边 $(i, j)$ 在切中当且仅当 $x_i \neq x_j$，即 $x_i x_j = -1$。

   最大切问题可以表述为：

   $$\begin{align*} \max \quad & \frac{1}{2} \sum_{(i,j) \in E} w_{ij}(1 - x_i x_j) \\ \text{s.t.} \quad & x_i \in \{-1, +1\}, \quad i = 1, \ldots, n \end{align*}$$

   等价地：

   $$\begin{align*} \max \quad & \frac{1}{2} \sum_{(i,j) \in E} w_{ij}(1 - x_i x_j) \\ \text{s.t.} \quad & x_i^2 = 1, \quad i = 1, \ldots, n \end{align*}$$

   半正定松弛

   引入矩阵变量 $X = xx^T$，其中 $X_{ij} = x_i x_j$。注意到 $X = xx^T$ 意味着：

   • $X \succeq 0$（半正定）
   • $\text{rank}(X) = 1$（秩为 1）
   • $X_{ii} = x_i^2 = 1$（对角线元素为 1）

   忽略秩约束 $\text{rank}(X) = 1$，得到半正定松弛：

   $$\begin{align*} \max \quad & \frac{1}{2} \sum_{(i,j) \in E} w_{ij}(1 - X_{ij}) \\ \text{s.t.} \quad & X_{ii} = 1, \quad i = 1, \ldots, n \\ & X \succeq 0 \end{align*}$$

   这是一个凸优化问题（半正定规划），可以在多项式时间内求解。

   从松弛解恢复原始解

   求解 SDP 松弛后，得到矩阵 $X^*$。由于 $X^*$ 可能不满足 $\text{rank}(X^*) = 1$，需要使用舍入（rounding）方法从 $X^*$ 恢复原始变量 $x$：

   随机舍入方法（Goemans-Williamson 算法）：

   1. 对 $X^*$ 进行 Cholesky 分解：$X^* = V^T V$，其中 $V \in \mathbb{R}^{n \times n}$
   2. 随机选择单位向量 $r \in \mathbb{R}^n$（均匀分布在单位球面上）
   3. 对每个顶点 $i$，计算 $x_i = \text{sign}(v_i^T r)$，其中 $v_i$ 是 $V$ 的第 $i$ 行

   这种方法可以保证得到至少 $0.878$ 倍最优值的近似解。

4. 半正定松弛的界 (Bounds of Semidefinite Relaxation)

   松弛的界

   设 $OPT$ 是原始最大切问题的最优值，$SDP$ 是半正定松弛的最优值，则：

   $$SDP \geq OPT$$

   因为原始问题的可行域是松弛问题可行域的子集。

   近似比

   Goemans-Williamson 算法可以保证：

   $$\frac{\text{算法得到的切的大小}}{OPT} \geq 0.878$$

   即算法得到的解至少是最优解的 $87.8\%$。

   紧性

   在某些情况下，半正定松弛可能是紧的（tight），即 $SDP = OPT$。但在一般情况下，存在松弛间隙（relaxation gap）。

5. 最大切问题的应用

   • 电路设计：VLSI 布局
   • 聚类：数据聚类问题
   • 网络分析：社区检测
   • 机器学习：半监督学习

6. 半正定松弛的一般方法

   二次优化问题的半正定松弛

   对于一般的二次优化问题：

   $$\begin{align*} \min \quad & x^T Q x + c^T x \\ \text{s.t.} \quad & x \in \mathcal{X} \end{align*}$$

   可以通过以下步骤进行半正定松弛：

   1. 引入矩阵变量 $X = xx^T$
   2. 将目标函数中的 $x^T Q x$ 替换为 $\text{tr}(QX)$
   3. 将约束中的二次项替换为 $X$ 的相应元素
   4. 添加约束 $X \succeq 0$ 和 $X_{ii} = x_i^2$（如果 $x_i \in \{-1, +1\}$）
   5. 忽略秩约束 $\text{rank}(X) = 1$

# 数独问题、拼图问题与日历问题

数独、拼图和日历等组合问题可以通过凸优化方法（特别是线性规划和二次规划）来求解。这些方法将组合约束转化为线性或二次约束，从而将离散优化问题转化为连续优化问题。

1. 数独问题 (Sudoku Puzzle)

   数独规则

   数独是一个 $9 \times 9$ 的网格，需要填入数字 $1$ 到 $9$，满足以下约束：

   • 每行包含 $1$ 到 $9$ 的每个数字恰好一次
   • 每列包含 $1$ 到 $9$ 的每个数字恰好一次
   • 每个 $3 \times 3$ 的子网格包含 $1$ 到 $9$ 的每个数字恰好一次
   • 某些格子已经预先填入数字（已知值）

   优化问题表述

   可以使用整数规划或线性规划来表述数独问题：

   变量定义：

   • 定义二进制变量 $x_{ijk} \in \{0, 1\}$，其中 $i, j \in \{1, \ldots, 9\}$ 表示位置，$k \in \{1, \ldots, 9\}$ 表示数字
   • $x_{ijk} = 1$ 表示位置 $(i, j)$ 填入数字 $k$
   • $x_{ijk} = 0$ 表示位置 $(i, j)$ 不填入数字 $k$

   约束条件：

   • 每个位置恰好填入一个数字：

     $$\sum_{k=1}^9 x_{ijk} = 1, \quad \forall i, j$$

   • 每行包含每个数字恰好一次：

     $$\sum_{j=1}^9 x_{ijk} = 1, \quad \forall i, k$$

   • 每列包含每个数字恰好一次：

     $$\sum_{i=1}^9 x_{ijk} = 1, \quad \forall j, k$$

   • 每个 $3 \times 3$ 子网格包含每个数字恰好一次：

     $$\sum_{i=3p+1}^{3p+3} \sum_{j=3q+1}^{3q+3} x_{ijk} = 1, \quad \forall k, p, q \in \{0, 1, 2\}$$

   • 已知值的约束：

     $$x_{ijk} = 1, \quad \text{如果位置 } (i, j) \text{ 已知为 } k$$

   目标函数：

   由于数独问题主要是可行性问题（找到满足所有约束的解），可以设置任意目标函数，例如：

   $$\min \quad 0$$

   或使用线性规划求解可行性问题。

   求解方法

   • 可以使用整数线性规划（ILP）求解器
   • 也可以使用线性规划松弛，然后通过舍入或分支定界方法得到整数解
   • 对于标准数独，通常有唯一解

2. 拼图问题 (Jigsaw Puzzle)

   问题描述

   拼图问题是将打乱的拼图片段重新组合成完整的图像。这涉及：

   • 确定每个片段的位置
   • 确定片段之间的邻接关系
   • 确保片段之间的边界匹配

   优化问题表述

   可以使用线性规划或二次规划来表述拼图问题：

   变量定义：

   • 定义位置变量表示每个片段在最终图像中的位置
   • 定义邻接变量表示片段之间的连接关系
   • 定义匹配变量表示片段边界的匹配程度

   约束条件：

   • 位置约束：每个片段有唯一位置
   • 邻接约束：相邻片段必须匹配
   • 边界约束：边界片段必须位于图像边缘
   • 完整性约束：所有片段都必须被使用

   目标函数：

   最小化片段之间的不匹配程度：

   $$\min \quad \sum_{\text{相邻片段对}} \text{不匹配惩罚}$$

   或最大化匹配程度：

   $$\max \quad \sum_{\text{相邻片段对}} \text{匹配得分}$$

   求解方法

   • 线性规划方法：将拼图问题转化为线性规划
   • 二次规划方法（PSQP）：使用二次规划求解拼图问题，考虑片段之间的匹配得分
   • 分层循环约束方法：使用分层方法处理大规模拼图

   应用

   • 图像重建
   • 考古学中的碎片重组
   • 计算机视觉中的图像拼接

3. 日历问题 (Calendar Puzzle)

   问题描述

   日历拼图是一种特殊的拼图问题，需要将拼图片段组合成特定形状（如日历形状），满足特定的约束条件。

   优化问题表述

   类似于拼图问题，可以使用线性规划或二次规划来表述：

   约束条件：

   • 片段位置约束
   • 形状约束（最终形状必须符合日历形状）
   • 邻接和匹配约束

   求解方法

   • 使用凸优化方法（线性规划、二次规划）
   • 结合启发式方法提高求解效率

4. 凸优化在组合问题中的优势

   优势

   • 将离散组合问题转化为连续优化问题
   • 可以利用高效的凸优化算法
   • 可以处理大规模问题
   • 提供理论保证（如最优性条件）

   挑战

   • 需要将离散约束转化为连续约束
   • 可能需要舍入步骤从连续解得到离散解
   • 对于某些问题，松弛可能不够紧

5. 相关工具和资源

   • CVX-Jigsaw：使用 CVX 求解拼图问题的工具
   • 在线日历拼图求解器：https://joinker.oss-cn-shanghai.aliyuncs.com/calendar-puzzle-solver/index.html
   • 计算拼图求解：http://icvl.cs.bgu.ac.il/automatic-jigsaw-puzzle-solving/

# MM 算法和 Reweighted L1

MM（Majorization-Minimization）算法和重加权 $\ell_1$（Reweighted $\ell_1$）方法是求解非凸优化问题的重要技术，通过迭代求解一系列凸优化子问题来逼近原问题的解。

1. MM 算法 (Majorization-Minimization Algorithm)

   基本思想

   MM 算法是一种迭代优化方法，通过构造代理函数（surrogate function）来简化原问题的求解：

   • Majorization（主化）：在每次迭代中，构造一个代理函数，该函数在原问题的当前点处与原函数值相等，且在原函数的"上方"（即大于等于原函数）
   • Minimization（最小化）：最小化代理函数，得到下一个迭代点

   算法流程

   对于优化问题 $\min_x f(x)$：

   1. 初始化 $x^{(0)}$
   2. 对于 $j = 0, 1, 2, \ldots$：
      • 构造代理函数 $g(x \mid x^{(j)})$，使得：
        • $g(x^{(j)} \mid x^{(j)}) = f(x^{(j)})$
        • $g(x \mid x^{(j)}) \geq f(x)$ 对所有 $x$ 成立
      • 更新：$x^{(j+1)} = \arg\min_x g(x \mid x^{(j)})$
   3. 重复直到收敛

   单调性保证

   MM 算法保证目标函数在每次迭代中单调递减：

   $$f(x^{(j+1)}) \leq g(x^{(j+1)} \mid x^{(j)}) \leq g(x^{(j)} \mid x^{(j)}) = f(x^{(j)})$$

   这是因为代理函数在原函数上方，且最小化代理函数会减少目标函数值。

2. 重加权 $\ell_1$ 方法 (Reweighted $\ell_1$)

   问题背景

   考虑 $\ell_0$ 最小化问题：

   $$\begin{align*} \min \quad & \|x\|_0 \\ \text{s.t.} \quad & Ax = b \end{align*}$$

   或等价地，考虑对数惩罚函数：

   $$\min \quad \sum_i \log(|x_i| + \epsilon) \quad \text{s.t.} \quad Ax = b$$

   其中 $\epsilon > 0$ 是一个小的常数。

   重加权 $\ell_1$ 算法

   重加权 $\ell_1$ 算法的关键思想是迭代求解带权重的 $\ell_1$ 最小化问题。

   算法步骤：

   1. 初始化 $x^{(0)}$（例如，使用标准 $\ell_1$ 最小化）
   2. 对于 $j = 0, 1, 2, \ldots$：
      • 计算权重：$w_i^{(j)} = \frac{1}{|x_i^{(j)}| + \epsilon}$
      • 求解加权 $\ell_1$ 最小化问题：

        $$x^{(j+1)} = \arg\min_x \sum_i w_i^{(j)} |x_i| \quad \text{s.t.} \quad Ax = b$$

   3. 重复直到收敛

   等价形式

   引入辅助变量 $u_i \geq |x_i|$，则优化问题可以写为：

   $$\begin{align*} \min_{x, u} \quad & \sum_i \frac{u_i}{u_i^{(j)} + \epsilon} \\ \text{s.t.} \quad & Ax = b \\ & |x_i| \leq u_i \end{align*}$$

   消去 $u$ 后，等价于：

   $$x^{(j+1)} = \arg\min_x \sum_i \frac{|x_i|}{|x_i^{(j)}| + \epsilon} \quad \text{s.t.} \quad Ax = b$$

   这是一个约束 $\ell_1$ 范数最小化问题，可以使用单纯形算法等方法快速求解。

   权重系数的解释

   重加权算法得名于目标函数中出现的反比例权重系数 $1/(|x_i^{(j)}| + \epsilon)$。

   直观解释：

   • 当 $|x_i^{(j)}|$ 较大时，权重 $1/(|x_i^{(j)}| + \epsilon)$ 较小，对 $x_i$ 的惩罚较小
   • 当 $|x_i^{(j)}|$ 较小时，权重 $1/(|x_i^{(j)}| + \epsilon)$ 较大，对 $x_i$ 的惩罚较大
   • 这迫使潜在解 $x$ 在 $|x_i|$ 较小的索引处收缩，从而促进稀疏性

   参数 $\epsilon$ 的作用

   常数 $\epsilon$ 的引入是为了：

   • 保证迭代稳定性：防止分母为零
   • 允许零值恢复：确保 $x$ 中零值分量 $x_i$ 不会严格禁止下一轮迭代中 $x_i$ 变为非零

   注意事项：

   • $\epsilon$ 通常在迭代开始时设置为很小的值
   • 如果第 $i$ 个分量 $x_i^{(j)}$ 在第 $j$ 次迭代后变为接近零，对应的权重系数将变为非常大的数 $1/\epsilon \gg 0$
   • 这通常阻止我们在第 $j$ 次迭代后重新考虑将第 $i$ 个分量 $x_i^{(j)}$ 作为非零解的一部分的可能性
   • 因此，$\epsilon$ 的选择需要在稳定性和灵活性之间权衡

3. MM 算法与重加权 $\ell_1$ 的结合

   代理函数构造

   对于对数惩罚函数 $\sum_i \log(u_i + \epsilon)$，可以构造代理函数：

   $$g(u \mid u^{(j)}) = \sum_i \frac{u_i}{u_i^{(j)} + \epsilon} + \text{const}$$

   该代理函数满足：

   • $g(u^{(j)} \mid u^{(j)}) = \sum_i \log(u_i^{(j)} + \epsilon)$
   • $g(u \mid u^{(j)}) \geq \sum_i \log(u_i + \epsilon)$（由对数函数的凸性）

   迭代优化问题

   在第 $j$ 次迭代中，优化问题为：

   $$(x^{(j+1)}, u^{(j+1)}) = \arg\min_{x, u} \sum_i \frac{u_i}{u_i^{(j)} + \epsilon} \quad \text{s.t.} \quad Ax = b, \ |x_i| \leq u_i$$

   消去 $u$ 后，等价于：

   $$x^{(j+1)} = \arg\min_x \sum_i \frac{|x_i|}{|x_i^{(j)}| + \epsilon} \quad \text{s.t.} \quad Ax = b$$

4. 重加权 $\ell_1$ 的优势

   • 比标准 $\ell_1$ 最小化更能促进稀疏性
   • 通过迭代改进，逐步逼近 $\ell_0$ 最小化
   • 每次迭代只需求解凸优化问题（加权 $\ell_1$ 最小化）
   • 计算效率高（可以使用单纯形算法等）

5. 应用

   • 稀疏信号恢复：从少量观测中恢复稀疏信号
   • 压缩感知：改进 $\ell_1$ 最小化的性能
   • 特征选择：在机器学习中选择重要特征

# Robust PCA

鲁棒主成分分析（Robust Principal Component Analysis, Robust PCA）旨在从被稀疏噪声污染的数据中恢复低秩结构，是传统 PCA 的鲁棒扩展。

1. 问题设定

   矩阵分解问题

   在许多情况下，我们需要将矩阵 $A \in \mathbb{R}^{m \times n}$ 分解为两个矩阵的和：

   • 矩阵 $B$ 具有小秩（low rank）
   • 矩阵 $C$ 是稀疏的（sparse）

   即 $A = B + C$，其中 $B$ 是低秩矩阵，$C$ 是稀疏矩阵。

   应用场景

   • 视频背景建模：$B$ 是静态背景（低秩），$C$ 是前景物体（稀疏）
   • 人脸识别：$B$ 是正常光照下的人脸（低秩），$C$ 是阴影或遮挡（稀疏）
   • 推荐系统：$B$ 是用户偏好（低秩），$C$ 是异常评分（稀疏）
   • 数据去噪：从被稀疏异常值污染的数据中恢复真实信号

2. 优化问题表述

   原始问题（非凸）

   原始优化问题为：

   $$\begin{align*} \min_{B, C \in \mathbb{R}^{m \times n}} \quad & \text{rank}(B) + \|C\|_0 \\ \text{s.t.} \quad & A = B + C \end{align*}$$

   其中：

   • $\text{rank}(B)$ 是矩阵 $B$ 的秩（非零奇异值的个数）
   • $\|C\|_0$ 是矩阵 $C$ 的 $\ell_0$ 范数（非零元素的个数）

   问题困难性

   • 这不是一个凸优化问题
   • $\text{rank}(\cdot)$ 和 $\|\cdot\|_0$ 都是非凸函数
   • 直接求解非常困难（NP 难问题）

3. 凸松弛：核范数与 $\ell_1$ 范数

   凸松弛问题

   通过凸松弛，将原问题转化为：

   $$\begin{align*} \min_{B, C \in \mathbb{R}^{m \times n}} \quad & \|B\|_* + \lambda \|C\|_1 \\ \text{s.t.} \quad & A = B + C \end{align*}$$

   其中：

   • $\|B\|_* = \text{trace}(\sqrt{B^T B}) = \sum_i \sigma_i(B)$ 是矩阵 $B$ 的核范数（nuclear norm），即 $B$ 的奇异值之和
   • $\|C\|_1 = \sum_{i,j} |C_{ij}|$ 是矩阵 $C$ 的 $\ell_1$ 范数（元素绝对值之和）
   • $\lambda > 0$ 是正则化参数，控制低秩性和稀疏性的权衡

   核范数的性质

   • 核范数是矩阵秩的凸包（在单位球上）
   • 核范数是矩阵的 $\ell_1$ 范数在奇异值空间中的推广
   • 最小化核范数可以促进低秩性，类似于 $\ell_1$ 范数促进稀疏性

   $\ell_1$ 范数的性质

   • $\ell_1$ 范数是 $\ell_0$ 范数的凸包
   • 最小化 $\ell_1$ 范数可以促进稀疏性

4. 理论保证

   精确恢复条件

   在满足某些条件下，凸松弛问题可以精确恢复原始的低秩矩阵 $B$ 和稀疏矩阵 $C$：

   • $B$ 的秩足够小
   • $C$ 的稀疏性足够高（非零元素比例足够小）
   • $B$ 和 $C$ 满足某些不相干性（incoherence）条件

   恢复保证

   如果：

   • $\text{rank}(B) \leq \rho_r \frac{m n}{\mu \log^2(m n)}$
   • $\|C\|_0 \leq \rho_s m n$

   其中 $\rho_r, \rho_s$ 是常数，$\mu$ 是 $B$ 的不相干参数，则凸松弛问题可以以高概率精确恢复 $B$ 和 $C$。

5. 求解方法

   算法

   Robust PCA 可以使用多种算法求解：

   • 增广拉格朗日方法（ALM）：将约束 $A = B + C$ 加入拉格朗日函数
   • 交替方向乘数法（ADMM）：交替更新 $B$ 和 $C$
   • 近端梯度方法：使用软阈值算子更新 $B$ 和 $C$

   软阈值算子

   对于核范数最小化，软阈值算子为：

   $$\mathcal{S}_\tau(X) = U \text{diag}(\max(\sigma_i - \tau, 0)) V^T$$

   其中 $X = U \Sigma V^T$ 是 $X$ 的奇异值分解，$\sigma_i$ 是奇异值，$\tau$ 是阈值参数。

   对于 $\ell_1$ 范数最小化，软阈值算子为：

   $$\mathcal{S}_\tau(x) = \text{sign}(x) \max(|x| - \tau, 0)$$

6. Robust PCA 的应用

   • 视频背景减除：从视频中分离静态背景和运动前景
   • 人脸识别：处理光照变化和遮挡
   • 推荐系统：检测异常评分
   • 数据清洗：去除稀疏异常值
   • 图像处理：图像去噪和修复

7. 与标准 PCA 的关系

   标准 PCA

   标准 PCA 假设数据是低秩的，且噪声是高斯噪声：

   $$A = B + E$$

   其中 $E$ 是高斯噪声矩阵。

   Robust PCA

   Robust PCA 假设数据是低秩的，但噪声是稀疏的（可能是任意大的异常值）：

   $$A = B + C$$

   其中 $C$ 是稀疏矩阵（异常值）。

   优势

   • 对稀疏异常值更鲁棒
   • 可以处理任意大的异常值（只要它们是稀疏的）
   • 在视频分析、推荐系统等应用中表现优异