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

给定一个优化问题，我们去理解它的时候，或者设计算法的时候，可以研究它的对偶。

有时候原问题不好解，但它的对偶相对容易。这个时候，可以从对偶问题出发，进而寻求原问题的解。

这篇文章总结了线性规划的对偶形式。按照这个思路，可以方便地写对偶。

考虑线性规划问题的标准型。如下所示，其中 A ∈ R m × n , c , b , x ∈ R n A\in\mathbb{R}^{m\times n}, c,b,x\in \mathbb{R}^n A∈Rm×n,c,b,x∈Rn。 min ⁡   c T x s.t.  A x ≥ b x ≥ 0. \begin{aligned} \min~ & c^Tx \\ \text{s.t. } & Ax \geq b \\ & x\geq 0. \end{aligned} min s.t. ​cTxAx≥bx≥0.​ 它的对偶问题如下，其中 y ∈ R m y\in\mathbb{R}^m y∈Rm 是决策变量。 max ⁡   b T y s.t.  A T y ≤ c y ≥ 0. \begin{aligned} \max~ & b^Ty \\ \text{s.t. } & A^Ty \leq c\\ & y \geq 0. \end{aligned} max s.t. ​bTyATy≤cy≥0.​ 对比两者的形式，注意下面几点：

值得注意的是，线性规划的标准型一般写成等式约束形式（如下所示）。 min ⁡   c T x s.t.  A x = b x ≥ 0. \begin{aligned} \min~ & c^Tx \\ \text{s.t. } & Ax = b \\ & x\geq 0. \end{aligned} min s.t. ​cTxAx=bx≥0.​ 它的对偶问题，是下面这个样子。 max ⁡   b T y s.t.  A T y ≤ c \begin{aligned} \max~ & b^Ty \\ \text{s.t. } & A^Ty \leq c\\ \end{aligned} max s.t. ​bTyATy≤c​ 注意到变化了吗？跟之前的形式相比，上式中对偶变量的非负约束 y ≥ 0 y\geq 0 y≥0 不见了。

前面介绍了线性规划的标准型（两种形式），以及相应的对偶问题。下面讲手写对偶问题的思路。

第一步，定义对偶变量。一个约束对应一个变量（忽略非负约束）。

第二步，约束乘以变量。然后得到对偶问题的目标。

第三步，再得到对偶问题的约束。

第四步，得到结果。

例1，写出它的对偶问题。

min ⁡   c T x s.t.  A x ≥ b → α B x = d → β x ≥ 0 \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} min s.t. ​cTxAx≥bBx=dx≥0​→α→β​

例2，考虑非矩阵形式。

min ⁡   − 50 x 1 + 20 x 2 s.t.  2 x 1 − x 2 ≥ − 5 3 x 1 + x 2 ≥ 3 2 x 1 − 3 x 2 ≤ 12 x 1 , x 2 ≥ 0 \begin{aligned} \min~ & -50x_1 + 20x_2\\ \text{s.t. } & 2x_1-x_2 \geq -5\\ & 3x_1+x_2\geq 3 \\ & 2x_1 -3x_2 \leq 12 \\ & x_1,x_2 \geq 0 \end{aligned} min s.t. ​−50x1​+20x2​2x1​−x2​≥−53x1​+x2​≥32x1​−3x2​≤12x1​,x2​≥0​ 注意第三个不等式，它的方向是小于等于。可以先写成大于等于，然后再写它的对偶。

给两道练习题，请试着写出它们的对偶。

第一题

其中 x i , j , y i x_{i,j}, y_i xi,j​,yi​ 是决策变量，且常量非负。 min ⁡   ∑ i = 1 m ∑ j = 1 n c i , j x i , j + ∑ i = 1 m f i y i  s.t.  ∑ i = 1 m x i , j = 1 , ∀ j → α j x i , j ≤ y i , ∀ i , j → β i , j x i , j ≥ 0 , y i ≥ 0 , ∀ i , j \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} min  s.t. ​i=1∑m​j=1∑n​ci,j​xi,j​+i=1∑m​fi​yi​i=1∑m​xi,j​=1,∀jxi,j​≤yi​,∀i,jxi,j​≥0,yi​≥0,∀i,j​→αj​→βi,j​​

它的对偶如下。 max ⁡   ∑ j = 1 n α j  s.t.  α j − β i , j ≤ c i , j , ∀ i , j β i , j ≤ f i , ∀ i , j β i , j ≥ 0 , ∀ i , j \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} max  s.t. ​j=1∑n​αj​αj​−βi,j​≤ci,j​,∀i,jβi,j​≤fi​,∀i,jβi,j​≥0,∀i,j​

第二题

