什么是线性规划？

线性规划，简单地来说就是在一系列线性约束下最优化一个线性函数的过程。

例如如下就是一个线性规划问题： \[ \begin{aligned} \text{minimize}\quad &7x_1+4x_2+3x_3\\ \text{subject to}\quad &4x_1+2x_2-x_3\ge 50 \\ &2x_1+x_2+3x_3\ge 20 \\ &x_1,x_2,x_3 \ge 0 \end{aligned} \] 这部分自己很早以前就会了。

在近似算法设计当中关于线性规划重要的一点是：它是可以在多项式时间内求得最优解的。具体的方法对于我们不重要，可以使椭圆形法或者其他内点法，反正只要知道可以就行了 —— 我们就指望着它来帮助我们设计近似算法呢。

为什么要对偶？

对于一个最小化（最大化类似）的线性规划，我们问一个问题：

目标函数是否可以 \(\le \alpha\)？

答案如果是肯定的，这个问题有没有一个简短的肯定证明（Yes Certificate）？显然是有的：我们只要把一组目标函数是 \(\alpha\) 的变量取值写出来，对方很快就可以验证我们的正确性。（“简短” 与 “很快” 均指多项式空间与时间内，有简短肯定证明的问题被称为 \(\mathsf{NP}\) 问题）

那答案如果是否定的呢？这个问题有没有一个简短的否定证明（No Certificate）？直觉上这就难了。（有简短否定证明的问题被称为 \(\textsf{co-NP}\) 问题，它和 \(\mathsf{NP}\) 的关系是至今计算机界悬而未决的）

幸好我们知道线性规划 \(\in \mathsf{P}\)，而 \(\mathsf{P}\subseteq \textsf{NP} \cap \textsf{co-NP}\)。也就是说确实是有否定回答的 —— 是什么呢？（嘛，其实对于多项式时间算法，把算法的过程作为否定证明也可以算是 “简短” 的，因为一样的算法可以在多项式时间内验证它）

如果我们可以给目标函数一个 \(>\alpha\) 的下界，不就证明目标函数不可能 \(\le \alpha\) 了吗？

目标函数的下界是什么？

\(0\)？这个下界太平凡了。

观察系数，因为 \(x_1,x_2,x_3\ge 0\)，而约束二式的各项系数都不大于目标函数的各项系数，因此 \[ \begin{aligned} 7x_1+4x_2+3x_3 \ge 4x_1+2x_2-x_3 \ge 50 \\ 7x_1+4x_2+3x_3 \ge 2x_1+x_2+3x_3 \ge 20 \\ \end{aligned} \] 这个下界可以更好： \[ 7x_1+4x_2+3x_3 \ge (4x_1+2x_2-x_3)+(2x_1+x_2+3x_3) \ge 70 \] 或者更好？ \[ 7x_1+4x_2+3x_3 \ge (4x_1+2x_2-x_3)+\frac{4}{3}(2x_1+x_2+3x_3) \ge \frac{230}{3} \] 这样下去会不会没完没了？不妨设两个约束的系数是 \(y_1,y_2\ge0\)，那我们的下界就是 \(50y_1+20y_2\)。 \[ \begin{aligned} 7x_1+4x_2+3x_3 &\ge y_1(4x_1+2x_2-x_3)+y_2(2x_1+x_2+3x_3) \\ &=(4y_1+2y_2)x_1+(2y_1+y_2)x_2+(-y_1+3y_2)x_3 \\ &\ge 50y_1+20y_2 \end{aligned} \] 为了确保我们上面的推理没有问题，约束和的各项系数不应大于目标函数的各项系数，因此又有 \(4y_1+2y_2\le 7\)，\(2y_1+y_2\le 4\)，\(-y_1+3y_2\le 3\)。我们希望下界越紧越好，所以 \(50y_1+20y_2\) 要越大越好 —— 我们想到了什么？另一个线性规划！ \[ \begin{aligned} \text{maximize}\quad &50y_1+20y_2\\ \text{subject to}\quad &4y_1+2y_2\le 7 \\ &2y_1+y_2\le 4 \\ &-y_1+3y_2\le 3 \\ &y_1,y_2\ge 0 \end{aligned} \] 这就是所谓的 “对偶线性规划”。如果我们给出一组 \(y_1,y_2\) 使得这个的目标函数 \(>\alpha\)，那么我们原来规划的目标函数就不可能 \(\le \alpha\)，即这就是我们所寻找的简短否定证明。

