线性规划技巧: 如何写对偶问题

给定线性规划的原始问题, 本文介绍写如何方便地写出其对偶问题.

基本公式

我们先给出互为对偶问题的两种基本形式, 作为后续写对偶问题的基础.

1. 原问题的约束是不等式

2. 原问题的约束是等式

总结

原问题的一个约束对应一个对偶变量.
对偶变量乘以原问题约束的右端( $b$ )得到对偶问题的目标.
原问题目标的系数 $c$ 对应对偶问题约束的右端.
最小化对应最大化(反之亦然).
如果原问题有等式约束, 对偶变量没有非负要求.

方法

1. 定义对偶变量

对原问题的每一个约束, 定义一个对偶变量 $y_i$ . 如果一个约束是等式, 其对偶变量无非负限制.

2. 对偶变量乘约束

把对偶变量乘以原问题的约束. 约束右端 $b^Ty$ 即为对偶问题的目标.

3. 计算 $x$ 的系数

上一步把对偶变量乘以原问题的约束之后, 接着计算原问题约束中决策变量 $x$ 的系数 $f(y) = A^Ty$ , 从而得到对偶问题的约束 $f(y) \leq c$ (假设原问题是最小化问题).

例子

1. 矩阵形式

原问题
$\begin{aligned} \min ~ & c^Tx \\ \text{s.t. } & Ax \geq b & \rightarrow \quad \alpha \\ & Bx = d & \quad \rightarrow \quad \beta \\ & x \geq 0 \end{aligned}$

定义对偶变量 $\alpha$ , $\beta$ , 分别对应原问题的约束 $Ax\geq b$ 和 $Bx=d$ .

用 $b^T, d^T$ 乘以 $\alpha$ , $\beta$ 然后求和得到对偶目标: $b^T\alpha + d^T\beta$
用 $A^T, B^T$ 乘以 $\alpha, \beta$ 然后求和得到约束: $A^T \alpha + B^T\beta \leq c$
$\beta$ 对应等式约束, 因此不要求非负

对偶问题
$\begin{aligned} \min~& b^T \alpha + d^T \beta \\ \text{s.t. } & A^T \alpha + B^T \beta \leq c \\ & \alpha \geq 0 \end{aligned}$

2. 非矩阵形式

原问题

$\begin{aligned} \min ~ & \sum_{i=1}^n \sum_{j=1}^n l_{i,j} x_{i,j} \\ \text{s.t. } & \sum_{j=1}^n x_{i,j} - \sum_{j=1}^n x_{j,i} = 0, \quad \forall i\neq 1, n \quad & \rightarrow \quad y_i \\ & \sum_{j=1}^n x_{1,j} - \sum_{j=1}^n x_{j,1} = 1 & \rightarrow \quad y_1 \\ & \sum_{j=1}^n x_{n,j} - \sum_{j=1}^n x_{j,n} = -1 & \rightarrow \quad y_n \\ & x_{i,j} \geq 0, \quad \forall i, j \end{aligned}$

如上面所示, 我们定义对偶变量 $y_i$ , $i=1, 2, ..., n$ . 原问题的约束是等式约束, 因此不要求 $y_i$ 非负. 用 $y_i$ 乘以每个等式, 得到对偶问题的目标: $(1, 0, ..., 0, -1) \cdot y = y_1 - y_n$ . 下面计算对偶问题的约束:

给定 $i,j$ , 计算原问题约束中 $x_{i,j}$ 的 系数之和, 记作 $f_{ij}(y)$ .
得到对偶问题的约束: $f_{ij}(y) \leq l_{ij}$

为了方便描述, 我们使用新的下标 $s, t$ , 并计算 $x_{s, t}$ 的系数. 详细的计算过程如下:

第一组约束:
$(a): \sum_{j=1}^n y_i \cdot x_{i,j} - \sum_{j=1}^n y_ i \cdot x_{j,i} = 0$ . 注意 $i=2, 3, ..., n-1$ .

当 $i=s$ 时, $x_{s, j}$ 的系数是 $y_s$ , $\forall j$
当 $i=t$ 时, $x_{j, t}$ 的系数是 $-y_t$ , $\forall j$
$x_{s,t}$ 的系数之和是 $y_s-y_t$ . 注意: $s, t \neq 1, n$ .
得到对偶问题的约束: $x_{s, t} \leq l_{s,t}$ , $\forall s, t \neq 1, n$

第二组和第三组约束:
$(b): \sum_{j=1}^n y_1 \cdot x_{1,j} - \sum_{j=1}^n y_1 \cdot x_{j,1} = y_1$
$(c): \sum_{j=1}^n y_n \cdot x_{n,j} - \sum_{j=1}^n y_n \cdot x_{j,n} = -y_n$

当 $s=1, t=n$ 时, $x_{1, n}$ 的系数之和为 $y_1-y_n$ (参考 $(b), (c)$ )
当 $s=1, t=1$ 时, $x_{1,1}$ 的系数之和为 $y_1-y_1=0$ (参考 $(b)$ )
当 $s=1$ , $t=2, ..., n-1$ 时, $x_{1,t}$ 的系数之和为 $y_1 - y_t$ (参考 $(b), (a)$ )
当 $s=n, t=1$ 时, $x_{n, 1}$ 的系数之和为 $y_n - y_1$ (参考 $(b), (c)$ )
当 $s=n, t=n$ 时, $x_{n, n}$ 的系数之和为 $y_n - y_n$ (参考 $(c)$ )
当 $s=n, t=2, ..., n-1$ 时, $x_{n, t}$ 的系数之和为 $y_n - y_t$ (参考 $(c), (a)$ )

综合上面所有对偶问题的约束, 我们得到:
$y_s - y_t \leq l_{s,t}, \quad \forall s, t = 1,2, ..., n.$

对偶问题
$\begin{aligned} \max ~ & y_1 - y_n \\ \text{s.t. } & y_i - y_j \leq l_{ i, j}, \quad \forall i, j = 1, 2, ... ,n. \end{aligned}$

练习

Ex1

原问题

$\begin{aligned} \min ~ & \sum_{i=1}^m \sum_{j=1}^n c_{i,j} x_{i,j} + \sum_{i=1}^m f_i y_i \\ \text{ s.t. } & \sum_{i=1}^m x_{i, j} = 1,\quad \forall j & \rightarrow \quad \alpha_j \\ & x_{i, j} \leq y_i, \quad \forall i, j & \rightarrow \quad \beta_{ i, j} \\ & x_{i, j} \geq 0, y_i \geq 0, \quad \forall i, j \end{aligned}$

对偶问题

$\begin{aligned} \max ~ & \sum_{j=1}^n \alpha_j \\ \text{ s.t. } & \alpha_j - \beta_{i,j} \leq c_{i,j}, \quad \forall i,j \\ & \beta_{i, j} \leq f_i, \quad \forall i, j \\ & \beta_{i, j} \geq 0, \quad \forall i, j \end{aligned}$

Ex2

原问题
$\begin{aligned} \max ~ & \sum_{e \in E} w_e x_e \\ \text{ s.t. } & \sum_{e\ni v} x_e = 1, \quad \forall v\in V \quad \rightarrow y_v \\ & x_e \geq 0 \end{aligned}$