4. 对偶理论：原问题与对偶问题的转换、弱对偶定理、强对偶定理与互补松弛性
对偶理论，说白了就是给优化问题找个「镜像世界」。你想想看，每个约束优化问题背后，都藏着一个对偶问题。我刚开始学的时候也觉得这玩意儿有点玄乎，直到后来在项目中用它来解一个大规模线性规划，才发现这玩意儿是真香。
今天咱们就把对偶理论掰开揉碎了讲。核心就四个东西：怎么转换、弱对偶、强对偶、互补松弛性。嗯，一个一个来。
4.1 原问题与对偶问题的转换
先看标准形式。假设我们有一个线性规划的原问题：
原问题（Primal）：
min c^T x
s.t. Ax ≥ b
x ≥ 0它的对偶问题长这样：
对偶问题（Dual）：
max b^T y
s.t. A^T y ≤ c
y ≥ 0这里有个规律，我管它叫「三换」：
- 目标换向：原问题求最小，对偶就求最大
- 约束换向：原问题的 ≥ 约束，对偶里变成 ≤
- 变量换角色：原问题的变量 x，对偶里变成约束的系数；原问题的约束右端项 b，对偶里变成目标系数
核心口诀：原问题有多少个约束，对偶问题就有多少个变量；原问题有多少个变量，对偶问题就有多少个约束。
我在项目中遇到过一种情况：原问题有 10 万个变量，但只有 100 个约束。直接求解原问题，内存直接爆炸。但转成对偶问题后，只有 100 个变量，求解速度飞起。这就是对偶转换的实战价值。
再给个更通用的转换规则，用表格展示：
| 原问题（min） | 对偶问题（max） |
|---|---|
| 约束 Ax ≥ b | 变量 y ≥ 0 |
| 约束 Ax ≤ b | 变量 y ≤ 0 |
| 约束 Ax = b | 变量 y 无约束 |
| 变量 x ≥ 0 | 约束 A^T y ≤ c |
| 变量 x ≤ 0 | 约束 A^T y ≥ c |
| 变量 x 无约束 | 约束 A^T y = c |
这张表我建议你存下来。每次做转换的时候，对着表套就行，不容易出错。
4.2 弱对偶定理
弱对偶定理说的是：原问题的最优值 ≥ 对偶问题的最优值（对于 min 原问题）。
用数学语言表达就是：
对于任意可行解 x（原问题）和 y（对偶问题），有：
c^T x ≥ b^T y为什么会这样？证明其实很简单。因为 x ≥ 0，y ≥ 0，且 Ax ≥ b，A^T y ≤ c，所以：
b^T y ≤ (Ax)^T y = x^T A^T y ≤ x^T c = c^T x嗯，中间那步用了转置的小技巧。我个人习惯把这个不等式叫做「对偶间隙」——它告诉我们原问题和对偶问题之间差了多少。
实战小技巧：弱对偶定理可以用来做「下界估计」。比如你算出一个对偶问题的可行解，它的目标值就是原问题最优值的一个下界。我在做整数规划分支定界时，经常用这个来剪枝。
4.3 强对偶定理
强对偶定理就厉害了。它说：如果原问题和对偶问题都有可行解，那么它们的最优值相等。
也就是说：
min c^T x = max b^T y对偶间隙为 0。
但这里有个前提条件——原问题必须是凸的，而且满足某些约束规格（比如 Slater 条件）。说白了，就是可行域内部不能是空的。
注意：强对偶定理不是无条件成立的。非凸问题、或者约束条件太苛刻时，对偶间隙可能不为 0。我曾经在一个非凸二次规划上吃过亏，对偶解和原理解差了十万八千里，后来才发现是强对偶不成立。
强对偶定理的意义在于：你可以选择求解更容易的那个问题。原问题变量多约束少？转对偶。对偶问题结构更简单？直接解对偶。
4.4 互补松弛性
互补松弛性，我愿称之为对偶理论里「最优雅」的性质。它描述了原问题和对偶问题最优解之间的关系。
假设 x* 是原问题最优解，y* 是对偶问题最优解。那么：
对于每个约束 i：
y_i* · (A_i x* - b_i) = 0
对于每个变量 j：
x_j* · (A^T_j y* - c_j) = 0翻译成人话就是：
- 如果某个约束在原问题中是松的（即 A_i x* > b_i），那么对应的对偶变量 y_i* 必须为 0
- 如果某个对偶变量 y_i* > 0，那么对应的原问题约束必须是紧的（即 A_i x* = b_i）
反过来对变量也一样。
直觉理解：互补松弛性告诉我们，资源（约束）只有在被用尽的时候，才「值得」有价格（对偶变量）。闲置的资源，价格就是 0。
我记得有一次做供应链优化，模型跑出来发现某个仓库的库存约束对应的对偶变量是 0。一开始我还以为是 bug，后来一查，那个仓库确实有大量闲置库存。嗯，互补松弛性诚不欺我。
4.5 知识体系总览
下面这张图把对偶理论的核心逻辑串起来了：
从图上你能看到，原问题和对偶问题通过转换规则相连，弱对偶和强对偶给出了它们之间的数值关系，而互补松弛性则刻画了最优解处的结构特征。
4.6 一个完整的例子
光说不练假把式。咱们看个具体的：
原问题：
min 2x₁ + 3x₂
s.t. x₁ + x₂ ≥ 4
2x₁ + x₂ ≥ 5
x₁, x₂ ≥ 0先转对偶。原问题有 2 个约束，所以对偶有 2 个变量 y₁, y₂。原问题有 2 个变量，所以对偶有 2 个约束。
对偶问题：
max 4y₁ + 5y₂
s.t. y₁ + 2y₂ ≤ 2
y₁ + y₂ ≤ 3
y₁, y₂ ≥ 0求解原问题，最优解是 x* = (1, 3)，最优值 11。求解对偶问题，最优解是 y* = (1, 0.5)，最优值也是 11。对偶间隙为 0，强对偶成立。
检查互补松弛性：
- 约束 1：x₁ + x₂ = 4，紧的 → y₁ = 1 > 0，符合
- 约束 2：2x₁ + x₂ = 5，紧的 → y₂ = 0.5 > 0，符合
- 对偶约束 1：y₁ + 2y₂ = 2，紧的 → x₁ = 1 > 0，符合
- 对偶约束 2：y₁ + y₂ = 1.5 < 3，松的 → x₂ = 3 > 0？等等，这里好像有问题
嗯，仔细看：对偶约束 2 是 y₁ + y₂ ≤ 3，代入 y* 得 1.5 ≤ 3，是松的。根据互补松弛性，对应的 x₂ 应该为 0。但 x₂ = 3 ≠ 0。
哪里出错了？
我检查了一下，发现原问题的变量 x₂ 对应的对偶约束是 y₁ + y₂ ≤ 3，这个约束是松的没错。但互补松弛性说的是：如果对偶约束是松的，那么对应的原问题变量必须为 0。这里 x₂ = 3，确实违反了。
等等，再仔细看——原问题变量 x₂ 对应的对偶约束是 y₁ + y₂ ≤ 3，但原问题变量 x₁ 对应的对偶约束是 y₁ + 2y₂ ≤ 2。我搞混了对应关系。
实际上，x₂ 对应的是对偶的第二个约束 y₁ + y₂ ≤ 3。这个约束在 y* = (1, 0.5) 下是 1.5 ≤ 3，松的。所以 x₂ 应该为 0。但最优解里 x₂ = 3。
这说明什么？说明我算错了对偶问题！
重新检查转换：原问题约束是 Ax ≥ b，对偶变量 y ≥ 0，对偶约束是 A^T y ≤ c。
A = [[1, 1], [2, 1]]，c = [2, 3]^T。
A^T = [[1, 2], [1, 1]]。
对偶约束：y₁ + 2y₂ ≤ 2（对应 x₁），y₁ + y₂ ≤ 3（对应 x₂）。
嗯，这个没错。那问题出在哪？
哦，我明白了！原问题的最优解 (1, 3) 代入约束 2：2×1 + 3 = 5，等于右端项 5，是紧的。所以 y₂ 可以不为 0。但 x₂ = 3 对应的对偶约束 y₁ + y₂ ≤ 3 是松的，所以 x₂ 应该为 0。
这就矛盾了。说明 (1, 3) 不是原问题的最优解？
重新求解一下：
原问题 min 2x₁ + 3x₂，约束 x₁ + x₂ ≥ 4，2x₁ + x₂ ≥ 5，x₁, x₂ ≥ 0。
画图求解：交点 (1, 3) 处目标值 2×1 + 3×3 = 11。另一个顶点 (4, 0) 处目标值 8。还有一个顶点 (0, 5) 处目标值 15。所以最优解确实是 (1, 3)，最优值 11。
那对偶问题呢？max 4y₁ + 5y₂，约束 y₁ + 2y₂ ≤ 2，y₁ + y₂ ≤ 3，y₁, y₂ ≥ 0。
顶点求解：交点 (1, 0.5) 处目标值 4×1 + 5×0.5 = 6.5。另一个顶点 (2, 0) 处目标值 8。还有一个顶点 (0, 1) 处目标值 5。所以对偶最优解是 (2, 0)，最优值 8。
啊，我前面算错了对偶最优解！正确的对偶最优解是 y* = (2, 0)，最优值 8。
但原问题最优值是 11，对偶最优值是 8，对偶间隙 = 3 ≠ 0。这说明强对偶不成立？
等等，再检查一下。原问题 min，对偶 max，弱对偶说 c^T x ≥ b^T y。11 ≥ 8，成立。但强对偶要求相等，这里不相等。
为什么？因为原问题不是标准形式！原问题的约束是 Ax ≥ b，但变量 x ≥ 0。这个形式下，对偶应该是 max b^T y，s.t. A^T y ≤ c，y ≥ 0。没错。
但强对偶成立的条件是原问题有可行解且对偶问题有可行解。这里原问题可行（比如 (4, 0)），对偶问题也可行（比如 (0, 0)），但最优值不相等。
嗯，我犯了一个经典错误——原问题必须是线性规划，且满足约束规格。这个例子中，原问题确实是线性规划，约束规格也满足（Slater 条件：存在严格内点，比如 (5, 5) 满足 Ax > b）。
那为什么强对偶不成立？
我再算一遍对偶问题。max 4y₁ + 5y₂，s.t. y₁ + 2y₂ ≤ 2，y₁ + y₂ ≤ 3，y₁, y₂ ≥ 0。
画图：可行域是 y₁ ≥ 0，y₂ ≥ 0，y₁ ≤ 2 - 2y₂，y₁ ≤ 3 - y₂。
在 y₂ = 0 时，y₁ ≤ 2。在 y₁ = 0 时，y₂ ≤ 1。交点：2 - 2y₂ = 3 - y₂ → -y₂ = 1 → y₂ = -1，不在可行域内。所以两个边界不相交于第一象限。
顶点：
- (0, 0)：目标值 0
- (2, 0)：目标值 8
- (0, 1)：目标值 5
- 边界交点？y₁ + 2y₂ = 2 与 y₁ = 0 交于 (0, 1)，y₁ + y₂ = 3 与 y₂ = 0 交于 (3, 0) 但不在第一个约束内。
所以对偶最优解是 (2, 0)，最优值 8。
原问题最优值 11，对偶最优值 8。对偶间隙 = 3。
这说明什么？说明我举的这个例子，强对偶不成立！
为什么？因为原问题的约束是 Ax ≥ b，但标准形式要求 Ax = b 或者 Ax ≤ b？不对，标准形式可以是 Ax ≥ b。
我查一下资料……哦，我明白了！原问题 min c^T x, s.t. Ax ≥ b, x ≥ 0 的对偶是 max b^T y, s.t. A^T y ≤ c, y ≥ 0，这个没问题。但强对偶成立需要原问题和对偶问题都有有限最优解。
这里原问题有有限最优解 (1, 3)，对偶问题也有有限最优解 (2, 0)，但值不相等。
嗯，实际上我搞错了。强对偶定理说：如果原问题有最优解，那么对偶问题也有最优解，且最优值相等。但这里原问题最优值 11，对偶最优值 8，不相等。
这说明我的计算有误。让我用单纯形法重新求解原问题：
原问题：min 2x₁ + 3x₂，s.t. x₁ + x₂ ≥ 4，2x₁ + x₂ ≥ 5，x₁, x₂ ≥ 0。
引入松弛变量：x₁ + x₂ - s₁ = 4，2x₁ + x₂ - s₂ = 5，s₁, s₂ ≥ 0。
用两阶段法或对偶单纯形法……算了，直接画图吧。
可行域：x₁ + x₂ ≥ 4 的上方，2x₁ + x₂ ≥ 5 的上方，x₁ ≥ 0，x₂ ≥ 0。
顶点：
- 交点 (1, 3)：目标值 11
- 与 x₁ 轴交点 (4, 0)：目标值 8
- 与 x₂ 轴交点 (0, 5)：目标值 15
所以最优解是 (4, 0)，最优值 8！我之前算错了，把 (1, 3) 当成了最优解，实际上 (4, 0) 的目标值更小。
检查 (4, 0) 是否可行：4 + 0 = 4 ≥ 4，2×4 + 0 = 8 ≥ 5，可行。目标值 8。
所以原问题最优解是 (4, 0)，最优值 8。对偶最优解是 (2, 0)，最优值 8。强对偶成立！
互补松弛性检查：
- 约束 1：x₁ + x₂ = 4，紧的 → y₁ = 2 > 0，符合
- 约束 2：2x₁ + x₂ = 8 > 5，松的 → y₂ = 0，符合
- 对偶约束 1：y₁ + 2y₂ = 2，紧的 → x₁ = 4 > 0，符合
- 对偶约束 2：y₁ + y₂ = 2 < 3，松的 → x₂ = 0，符合
完美！
经验之谈：做对偶问题，最容易出错的就是转换规则和最优解计算。我建议你每步都验证一下互补松弛性，它能帮你发现 90% 的计算错误。
4.7 小结
对偶理论的核心就这四块：
- 转换：记住那张对照表，对着套就行
- 弱对偶：原问题值 ≥ 对偶问题值，对偶间隙 ≥ 0
- 强对偶：凸问题 + 约束规格 → 对偶间隙 = 0
- 互补松弛性：松的约束对应 0 变量，紧的约束对应正变量
我个人习惯在每次建模完成后，顺手写出对偶问题。不是为了炫技，而是对偶问题往往能揭示原问题的结构——比如哪些约束是「瓶颈」，哪些资源有「影子价格」。这些信息在实际决策中比最优解本身还有用。
嗯，对偶理论就讲到这里。记住，纸上得来终觉浅，拿个实际问题练练手，比看十遍理论都管用。
公众号:蓝海资料掘金营，微信deep3321