强弱对偶定理

概述

强弱对偶定理（Weak and Strong Duality Theorems）：在线性规划中，原始问题（primal）与对偶问题（dual）之间存在深刻的最优值关系——弱对偶保证原始最优值不超过对偶最优值，强对偶则在最优解存在时保证两者严格相等。

定理陈述

形式化陈述

原始线性规划（标准型）： $\max z={\mathbf{c}}^T\mathbf{x}$ $\text{s.t.}A\mathbf{x}\le \mathbf{b},\mathbf{x}\ge 0$

对偶线性规划： $\min w={\mathbf{b}}^T\mathbf{y}$ $\text{s.t.}{A}^T\mathbf{y}\ge \mathbf{c},\mathbf{y}\ge 0$

---

弱对偶定理（Weak Duality Theorem）： 若 $\mathbf{x}$ 是原始问题的可行解，$\mathbf{y}$ 是对偶问题的可行解，则： ${\mathbf{c}}^T\mathbf{x}\le {\mathbf{b}}^T\mathbf{y}$ 即原始问题的目标函数值不超过对偶问题的目标函数值。

---

强对偶定理（Strong Duality Theorem）： 若原始线性规划有最优解 ${\mathbf{x}}^{\ast }$，则对偶线性规划也有最优解 ${\mathbf{y}}^{\ast }$，且： ${\mathbf{c}}^T{\mathbf{x}}^{\ast }={\mathbf{b}}^T{\mathbf{y}}^{\ast }$ 即两者的最优值严格相等。

证明概要

证明思路

弱对偶的证明（直接推导）

弱对偶的证明非常直接，仅依赖约束条件的代数运算：

1. 设 $\mathbf{x}$ 是原始可行解，$\mathbf{y}$ 是对偶可行解
2. 由原始约束 $A\mathbf{x}\le \mathbf{b}$，且 $\mathbf{y}\ge 0$，左乘 ${\mathbf{y}}^T$： ${\mathbf{y}}^{T}A\mathbf{x}\le {\mathbf{y}}^T\mathbf{b}={\mathbf{b}}^T\mathbf{y}$
3. 由对偶约束 $A^T\mathbf{y}\ge \mathbf{c}$，即 ${\mathbf{y}}^{T}A\ge {\mathbf{c}}^T$，且 $\mathbf{x}\ge 0$，右乘 $\mathbf{x}$： ${\mathbf{y}}^{T}A\mathbf{x}\ge {\mathbf{c}}^T\mathbf{x}$
4. 联合两个不等式： ${\mathbf{c}}^T\mathbf{x}\le {\mathbf{y}}^{T}A\mathbf{x}\le {\mathbf{b}}^T\mathbf{y}$

关键推论：弱对偶意味着对偶问题的任何可行解都给出原始问题最优值的一个上界。

强对偶的证明（互补松弛性）

强对偶的证明更为深刻，核心工具是互补松弛性条件：

1. 互补松弛条件：若 ${\mathbf{x}}^{\ast }$ 和 ${\mathbf{y}}^{\ast }$ 分别是原始和对偶的最优解，则：
   • $y_i^{\ast }(a_i{\mathbf{x}}^{\ast }-b_i)=0$，对每个约束 $i$（原始约束的松弛变量与对偶变量互补）
   • $x_j^{\ast }({\mathbf{a}}^j{\mathbf{y}}^{\ast }-c_j)=0$，对每个变量 $j$（对偶约束的松弛变量与原始变量互补）
2. 证明逻辑：
   • 由弱对偶，${\mathbf{c}}^T{\mathbf{x}}^{\ast }\le {\mathbf{b}}^T{\mathbf{y}}^{\ast }$
   • 若能找到可行解使等号成立，则两者都是最优解
   • 互补松弛条件恰好保证了等号成立：当所有互补松弛条件满足时，${\mathbf{y}}^{T}A\mathbf{x}$ 中的每一项都使不等式取等
3. 存在性论证：通过单纯形法的最优基解，可以构造性地找到满足互补松弛条件的对偶最优解。

参考资源：

• UBC互补松弛性证明：https://www.math.ubc.ca/~anstee/math340/340complementaryslackness.pdf
• Washington大学强对偶定理讲义：https://sites.math.washington.edu//~burke/crs/407/notes/section4.pdf

关键推论

• 对偶间隙（Duality Gap）：弱对偶定义了对偶间隙 $={\mathbf{b}}^T\mathbf{y}-{\mathbf{c}}^T\mathbf{x}\ge 0$。强对偶表明在最优解处对偶间隙为零。
• 互补松弛性（Complementary Slackness）：最优解处，原始约束的松弛变量与对偶变量乘积为零，反之亦然。这是验证最优性的重要工具。
• 无界性推论：若原始问题无界（目标函数可趋向 $+\infty$），则对偶问题不可行；反之亦然。
• Farkas引理：强对偶等价于Farkas引理——线性不等式组可行性的核心判定工具。

应用场景

在算法导论（CLRS）Ch29中的具体应用：

1. 线性规划的对偶解释：对偶变量可解释为原始约束的”影子价格”（shadow prices），反映约束放宽一个单位时目标函数的改善量。
2. 最大流最小割定理：最大流问题可以表述为线性规划，其对偶恰好是最小割问题，强对偶直接推出最大流等于最小割。
3. 算法设计：对偶理论为近似算法提供了下界工具——通过对偶问题的解来估计原始问题的最优值。
4. 动态规划：某些动态规划问题可以转化为线性规划，利用对偶理论获得更深刻的结构理解。

参见

• 动态规划
• 贪心算法
• 最大流
• 模运算
• 数学归纳法