Linear Programming and Duality Theory.

本文目录：

线性规划问题 Linear Programming
弱对偶形式 Weak Duality
强对偶形式 Strong Duality

1. 线性规划问题 Linear Programming

线性规划(linear programming)问题是指求解线性约束下的线性函数最小值问题：

\begin{matrix} min x & c^{T} x s.t. & A x = b x \geq 0 \end{matrix}

$\begin{aligned} \mathop{\min}_{x} & \quad c^Tx \\ \text{s.t. } & \quad Ax=b \\ & \quad x \geq 0 \end{aligned}$

其中 $x,c \in \Bbb{R}^n, b \in \Bbb{R}^m, A \in \Bbb{R}^{m\times n}$ ； $Ax=b$ 表示 $m$ 个等式约束。

等价地，线性规划问题也可以写作：

$\mathop{\min}_{x} \{ c^Tx | Ax=b , x \geq 0 \}$

有时线性规划问题难以直接求解，因此转而寻找线性规划问题的对偶形式(duality)。一般地，对偶是指将原问题转化为一个等价的、但具有不同形式的新问题；将新问题通过同样形式的变换后能够还原为原问题。解决对偶问题，就等价地解决了原问题；在实践中可以灵活地选择两者中形式更简单的进行解决。

2. 弱对偶形式 Weak Duality

线性规划问题的原问题是一个最小值问题，不妨假设最小值在 $x^{*}$ 处取得，此时有 $Ax^{*}=b$ ；在等式两边左乘 $y \in \Bbb{R}^m$ ，则有：

$y^TAx^{*}=y^Tb$

若引入约束条件 $A^Ty \leq c$ 或等价地 $y^TA\leq c^T$ ，根据 $x\geq 0$ 则有：

$y^TAx^{*}\leq c^Tx^{*} =\mathop{\min}_{x} \{ c^Tx | Ax=b , x \geq 0 \}$

结合上述两式可得：

$y^Tb\leq c^Tx^{*} =\mathop{\min}_{x} \{ c^Tx | Ax=b , x \geq 0 \}$

注意到上式对任意满足 $A^Ty\leq c$ 的 $y$ 均成立，则对满足约束条件下使得 $y^Tb$ 取值最大的情况也成立：

$\mathop{\max}_{y} \{ b^Ty |A^Ty\leq c\} \leq \mathop{\min}_{x} \{ c^Tx | Ax=b , x \geq 0 \}$

上式即为线性规划问题的弱对偶形式。弱对偶形式将一个最小值问题转换为一个最大值问题，给出了原问题的一个下界。

进一步地，若两个问题相等，则称为强对偶形式。

3. 强对偶形式 Strong Duality

线性规划问题的强对偶形式为：

$\mathop{\max}_{y} \{ b^Ty |A^Ty\leq c\} = \mathop{\min}_{x} \{ c^Tx | Ax=b , x \geq 0 \}$

对于线性规划问题来说，强对偶形式是成立的；证明过程需要借助Farkas引理。

⚪ Farkas引理

对于矩阵 $A \in \Bbb{R}^{m\times n}$ 和向量 $b \in \Bbb{R}^m$ ，下面两种情况有且只有一种成立：

存在 $x \in \Bbb{R}^n$ 且 $x\geq 0$ ，使得 $Ax=b$ ；
存在 $y \in \Bbb{R}^m$ ，使得 $A^Ty \leq 0$ 且 $b^Ty > 0$ 。

下面提供一种几何视角的证明：

将矩阵 $A$ 看作 $n$ 个 $m$ 维列向量的组合 $A=(a_1,a_2,\cdots a_n)$ ，考虑集合：

$\{ Ax |x \in \Bbb{R}^n, x\geq 0 \}$

上述集合构成了矩阵 $A$ 的所有列向量的非负线性组合，在空间中构成了一个“锥体”：

对于任意向量 $b \in \Bbb{R}^m$ ，则在空间中应具有两种情况：在锥体内部(包括边界)和在锥体外部。

若向量 $b$ 在锥体内部(包括边界)，则 $b$ 可以表示为矩阵 $A$ 列向量的非负线性组合，即存在 $x \geq 0$ ，使得 $Ax=b$ 。此即第一种情况。

若向量 $b$ 在锥体外部，则总可以找到一个向量 $y \in \Bbb{R}^m$ ，使得 $y$ 与矩阵 $A$ 所有列向量的夹角都为钝角，表示为：

$(a_1^Ty \leq 0, a_2^Ty \leq 0, \cdots a_n^Ty \leq 0) \quad \leftrightarrow \quad A^Ty \leq 0$

且向量 $y$ 与向量 $b$ 的夹角为锐角，表示为 $b^Ty \geq 0$ 。此即第二种情况。

⚪ 证明线性规划的强对偶形式

仍然假设原问题的最小值在 $x^{*}$ 处取得，且对应的最小值为 $z^{*}=c^Tx^{*}$ 。构造如下矩阵：

$\hat{A} = \begin{pmatrix} A \\ -c^T \end{pmatrix} \in \Bbb{R}^{(m+1)\times n}, \hat{b}_{\epsilon} = \begin{pmatrix} b \\ -z^*+\epsilon \end{pmatrix} \in \Bbb{R}^{m+1}$

当 $\epsilon>0$ 时，对于 $\forall x \geq 0$ ， $\hat{A}^Tx=\hat{b}_{\epsilon}$ 不成立。这是因为 $-z^{*}$ 已经是 $-c^Tx$ 的最大值，不可能存在一个更大的值 $-z^{*}+\epsilon$ 。则根据Farkas引理，存在 $\hat{y} \in \Bbb{R}^{m+1}$ ，使得 $\hat{A}^T\hat{y} \leq 0$ 且 $\hat{b}_{\epsilon}^T\hat{y} > 0$ 。

不妨将 $\hat{y}$ 记为 $\hat{y} = \begin{pmatrix} y \\ \alpha \end{pmatrix}$ ，则有：

$A^Ty \leq \alpha c, \quad b^Ty \geq \alpha(z^*-\epsilon)$

注意到当 $\epsilon > 0$ 时有 $\hat{b}_{\epsilon}^T\hat{y} = \hat{b}_{0}^T\hat{y}+\alpha \epsilon > 0$ 。另一方面，当 $\epsilon = 0$ 时有 $\hat{A}x^{*}=\hat{b}_{0}^T$ ，满足Farkas引理的第一种情况；则第二种情况不成立，即恒有 $\hat{b}_{\epsilon}^T\hat{y}<0$ 。结合上述两种情况可知当 $\epsilon > 0$ 时有 $\alpha \epsilon > 0$ ，即 $\alpha > 0$ 。此时有：

$A^T\frac{y}{\alpha} \leq c, \quad b^T\frac{y}{\alpha} \geq z^*-\epsilon$

即存在一个 $y$ 在满足约束条件 $A^Ty \leq c$ 下使得 $b^Ty \geq z^{*}-\epsilon$ ；显然 $b^Ty$ 的最大值也是满足的：

$\begin{aligned} \mathop{\max}_{y} \{ b^Ty |A^Ty\leq c\} & \geq z^*-\epsilon \\ & = \mathop{\min}_{x} \{ c^Tx | Ax=b , x \geq 0 \} -\epsilon \end{aligned}$

而根据弱对偶形式有：