什么是对偶问题？
这篇文章试图回答一个问题：线性规划的对偶问题到底是怎么来的？为什么它长成那个样子？
很多教材直接给出对偶问题的定义，然后列出一堆转化规则让你记。但如果你不知道这些规则背后的道理，记起来会很痛苦，用起来也没有信心。所以我们换一个方式：从一个自然的问题出发，一步步推导出对偶问题的形式。你会发现，对偶问题不是凭空规定的，而是顺着一个简单的想法自然生长出来的。
从一个简单的愿望说起
假设你面对一个线性规划问题：
$$\max \quad 3x_1 + 2x_2$$ $$\text{s.t.} \quad x_1 + x_2 \leq 4$$ $$\quad\quad\quad 2x_1 + x_2 \leq 5$$ $$\quad\quad\quad x_1, x_2 \geq 0$$
这个问题问的是：在满足约束的前提下，目标函数 $3x_1 + 2x_2$ 最大能到多少？
现在假设你不想真正去解这个问题（也许问题太大，也许你只是想快速估计一下），但你想知道：最优值的上界是多少？也就是说，不管最优解是什么，目标函数不可能超过多少？
这个愿望听起来简单，但它会引出整个对偶理论。
一个幸运的观察
让我们盯着约束看一会儿：
$$x_1 + x_2 \leq 4$$ $$2x_1 + x_2 \leq 5$$
如果我把这两个不等式直接加起来，会得到什么？
$$(x_1 + x_2) + (2x_1 + x_2) \leq 4 + 5$$
整理左边：
$$3x_1 + 2x_2 \leq 9$$
你注意到了吗？左边恰好就是我们的目标函数！
这意味着什么？这意味着对于任何满足原约束的 $x_1, x_2$，目标函数 $3x_1 + 2x_2$ 都不可能超过 9。我们不费吹灰之力，就给最优值找到了一个上界。
这就是对偶思想的萌芽：通过把约束"组合"起来，我们可以得到目标函数的上界。
如果没那么幸运呢？
刚才的例子很凑巧，两个约束直接相加就得到了目标函数。但大多数情况下，事情没有这么顺利。
假设目标函数换成 $5x_1 + 3x_2$，我还能用约束"拼"出它吗？
直接相加得到的是 $3x_1 + 2x_2$，系数是 $(3, 2)$，但目标函数的系数是 $(5, 3)$，对不上。
那我能不能给约束加上不同的权重，然后再组合？
设第一个约束乘以权重 $y_1$，第二个约束乘以权重 $y_2$：
$$y_1 \cdot (x_1 + x_2) + y_2 \cdot (2x_1 + x_2) \leq y_1 \cdot 4 + y_2 \cdot 5$$
左边整理一下，按 $x_1$ 和 $x_2$ 归类：
$$(y_1 + 2y_2) x_1 + (y_1 + y_2) x_2 \leq 4y_1 + 5y_2$$
现在左边的系数是 $(y_1 + 2y_2, , y_1 + y_2)$，右边是 $4y_1 + 5y_2$。
问题来了：我能选择怎样的 $y_1, y_2$，使得这个不等式能帮我估计目标函数 $5x_1 + 3x_2$ 的上界？
关键的一步："压住"目标函数
这里有一个微妙但重要的地方，值得停下来仔细说清楚。
我们的目标是证明：$5x_1 + 3x_2 \leq \text{某个数}$。
我们手里有一个不等式：$(y_1 + 2y_2) x_1 + (y_1 + y_2) x_2 \leq 4y_1 + 5y_2$。
如果我能保证左边"压住"目标函数，也就是：
$$5x_1 + 3x_2 \leq (y_1 + 2y_2) x_1 + (y_1 + y_2) x_2$$
那么我就可以把两个不等式串起来：
$$5x_1 + 3x_2 \leq (y_1 + 2y_2) x_1 + (y_1 + y_2) x_2 \leq 4y_1 + 5y_2$$
右端的 $4y_1 + 5y_2$ 就是目标函数的上界了。
现在问题变成：什么条件下，$(y_1 + 2y_2) x_1 + (y_1 + y_2) x_2$ 能"压住" $5x_1 + 3x_2$？
这里要用到 $x_1, x_2 \geq 0$ 这个条件。当变量非负时，如果每个变量前面的系数都更大，那整个表达式就更大。具体地说，只要：
$$y_1 + 2y_2 \geq 5 \quad \text{（$x_1$ 前面的系数要压住 5）}$$ $$y_1 + y_2 \geq 3 \quad \text{（$x_2$ 前面的系数要压住 3）}$$
那么对于任何 $x_1, x_2 \geq 0$，都有 $(y_1 + 2y_2) x_1 + (y_1 + y_2) x_2 \geq 5x_1 + 3x_2$。
这就是"压住"的精确含义。
还有一点不能忘：我们在加权组合约束时，权重 $y_1, y_2$ 必须非负。为什么？因为原约束是"$\leq$"的形式，如果乘以负数，不等号会反向，我们就没法保持"$\leq$"的结构了。
找最紧的上界
现在我们知道，只要 $y_1, y_2$ 满足：
$$y_1 + 2y_2 \geq 5$$ $$y_1 + y_2 \geq 3$$ $$y_1, y_2 \geq 0$$
那么 $4y_1 + 5y_2$ 就是目标函数的一个上界。
不同的 $(y_1, y_2)$ 会给出不同的上界。有些上界很松（比如取 $y_1 = 100, y_2 = 100$，上界是 900，没什么用），有些上界很紧。
我们当然希望找到最紧的上界——也就是最小的 $4y_1 + 5y_2$。
于是我们要解这样一个问题：
$$\min \quad 4y_1 + 5y_2$$ $$\text{s.t.} \quad y_1 + 2y_2 \geq 5$$ $$\quad\quad\quad y_1 + y_2 \geq 3$$ $$\quad\quad\quad y_1, y_2 \geq 0$$
这就是原问题的对偶问题。
用矩阵语言写出一般形式
让我们把刚才的推导过程用矩阵语言重新描述一遍，这样可以得到对偶问题的一般形式。
原问题（用矩阵写）：
$$\max \quad c^T x$$ $$\text{s.t.} \quad Ax \leq b$$ $$\quad\quad\quad x \geq 0$$
这里 $c$ 是目标函数系数向量，$A$ 是约束矩阵，$b$ 是约束右端项。
我们引入权重向量 $y \geq 0$，把所有约束加权组合：
$$y^T (Ax) \leq y^T b$$
也就是：
$$(A^T y)^T x \leq b^T y$$
为了让左边能"压住"目标函数 $c^T x$（在 $x \geq 0$ 的条件下），我们需要：
$$A^T y \geq c$$
满足这个条件后，$b^T y$ 就是目标函数的上界。我们想找最紧的上界，所以要最小化 $b^T y$。
于是对偶问题是：
$$\min \quad b^T y$$ $$\text{s.t.} \quad A^T y \geq c$$ $$\quad\quad\quad y \geq 0$$
现在你应该能看出对偶问题的各个部分是怎么来的了：
原问题的约束右端 $b$ 变成了对偶问题的目标函数系数，因为 $b^T y$ 就是我们要最小化的上界。
原问题的目标函数系数 $c$ 变成了对偶问题的约束右端，因为 $A^T y \geq c$ 是"压住"条件。
原问题有 $m$ 个约束，对偶问题就有 $m$ 个变量（每个约束对应一个权重）。
原问题有 $n$ 个变量，对偶问题就有 $n$ 个约束（每个变量对应一个"压住"条件）。
这些转化规则不是随意规定的，它们都是从"用约束估计上界"这个思想自然推导出来的。
弱对偶定理：显而易见的结论
有了上面的理解，弱对偶定理几乎是不证自明的。
弱对偶定理说：对于任何原问题的可行解 $x$ 和对偶问题的可行解 $y$，有 $c^T x \leq b^T y$。
这不就是我们一直在说的事情吗？对偶可行解 $y$ 给出的 $b^T y$ 是目标函数的上界，所以任何可行解的目标函数值都不可能超过它。
强对偶定理：上界是紧的
弱对偶告诉我们原问题的最优值 $\leq$ 对偶问题的最优值。但会不会存在一个"间隙"——原问题怎么努力也达不到对偶问题给的那个上界？
强对偶定理说：如果原问题有有限最优解，那么对偶问题也有有限最优解，而且两者的最优值相等。
也就是说，不存在间隙。最紧的上界恰好就是原问题能达到的最大值。
这个结论不那么直观，证明需要用到线性规划的一些特殊性质。但从直觉上可以这样理解：线性规划的可行域是多面体，目标函数在顶点达到最优。对偶问题的构造方式恰好"捕捉"了这些顶点的信息，所以能够精确地给出最优值，而不只是一个粗略的估计。
互补松弛：哪些约束真正起作用？
互补松弛定理描述了原问题最优解和对偶问题最优解之间的一种精细关系。
它说的是：在最优解处，如果原问题的某个约束是"松"的（严格小于，没有取等号），那么对偶问题对应的变量必须等于零；反过来，如果对偶变量是正的，那么原问题对应的约束必须是"紧"的（取等号）。
这个结论从我们的推导过程中也可以理解。回想一下，对偶变量 $y_i$ 是第 $i$ 个约束的权重。如果第 $i$ 个约束是松的（有富余空间），那么它对于"卡住"最优解没有贡献，给它分配正的权重是浪费。要让上界尽量紧，就应该把权重集中在那些真正起限制作用的约束上。
所以互补松弛实际上在说：最优的权重分配方案，只会在"真正卡住"最优解的约束上放正的权重。
对偶的对偶是什么？
一个自然的问题：对偶问题的对偶问题是什么？
答案是：原问题。
如果你把对偶问题当作新的"原问题"，按照同样的方法构造它的对偶，你会得到一个和最初的原问题等价的问题。
这种对称性说明原问题和对偶问题是"平等"的。你可以把任何一个当作起点，另一个自然随之确定。之所以叫一个"原问题"、一个"对偶问题"，只是因为我们通常先遇到其中一个而已。
最后的总结
让我们回顾一下对偶问题是怎么来的：
我们想给原问题的最优值找一个上界。方法是把约束加权组合，让组合出来的式子能"压住"目标函数。压住之后，约束右端项的加权和就是上界。为了让上界尽量紧，我们最小化这个加权和。这个最小化问题，就是对偶问题。
从这个角度看，对偶问题不是某种抽象的数学构造，而是回答了一个非常实际的问题：仅仅通过观察约束条件，我能对最优值说些什么？
下次你看到对偶问题的转化规则时，不用死记，试着用"加权组合约束来估计上界"的思路想一想，规则自然就出来了。
评论