线性规划对偶性的直观理解：从上界到对偶定理
本文围绕一个简单的线性规划例子，说明：
- 怎么“仅根据约束”给目标函数找上界；
- 怎么用多个约束的线性组合得到更紧的上界；
- 这些上界怎么自然地变成一个新的线性规划——对偶问题；
- 最后给出 弱对偶定理 及其证明。➡️
考虑下面的线性规划（Linear Programming）问题（原问题 / Primal LP）：
\[\begin{eqnarray} \max _{x_1,x_2} &\quad& 2x_1 + 3x_2 \nonumber\\ \text{s.t.} && 4x_1 + 8x_2 \le 12, \nonumber\\ && 2x_1 + x_2 \le 3, \nonumber\\ && 3x_1 + 2x_2 \le 4, \nonumber\\ && x_1, x_2 \ge 0. \end{eqnarray}\]
下面给出其对偶线性规划（Dual LP）的直观推导过程。
1. 例子：从最大化问题出发
如果将 \(\max _{x_1,x_2} 2x_1 + 3x_2\) 理解为找目标函数 \(2x_1 + 3x_2\) 的上界，则可以将这个 LP 问题描述为：
- 找一个常数 \(U\)，使得对所有满足约束的 \((x_1,x_2)\) 都有： \[\begin{equation} 2x_1 + 3x_2 \le U. \end{equation}\]
能不能不求解这个最优化问题本身，只利用约束条件， 就推导出目标函数的一个上界？
1.1 只用第一个约束得到一个粗上界
先看第一个约束： \[\begin{equation} 4x_1 + 8x_2 \le 12, \end{equation}\] 又因为 \(x_1,x_2 \ge 0\)，系数都是正数，显然： \[\begin{equation} 2x_1 + 3x_2 \le 4x_1 + 8x_2 \le 12, \end{equation}\]
于是我们得到了 \(2x_1 + 3x_2\) 的一个上界。
进一步： \[\begin{equation} 2x_1 + 3x_2 \le 2x_1 + 4x_2 = \tfrac12(4x_1 + 8x_2) , \end{equation}\]
于是 \[\begin{align} 2x_1 + 3x_2 &\le \tfrac12(4x_1 + 8x_2) \nonumber\\ &= 6. \end{align}\]
这给出了一个更小的上界。
但是：
- 这个上界只用了第一个约束；
- 实际上很可能在可行域内根本取不到这么大的值，
- 因为还要同时满足另外两个约束。
自然的想法是：
能不能在这个上界的基础上，利用其他约束， 找到一个更小、更紧的上界？
1.2 再利用第二个约束得到更紧的上界
现在试着把第一个约束和第二个约束加在一起：
\[\begin{equation} \left\{ {\begin{array}{*{20}{l}} {4{x_1} + 8{x_2} \le 12,}\\ {2{x_1} + {x_2} \le 3.} \end{array}} \right. \Rightarrow 6{x_1} + 9{x_2} \le 15. \end{equation}\]
于是： \[\begin{align} 2x_1 + 3x_2 &= \tfrac13(6x_1 + 9x_2) \nonumber\\ &\le \tfrac13 \cdot 15 \nonumber\\ &= 5. \end{align}\]
这就得到一个更紧的上界。
小结：通过对约束做“缩放 + 加法”，我们把上界从 12 压到了 6，再压到了 5。
自然继续追问：
用这样“对约束做非负线性组合”的办法，
最多能把目标函数 \(2x_1 + 3x_2\) 的上界压到多小？
换句话说：
在所有可以由约束推得的上界中，最小的那个上界是多少？
这个问题可以用另一个 LP 问题来描述。
1.3 问题重述
1.3.1 不等式推导
我们想做的是从原来的约束中，推导出一个不等式：
\[\begin{align} \label{eq:dual_inequality} d_1 x_1 + d_2 x_2 \le h, \end{align}\]
满足：
- 对所有可行 \((x_1,x_2)\) 都成立（也就是不等式 是由所有约束条件推得的）；
- 系数满足：
\[\begin{equation} d_1 \ge 2, \quad d_2 \ge 3, \end{equation}\] 这样才能保证： \[\begin{equation} 2x_1 + 3x_2 \le d_1 x_1 + d_2 x_2; \end{equation}\]
- 而 \(h\) 要尽量小，这样得到的上界越紧、越接近真实最优值。
原来的 LP 问题就变成：
如何系统地构造这样的 \(d_1,d_2,h\) ？
确保每个约束都满足的关键是：
将原问题的所有约束进行非负线性组合，来推导需要的不等式。
具体到我们的例子，给三个约束分别乘 \(y_1,y_2,y_3 \ge 0\) 然后再相加，并把左边按 \(x_1,x_2\) 合并：
\[\begin{equation} \left\{ \begin{array}{l} {y_1}\left( {4{x_1} + 8{x_2} \le 12} \right),\\ {y_2}\left( {2{x_1} + {x_2} \le 3} \right),\\ {y_3}\left( {3{x_1} + 2{x_2} \le 4} \right). \end{array} \right. \Rightarrow \left( {4{y_1} + 2{y_2} + 3{y_3}} \right){x_1} + \left( {8{y_1} + {y_2} + 2{y_3}} \right){x_2} \le 12{y_1} + 3{y_2} + 4{y_3} \end{equation}\]
于是，我们得到了一个形如 \(d_1 x_1 + d_2 x_2 \le h\) 的不等式，其中，
\[\begin{equation} d_1 = 4y_1 + 2y_2 + 3y_3,\quad d_2 = 8y_1 + y_2 + 2y_3,\quad h = 12y_1 + 3y_2 + 4y_3. \nonumber \end{equation}\]
为了让 \(h\) 成为目标函数的上界，还要要求： \[\begin{equation} d_1 \ge 2,\quad d_2 \ge 3. \end{equation}\]
把 \(d_1,d_2\) 的表达式代进去，得到对 \(y\) 的约束：
\[\begin{eqnarray} &&4y_1 + 2y_2 + 3y_3 \ge 2, \nonumber\\ &&8y_1 + y_2 + 2y_3 \ge 3, \nonumber\\ &&y_1, y_2, y_3 \ge 0. \label{eq:dual_constraints} \end{eqnarray}\]
此时，对任意可行的 \(x_1,x_2\) 都有：
\[\begin{equation} 2x_1 + 3x_2 \le d_1 x_1 + d_2 x_2 \le h = 12y_1 + 3y_2 + 4y_3. \end{equation}\]
也就是说：
如果能够找到满足上述不等式的 \((y_1,y_2,y_3)\) ，就能给出原目标函数 \(2x_1+3x_2\) 相应的一个上界 \(h\)。 我们希望的是这个上界尽可能地小，这样才能逼近原问题的最优值。
1.3.2 从“找最好上界”到“对偶线性规划”
要做的事可以总结为：
在所有满足 中约束的 \((y_1,y_2,y_3)\) 里，
让 \(h = 12y_1 + 3y_2 + 4y_3\) 尽可能小。
这本身就是一个线性规划：
\[\begin{aligned} \min_{y_1,y_2,y_3}\quad & 12y_1 + 3y_2 + 4y_3 \\ \text{s.t.}\quad & 4y_1 + 2y_2 + 3y_3 \ge 2, \\ & 8y_1 + y_2 + 2y_3 \ge 3, \\ & y_1, y_2, y_3 \ge 0. \end{aligned}\]这个线性规划就是原问题的 对偶问题（Dual LP）。
最大化优化问题的对偶问题在做的事就是——
在所有“由约束线性组合得到的上界”当中，
找一个最小的上界。
7. 一般形式：矩阵-向量写法的对偶
考虑标准型线性规划：
\[\begin{aligned} \text{(P)}\quad \max\quad & c^\top x \\ \text{s.t.}\quad & Ax \le b, \\ & x \ge 0. \end{aligned}\]其中
- \(x \in \mathbb{R}^n\)：原问题变量；
- \(c \in \mathbb{R}^n\)：目标函数系数；
- \(A \in \mathbb{R}^{m\times n}\)：约束系数矩阵；
- \(b \in \mathbb{R}^m\)：约束右端项。
给每个约束乘上一个非负系数 \(y_i \ge 0\)，把它们写成向量形式：
- \(y \in \mathbb{R}^m\)：对偶变量（每个分量对应一条约束）。
把 \(Ax \le b\) 左右同时左乘 \(y^\top\)，得到
\[ y^\top A x \le y^\top b = b^\top y. \]
另一方面，若要求
[ A^T y c, ]
那就有
[ c^T x y^T A x. ]
两者合并得到
[ c^T x y^T A x b^T y. ]
只要
[ \[\begin{cases} Ax \le b,\ x \ge 0, &(\text{原问题可行}) \\ A^T y \ge c,\ y \ge 0, &(\text{对偶可行}) \end{cases}\]]
就必然有
[ c^T x b^T y. ]
这说明：
- 任意一个对偶可行的 (y)，都会给出原问题目标函数 (c^Tx) 的一个上界 (b^Ty)；
- 如果我们想要最紧的上界，就要让 (b^Ty) 尽量小。
于是得到一般形式的对偶问题：
[ \[\begin{aligned} \text{(D)}\quad \min\quad & b^T y \\ \text{s.t.}\quad & A^T y \ge c, \\ & y \ge 0. \end{aligned}\]]
这就是图里蓝底部分写的那句话：
“更一般地，
(c^T x Axb, x) 的对偶是
(b^T y A^T yc, y)。”
8. 弱对偶定理（Weak Duality）
到这里，可以正式写出 弱对偶定理。
定理（弱对偶）
设 (x) 是原问题 (P) 的任意可行解，(y) 是对偶问题 (D) 的任意可行解，则有 [ c^T x ;; b^T y. ] 换句话说： - 对“最大化”的原问题来说， 任意对偶可行解的目标值都是原问题最优值的上界； - 对“最小化”的对偶问题来说， 任意原问题可行解的目标值都是对偶最优值的下界。
证明
由原问题可行性 (Ax b) 和对偶变量非负 (y )，有
[ y^T A x y^T b = b^T y. ]
由对偶问题可行性 (A^T y c)，对任意 (x ) 有
[ c^T x (A^T y)^T x = y^T A x. ]
把两条不等式连起来：
[ c^T x y^T A x b^T y. ]
证毕。
9. 小结：从“上界”到“对偶”
从一个具体的线性规划出发，我们先问： > 能否只用约束给目标函数找一个上界？
先用一个约束，得到一个粗上界；
再用多个约束的缩放与加法，得到更紧的上界；
把“给每个约束乘一个非负系数再相加”的方法参数化为对偶变量 (y)；
发现对任意对偶可行 (y)，(b^Ty) 都是原问题目标函数的一个上界；
于是自然得到一个新的线性规划——对偶问题 (D)：在这些上界中找一个最小的；
弱对偶定理则形式化地说明：
对任意原问题可行解 (x) 和任意对偶可行解 (y)，
总有 (c^Tx b^Ty)。
在后续，如果再引入强对偶定理，可以解释为什么在适当条件下，
原问题和对偶问题的最优值实际上是相等的——
这就是“对偶线性规划对原问题的估计是 perfectly tight” 的含义。