其中 x i , j x_{i,j} xi,j​ 是决策变量，且常量非负。 min ⁡   ∑ i = 1 n ∑ j = 1 n l i , j x i , j s.t.  ∑ j = 1 n x i , j − ∑ j = 1 n x j , i = 0 , ∀ i ≠ 1 , n → y i ∑ j = 1 n x 1 , j − ∑ j = 1 n x j , 1 = 1 → y 1 ∑ j = 1 n x n , j − ∑ j = 1 n x j , n = − 1 → y n x i , j ≥ 0 , ∀ i , j \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} min s.t. ​i=1∑n​j=1∑n​li,j​xi,j​j=1∑n​xi,j​−j=1∑n​xj,i​=0,∀i​=1,nj=1∑n​x1,j​−j=1∑n​xj,1​=1j=1∑n​xn,j​−j=1∑n​xj,n​=−1xi,j​≥0,∀i,j​→yi​→y1​→yn​​

它的对偶如下。 max ⁡   y 1 − y n s.t.  y i − y j ≤ l i , j , ∀ i , j = 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} max s.t. ​y1​−yn​yi​−yj​≤li,j​,∀i,j=1,2,...,n.​

这一题算对偶约束有些麻烦，我解释一下。

思路是这样的，约束乘对偶变量之后，要计算 x i , j x_{i,j} xi,j​的系数之和，记作 f i j ( y ) f_{ij}(y) fij​(y)，然后得到对偶问题的约束 f i j ( y ) ≤ l i j f_{ij}(y) \leq l_{ij} fij​(y)≤lij​， ∀ i , j = 1 , 2 , . . . , n \forall i, j = 1, 2, ... ,n ∀i,j=1,2,...,n。

下面是详细的计算过程。

先看第一组约束: ∑ j = 1 n y i ⋅ x i , j − ∑ j = 1 n y i ⋅ x j , i = 0. ( a ) \sum_{j=1}^n y_i \cdot x_{i,j} - \sum_{j=1}^n y_ i \cdot x_{j,i} = 0.\qquad (a) j=1∑n​yi​⋅xi,j​−j=1∑n​yi​⋅xj,i​=0.(a) 其中 i = 2 , 3 , . . . , n − 1 i=2, 3, ..., n-1 i=2,3,...,n−1。

先算 i , j ≠ 1 , n i,j\neq 1, n i,j​=1,n 时 x i , j x_{i,j} xi,j​ 的系数。

看 ( a ) (a) (a) 的第一项， x i , j x_{i,j} xi,j​ 的系数是 y i y_i yi​。这还没完，因为其他地方会出现 x i , j x_{i,j} xi,j​。看 ( a ) (a) (a) 的第二项，当 i , j i,j i,j 的值交换时，第二项中 x i , j x_{i,j} xi,j​ 的系数是 − y j -y_j −yj​。

以 x 2 , 3 x_{2,3} x2,3​ 为例， 它的系数之和由两项组成，一个是 y 2 y_2 y2​，来自约束 i = 2 i=2 i=2 中的第一部分 y i ⋅ x i , j y_i \cdot x_{i,j} yi​⋅xi,j​，其中 i = 2 , j = 3 i=2, j=3 i=2,j=3 ；

另一个是 − y 3 -y_3 −y3​，来自不等式 i = 3 i=3 i=3 中的第二部分 y i ⋅ x j , i y_i\cdot x_{j,i} yi​⋅xj,i​，其中 i = 3 , j = 2 i=3, j=2 i=3,j=2。

这样一来， x i , j x_{i,j} xi,j​ 的系数之和为 f i , j ( y ) = y i − y j , ∀ i , j ≠ 1 , n . f_{i,j}(y) = y_i - y_j, \quad \forall i,j \neq 1, n. fi,j​(y)=yi​−yj​,∀i,j​=1,n.

接下来还有三种情况要考虑，分别是：

(1) i = 1 ; j = 1 , . . . , n i=1;\quad j=1, ..., n i=1;j=1,...,n

(2) i = n ; j = 1 , . . . , n i=n; \quad j=1, ..., n i=n;j=1,...,n

(3) i = 2 , . . . , n ; j = 1 , n i=2,...,n; \quad j=1, n i=2,...,n;j=1,n

再结合第二组和第三组约束： ∑ j = 1 n y 1 ⋅ x 1 , j − ∑ j = 1 n y 1 ⋅ x j , 1 = y 1 ( b ) ∑ j = 1 n y n ⋅ x n , j − ∑ j = 1 n y n ⋅ x j , n = − y n ( c ) \begin{aligned} \sum_{j=1}^n y_1 \cdot x_{1,j} - \sum_{j=1}^n y_1 \cdot x_{j,1} = y_1 &\qquad (b)\\ \sum_{j=1}^n y_n \cdot x_{n,j} - \sum_{j=1}^n y_n \cdot x_{j,n} = -y_n &\qquad (c) \end{aligned} j=1∑n​y1​⋅x1,j​−j=1∑n​y1​⋅xj,1​=y1​j=1∑n​yn​⋅xn,j​−j=1∑n​yn​⋅xj,n​=−yn​​(b)(c)​

