本文共 1128 字，大约阅读时间需要 3 分钟。

对偶问题简介

在优化理论中，对偶问题是将原问题通过拉格朗日法转换而来的对偶形式。原问题通常表示为：

$$ \min_{x \mid c(x) \geq 0} f(x) $$

其对偶问题则表示为：

$$ \max_{\lambda \geq 0} \min_{x \mid c(x) \geq 0} (f(x) - \lambda c(x)) $$

其中，$\lambda$ 称为对偶变量。

线性规划的对偶问题

对于线性规划问题，原问题通常表示为：

$$ \min z = c^T x \quad \text{s.t.} \quad A x \geq b, \quad x \geq 0 $$

其对偶问题通过拉格朗日法转换后为：

$$ \max y \geq 0 \quad \min_{x \mid A x \geq b} (c^T x - y (A x - b)) $$

通过KKT条件，我们可以进一步简化对偶问题为：

$$ \max_{y \geq 0} b^T y \quad \text{s.t.} \quad A^T y \leq c^T, \quad y \geq 0 $$

对偶问题的性质

对偶单纯形法

对偶单纯形法是对偶问题的求解方法，类似于单纯形法但方向相反。与原问题保持约束 $c \geq 0$，通过平移（pivoting）使约束 $b \geq 0$ 满足。

对偶单纯形法的优势在于：

• 不需要两阶段法，初始可行解较容易找到。
• 对于MILP问题，商用求解器通常使用对偶单纯形法求解松弛线性规划问题，通过变量分支提高效率。

例子说明

假设原问题为：

$$ \min c^T x \quad \text{s.t.} \quad A x = b, \quad x \geq 0 $$

其对偶问题为：

$$ \max y \geq 0 \quad \min_{x} (c^T x - y (A x - b)) $$

通过KKT条件，得到对偶问题的最优解与原问题最优解满足一定关系。

结论

通过上述分析，可以看出对偶问题在优化理论中具有重要地位。对偶单纯形法作为求解对偶问题的高效方法，广泛应用于实数线性规划和整数线性规划中。