KNOWECON WIKI

ARTICLE

dual problem

对偶问题 (Dual Problem) 对偶问题 (Dual Problem) 是优化理论中的核心概念，指从一个原始优化问题（原问题，Primal Problem）通过系统的数学变换衍生出的另一个优化问题。对偶问题与原问题之间存在深刻的对偶关系：原问题的最优值提供对偶问题的上界（或下界），而强对偶性成立时二者精确相等。对偶理论不仅为求解复杂优化问题提供了新的

浏览 0 更新 2025-10-26

对偶问题 (Dual Problem)

对偶问题 (Dual Problem) 是优化理论中的核心概念，指从一个原始优化问题（原问题，Primal Problem）通过系统的数学变换衍生出的另一个优化问题。对偶问题与原问题之间存在深刻的对偶关系：原问题的最优值提供对偶问题的上界（或下界），而强对偶性成立时二者精确相等。对偶理论不仅为求解复杂优化问题提供了新的途径，也为经济学、博弈论、工程优化和机器学习等领域提供了理论洞察。

对偶问题的构造——从 Lagrange 函数出发

考虑一般形式的约束优化问题（原问题）：

min⁡x∈Rnf(x)s.t.gi(x)≤0,i=1,…,mhj(x)=0,j=1,…,p\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \le 0, \quad i = 1, \dots, m \\ & h_j(x) = 0, \quad j = 1, \dots, p \end{aligned}

其中 f(x) f(x) 为目标函数，gi(x)≤0 g_i(x) \le 0 为不等式约束，hj(x)=0 h_j(x) = 0 为等式约束。定义该问题的 Lagrange 函数：

