Linear Programming and Duality Theory.
本文目录：
- 线性规划问题 Linear Programming
- 弱对偶形式 Weak Duality
- 强对偶形式 Strong Duality
1. 线性规划问题 Linear Programming
线性规划(linear programming)问题是指求解线性约束下的线性函数最小值问题：
\[\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}\]而根据弱对偶形式有：
\[\mathop{\max}_{y} \{ b^Ty |A^Ty\leq c\} \leq \mathop{\min}_{x} \{ c^Tx | Ax=b , x \geq 0 \}\]注意到对任意$\epsilon > 0$上述两个不等式恒成立。不妨取$\epsilon$为无穷小的正数，根据两边夹定理则有：
\[\mathop{\max}_{y} \{ b^Ty |A^Ty\leq c\} = \mathop{\min}_{x} \{ c^Tx | Ax=b , x \geq 0 \}\]