如果我们要求这个对偶规划的目标上界（也就是再对偶），不难发现我们又回到了最初的线性规划。

而由我们构造对偶规划的过程，不难明白为什么所有变量都要非负，为什么对偶问题的变量数等于原问题的约束数，约束数等于原问题的变量数，为什么最小化问题的约数要转化成 \(\ge\) 的形式，最大化问题的约数要转化成 \(\le\) 的形式，为什么对偶前后不等号方向会变化等问题。

一旦知道对偶的目的，这些步骤豁然开朗，而这些在大多教科书里是略过不讲的，或者先抛给你对偶的方式，再把这个目的冠以 “弱对偶定理” 的名号塞给你（此处点名《算法导论》），或许我们在阅读证明的时候能够明白这些步骤的用处，但是不免还是有些云里雾里。

但是严谨地走一遍还是必要的，此处给出线性规划对偶的定义：对于线性规划 \[ \begin{aligned} \text{minimize}\quad &\sum_{j=1}^nc_jx_j\\ \text{subject to}\quad &\sum_{j=1}^na_{ij}x_j\ge b_i \quad \forall i =1,2,\cdots,m \\ &x_1, x_2, \cdots, x_n\ge0 \end{aligned} \] 其对偶线性规划（Dual）为 \[ \begin{aligned} \text{maximize}\quad &\sum_{i=1}^mb_iy_i\\ \text{subject to}\quad &\sum_{i=1}^ma_{ij}y_i\le c_j \quad \forall j =1,2,\cdots,n \\ &y_1, y_2, \cdots, y_m\ge0 \end{aligned} \] 此时一开始的线性规划被称为主线性规划（Primal）。反之亦然。

所谓弱对偶原理 \[ \sum_{j=1}^nc_jx_j \ge\sum_{i=1}^mb_iy_i \] 的证明： \[ \begin{aligned} \sum_{j=1}^nc_jx_j &\ge \sum_{j=1}^n\left(\sum_{i=1}^ma_{ij}y_i\right)x_j \\ &= \sum_{i=1}^m\left(\sum_{j=1}^na_{ij}x_j\right)y_i \\ &\ge \sum_{i=1}^m b_iy_i \end{aligned} \] 这其实就是我们之前例子中论述的严谨版本，注意到两个不等号之所以成立，不仅仅是因为 \(\sum_{i=1}^ma_{ij}y_i \le c_j\) 以及 \(\sum_{j=1}^na_{ij}x_j\ge b_i\)，还有 \(x_j\ge 0\) 和 \(y_i\ge 0\)，因此变量必须是非负的。

除此以外，更强的一个结论被称为强对偶原理：对偶规划与主规划的最优解相等。证明参见《算法导论》，在近似算法设计中，弱对偶原理才是最重要的。

互补松弛条件

令 \((x_1^*,x_2^*,\cdots,x_n^*)\) 与 \((y_1^*,y_2^*,\cdots,y_m^*)\) 为主线性规划和对偶线性规划的最优解，强对偶原理表明 \[ \sum_{j=1}^nc_jx_j^*=\sum_{i=1}^mb_iy_i^* \] 回过头看我们弱对偶原理的证明过程，两个不等号必须同时取等，于是便得到两个条件，成为所谓的互补松弛条件（Complementary Slackness Condition）：

主互补松弛条件：\(x_j^*=0\) 或者 \(\sum_{i=1}^ma_{ij}y_i = c_j\)，即要么变量为 \(0\)，要么对偶规划里面的对应约束取等。

对偶互补松弛条件：\(y_i^*=0\) 或者 \(\sum_{j=1}^na_{ij}x_j = b_i\)，即要么变量为 \(0\)，要么主规划里面的对应约束取等。