线性规划(1)：线性规划基础

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为线性规划概述、LP对偶、LP松弛。

线性规划基础

标准型

$$\begin{align*} \text{maximize} & \quad c_1x_1 + c_2x_2 + \cdots + c_nx_n \\ \text{subject to} &\quad a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1 \\ &\quad a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2 \\ &\quad \vdots \\ &\quad a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \leq b_m \\ &\quad x_1, x_2, \ldots, x_n \geq 0 \end{align*}$$

关键特征

• 可行域是凸集
• 局部最大值一定是全局最大值
• 最优解存在且出现在可行域的顶点处

化标准型

单纯形法

算法步骤

1. 选择初始顶点：任意可行顶点
2. 迭代移动：沿边移动到相邻顶点，要求目标函数值增加
   • 将当前顶点作为原点，对目标函数和约束条件换元
3. 终止条件：无法找到更优的相邻顶点时停止

时间复杂度

• 最坏情况：$\begin{pmatrix} m \\ n \end{pmatrix}$ （$m$ 个约束，$n$ 个变量），指数级
• 但实际效率高

最大流问题

• 可建模为 LP 问题
• Ford-Fulkerson 算法本质是单纯形法的实现

LP 对偶

对偶问题构造

原始问题：

$$\begin{align*} \text{maximize} &\quad \bm{c}^T\bm{x} \\ \text{subject to} &\quad A\bm{x} \leq \bm{b} \\ &\quad \bm{x} \geq \bm{0} \end{align*}$$

对偶问题：

$$\begin{align*} \text{minimize} &\quad \bm{b}^T\bm{y} \\ \text{subject to} &\quad A^T\bm{y} \geq \bm{c} \\ &\quad \bm{y} \geq \bm{0} \end{align*}$$

对偶定理

• 弱对偶定理：对偶问题的目标值始终 $\ge$ 原始问题的目标值
• 强对偶定理：若两者均有可行解，则最优目标值相等

LP 松弛

整数规划（Integer Programming）

要求变量为整数：

$$\begin{align*} \text{maximize} &\quad \bm{c}^T\bm{x} \\ \text{subject to} &\quad A\bm{x} \leq \bm{b} \\ &\quad \bm{x} \le \bm{0} \\ &\quad \bm{x} \in \mathbb{Z}^n \end{align*}$$

• 即使对于 $x_i \in \{0,1\}$，整数规划也是 NP 完全问题

LP 松弛策略

1. 松弛变量：将 $x_i \in \{0,1\}$ 松弛为 $0 \leq x_i \leq 1$
2. 求解 LP：通过求解 LP 获得分数解
3. 舍入策略：将分数解转换为整数解

• 我们希望得到的解可行且有近似度保证

顶点覆盖问题

LP 松弛策略

• 整数规划模型:

$$\begin{align*} \text{minimize} &\quad \sum_{v \in V} x_v \\ \text{subject to} &\quad x_u + x_v \geq 1 &&\quad \forall (u,v) \in E \\ &\quad x_v \in \{0,1\} &&\quad \forall v \in V \end{align*}$$

• LP 松弛与舍入：

1. 将 $x_v \in \{0,1\}$ 松弛为 $0 \leq x_v \leq 1$
2. 对解 $\{x_v^*\}_{v \in V}$ 舍入：解 $S = \{v \vert x_v^* \ge \dfrac{1}{2}\}$

解的质量

• 可行：对每条边 $(u, v) \in E$，有 $x_u^* + x_v^* \ge 1$，从而 $x_u^* \ge \dfrac{1}{2}$ 或 $x_v^* \ge \dfrac{1}{2}$，即至少有一个点被选中
• 2-近似：$\vert S \vert \le 2 \mathrm{OPT(LP)} \le 2 \mathrm{OPT(IP)}$

Primal Dual 分析

顶点覆盖问题

• 原始问题：

$$\begin{align*} \text{minimize} &\quad \sum_{v \in V} x_v \\ \text{subject to} &\quad x_u + x_v \geq 1 &&\quad \forall (u,v) \in E \\ &\quad x_v \ge 0 &&\quad \forall v \in V \end{align*}$$

• 对偶问题：

$$\begin{align*} \text{minimize} &\quad \sum_{e \in E} y_e \\ \text{subject to} &\quad \sum_{v \in N(u)} y_{(u, v)} \le 1&&\quad \forall u \in V \\ &\quad y_{(u, v)} \ge 0 &&\quad \forall (u, v) \in E \end{align*}$$

注意到，顶点覆盖问题的对偶问题是最大匹配问题

二分图匹配的贪心算法

• 策略：按任意顺序将 $B$ 中的点与未被匹配的邻居匹配
• 2-近似：对 OPT 中的任意一条边，至少有一个端点被匹配

2-近似的 Primal Dual 证明

• 同时维护一个 Dual 的解：每选中一条边，即 $y_{(u, v)} = 1$，分摊到顶点 $x_u = 0.5$，$x_v = 0.5$，从而有 $\sum_u x_u = \sum_e y_e = \mathrm{ALG}$
• 由于 $\forall (u, v) \in E$，$x_u + x_v \ge 0.5$，

$$2 \cdot \mathrm{ALG} = 2 \cdot \sum_v x_v \ge \mathrm{OPT(Dual)} \ge \mathrm{OPT(Primal)} \ge \mathrm{OPT(Matching\text{ }IP)}$$

在线二分图匹配的 Ranking 算法（分数版本）

• 分配方式：$\mathrm{d}x_u = g(w_u) \mathrm{d}y$，$\mathrm{d}x_v = (1 - g(w_u)) \mathrm{d}y$
• $x_u = \int_0^{w_u} g(y) \mathrm{d}y$，$x_v \ge 1 - g(w_u)$
• 问题变为

  $$\max_{g} \min_{w_u} \int_0^{w_u} g(y) \mathrm{d}y + 1 - g(w_u)$$

  解得最优的 $g(y) = e^{y - 1}$
• $(1 - \dfrac{1}{e})$-competitive