分别考虑上述三种情况：

(1) i = 1 ; j = 1 , . . . , n i=1;\quad j=1, ..., n i=1;j=1,...,n

观察 ( b ) (b) (b)，得到 f 1 , 1 ( y ) = y 1 − y 1 = 0 f_{1,1}(y) = y_1 - y_1 =0 f1,1​(y)=y1​−y1​=0。

结合 ( b ) , ( c ) (b),(c) (b),(c)，看 ( b ) (b) (b) 第一项和 ( c ) (c) (c) 第二项，得到 f 1 , n ( y ) = y 1 − y n f_{1,n}(y)=y_1-y_n f1,n​(y)=y1​−yn​。

结合 ( b ) , ( a ) (b),(a) (b),(a)，看 ( b ) (b) (b) 第一项和 ( a ) (a) (a) 第二项，得到 f 1 , j ( y ) = y 1 − y j f_{1,j}(y)=y_1-y_j f1,j​(y)=y1​−yj​，其中 j = 2 , . . . , n − 1 j=2, ..., n-1 j=2,...,n−1。

我们有 f 1 , j ( y ) = y 1 − y j , j = 1 , . . . , n . f_{1,j}(y) = y_1-y_j, \quad j=1,...,n. f1,j​(y)=y1​−yj​,j=1,...,n.

(2) i = n ; j = 1 , . . . , n i=n; \quad j=1, ..., n i=n;j=1,...,n

结合 ( c ) , ( b ) (c), (b) (c),(b)，看 ( c ) (c) (c) 第一项和 ( b ) (b) (b) 第二项，得到 f n , 1 ( y ) = y n − y 1 f_{n,1}(y)=y_n-y_1 fn,1​(y)=yn​−y1​。

观察 ( c ) (c) (c)，得到 f n , n ( y ) = y n − y n = 0 f_{n,n}(y) = y_n - y_n =0 fn,n​(y)=yn​−yn​=0。

结合 ( c ) , ( a ) (c),(a) (c),(a)，看 ( c ) (c) (c) 第一项和 ( a ) (a) (a) 第二项，得到 f n , j ( y ) = y n − y j f_{n,j}(y)=y_n-y_j fn,j​(y)=yn​−yj​，其中 j = 2 , . . . , n − 1 j=2, ..., n-1 j=2,...,n−1。

我们有 f n , j ( y ) = y n − y j , j = 1 , . . . , n . f_{n,j}(y) = y_n-y_j, \quad j=1,...,n. fn,j​(y)=yn​−yj​,j=1,...,n.

(3) i = 2 , . . . , n ; j = 1 , n i=2,...,n; \quad j=1, n i=2,...,n;j=1,n

结合 ( a ) , ( b ) (a), (b) (a),(b)，看 ( a ) (a) (a) 第一项和 ( b ) (b) (b) 第二项，得到 f i , 1 ( y ) = y i − y 1 f_{i,1}(y)=y_i-y_1 fi,1​(y)=yi​−y1​。

结合 ( a ) , ( c ) (a), (c) (a),(c)，看 ( a ) (a) (a) 第一项和 ( c ) (c) (c) 第二项，得到 f i , n ( y ) = y i − y n f_{i,n}(y)=y_i-y_n fi,n​(y)=yi​−yn​。

我们有 f i , 1 ( y ) = y i − y 1 , i = 2 , . . . , n f i , n ( y ) = y i − y n , i = 2 , . . . , n \begin{aligned} f_{i,1}(y) = y_i-y_1, \quad i=2,...,n\\ f_{i,n}(y) = y_i-y_n,\quad i=2,...,n \end{aligned} fi,1​(y)=yi​−y1​,i=2,...,nfi,n​(y)=yi​−yn​,i=2,...,n​

综合 (1) (2) (3) 三种情况，我们得到 f i , j ( y ) = y i − y j , i = 1 , . . . , n , j = 1 , . . . , n . f_{i,j}(y) = y_i-y_j,\quad i=1,...,n, j=1,...,n. fi,j​(y)=yi​−yj​,i=1,...,n,j=1,...,n.

这样一来，得到对偶问题的约束 y i − y j ≤ l i , j i = 1 , . . . , n , j = 1 , . . . , n . y_i-y_j\leq l_{i,j}\quad i=1,...,n, j=1,...,n. yi​−yj​≤li,j​i=1,...,n,j=1,...,n.

从这两个练习题，我们还可以看到，它们的对偶问题，形式上比原问题更简单。所以说设计算法的时候，对偶是个好工具。

在线性规划中，对偶的对偶，就是原问题。这两个习题还可以再做一次，把对偶当作原问题，然后再写一次对偶，得到之前的原问题。