L(x,λ,ν)=f(x)+∑i=1mλigi(x)+∑j=1pνjhj(x)\mathcal{L}(x, \lambda, \nu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \nu_j h_j(x)

其中 λi≥0 \lambda_i \ge 0 和 νj∈R \nu_j \in \mathbb{R} 分别为不等式约束和等式约束的 Lagrange 乘子。在此基础上，Lagrange 对偶函数定义为：

d(λ,ν)=inf⁡x∈RnL(x,λ,ν)d(\lambda, \nu) = \inf_{x \in \mathbb{R}^n} \mathcal{L}(x, \lambda, \nu)

对偶函数的关键性质是：对于任意 λ≥0 \lambda \ge 0 和任意 ν \nu ，它给出原问题最优值 p∗ p^* 的一个下界，即 d(λ,ν)≤p∗ d(\lambda, \nu) \le p^* 。这一性质源于约束条件的结构——在可行域内，Lagrange 函数中的约束项非正（对不等式约束）或为零（对等式约束），因此 L(x,λ,ν)≤f(x) \mathcal{L}(x, \lambda, \nu) \le f(x) 。

为了获得最好的下界，自然要对 d(λ,ν) d(\lambda, \nu) 在 λ≥0 \lambda \ge 0 的约束下求极大，由此引出对偶问题：

max⁡λ,νd(λ,ν)s.t.λ≥0\begin{aligned} \max_{\lambda, \nu} \quad & d(\lambda, \nu) \\ \text{s.t.} \quad & \lambda \ge 0 \end{aligned}

记对偶问题的最优值为 d∗ d^* ，则总是有 d∗≤p∗ d^* \le p^* ，这一关系称为 弱对偶性 (Weak Duality)。弱对偶性不依赖任何凸性假设，是优化理论中最普遍的结论之一。

强对偶性与 Slater 条件

当 d∗=p∗ d^* = p^* 时，称 强对偶性 (Strong Duality) 成立。强对偶性的成立条件与原问题的结构密切相关。对于凸优化问题（f f 和 gi g_i 为凸函数，hj h_j 为仿射函数），强对偶性通常在 Slater 条件 下成立：存在 x∈relint D x \in \text{relint } \mathcal{D} 使得对所有 i=1,…,m i = 1, \dots, m 有 gi(x)<0 g_i(x) < 0 。换言之，存在一个严格满足所有不等式约束的内点。

当强对偶性成立时，原问题与对偶问题的最优解满足一组称为 KKT 条件 (Karush–Kuhn–Tucker Conditions) 的必要充分条件。其中最关键的是 互补松弛性 (Complementary Slackness)：λi∗gi(x∗)=0 \lambda_i^* g_i(x^*) = 0 ，即如果某个不等式约束的 Lagrange 乘子 λi∗>0 \lambda_i^* > 0 ，则该约束在对偶最优解处必然紧致（gi(x∗)=0 g_i(x^*) = 0 ）；反之，若约束不紧致，则对应的乘子为零。

在非凸问题中，对偶差距（p∗−d∗>0 p^* - d^* > 0 ）通常严格为正。尽管如此，对偶函数仍然能为非凸问题提供有意义的下界估计，这在组合优化和整数规划中具有重要的实用价值。

线性规划中的对偶性

线性规划是对偶理论最经典的应用场景。考虑标准形式的原问题：

min⁡xc⊤xs.t.Ax≥b,x≥0\begin{aligned} \min_{x} \quad & c^\top x \\ \text{s.t.} \quad & Ax \ge b, \quad x \ge 0 \end{aligned}

其对偶问题为：

max⁡yb⊤ys.t.A⊤y≤c,y≥0\begin{aligned} \max_{y} \quad & b^\top y \\ \text{s.t.} \quad & A^\top y \le c, \quad y \ge 0 \end{aligned}

线性规划中的对偶性具有丰富而对称的结构：原问题中约束的数量等于对偶问题中变量的数量，原问题中变量的数量等于对偶问题中约束的数量；原问题中的目标系数 c c 在对偶中变为约束右端项，而原问题中的约束右端项 b b 在对偶中变为目标系数。

线性规划的强对偶定理指出：如果原问题和对偶问题中至少一个有有限的最优解，那么另一个也有有限的最优解，且二者最优值相等。更重要的是，原问题与对偶问题的最优解通过互补松弛性相互确定——这意味着求解其中一个问题等价于求解另一个。

对偶单纯形法 巧妙地利用这一关系：当原问题不可行但其对偶可行时，可以在对偶空间中迭代以保持对偶可行性，逐步逼近最优解。这种方法在某些情形下——例如在割平面法和重新优化（re-optimization）任务中——比原始单纯形法更为高效。

对偶问题在各学科中的应用

在经济学中，对偶问题为影子价格提供了严格的理论基础。在线性规划框架下，对偶变量恰好度量了约束右端项的边际价值——即放松一单位约束所能带来的目标函数改善程度，其大小直接反映了稀缺资源的配置效率。这一思想延伸至一般均衡理论：消费者的间接效用函数和支出函数之间构成对偶关系，生产者的利润函数和成本函数亦然。

在博弈论中，对偶理论构成了 零和博弈 极小极大定理的核心。对于双人零和博弈，原问题对应一方的最小化策略，对偶问题对应另一方的最大化策略，而强对偶性保证了纳什均衡的存在性，且二人最优值精确相等。

在机器学习中，SVM (Support Vector Machine) 的求解过程是应用对偶理论的典型案例。支持向量机的原问题是一个二次规划，通过构造 Lagrange 对偶将其转化为仅约束于 αi \alpha_i 的对偶问题，使核技巧能够自然地引入——内积运算被核函数替代，从而将算法隐式地映射到高维特征空间。此外，对偶性也是深度学习优化理论中用于分析泛化误差的重要工具。

在约束优化算法的实践中，增广 Lagrange 方法 和 ADMM (Alternating Direction Method of Multipliers) 都建立在对偶更新的框架之上。这些方法通过交替更新原始变量和对偶变量来逼近最优解，在大规模分布式优化中表现出色。

对偶问题不仅仅是优化理论中的数学工具——它是一种深刻的对称性思维，揭示了约束与目标、最小化与最大化之间的内在联系。从最优化到经济学、从博弈论到机器学习，对偶视角为我们提供了一条理解复杂决策系统的统一线索。