KNOWECON WIKI

ARTICLE

对偶理论

对偶理论 (Duality Theory) 对偶理论是数学规划与最优化理论中的核心方法论，研究每一个最优化问题（称为原始问题，Primal Problem）如何自然地关联到另一个最优化问题（称为对偶问题，Dual Problem）。原始问题与对偶问题之间存在深刻的数学关系，包括弱对偶性、强对偶性以及互补松弛条件，这些关系不仅是理论分析的基石，也是算法设计和经

浏览 5 更新 2026-05-25

对偶理论 (Duality Theory)

对偶理论是数学规划与最优化理论中的核心方法论，研究每一个最优化问题（称为原始问题，Primal Problem）如何自然地关联到另一个最优化问题（称为对偶问题，Dual Problem）。原始问题与对偶问题之间存在深刻的数学关系，包括弱对偶性、强对偶性以及互补松弛条件，这些关系不仅是理论分析的基石，也是算法设计和经济解释的源泉。

线性规划中的对偶

对于标准形式的线性规划原始问题：

min⁡cTxs.t.Ax≥b,x≥0\begin{aligned} \min \quad & \mathbf{c}^T \mathbf{x} \\ \text{s.t.} \quad & A\mathbf{x} \geq \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0} \end{aligned}

其对偶问题为：

max⁡bTys.t.ATy≤c,y≥0\begin{aligned} \max \quad & \mathbf{b}^T \mathbf{y} \\ \text{s.t.} \quad & A^T \mathbf{y} \leq \mathbf{c}, \quad \mathbf{y} \geq \mathbf{0} \end{aligned}

其中 x∈Rn\mathbf{x} \in \mathbb{R}^n 为原始变量，y∈Rm\mathbf{y} \in \mathbb{R}^m 为对偶变量（也称影子价格）。对偶变量 y\mathbf{y} 的经济含义是：第 ii 个约束资源每增加一个单位，目标函数最优值的边际改善量。

核心定理

弱对偶定理

若 x\mathbf{x} 为原始问题的可行解，y\mathbf{y} 为对偶问题的可行解，则恒有：

cTx≥bTy\mathbf{c}^T \mathbf{x} \geq \mathbf{b}^T \mathbf{y}

换言之，原始问题的任意目标值总是不低于对偶问题的任意目标值。原始目标的最小值与对偶目标的最大值之间形成一个"对偶间隙"。

强对偶定理

若原始问题存在最优解 x∗\mathbf{x}^*，则对偶问题也存在最优解 y∗\mathbf{y}^*，且：

cTx∗=bTy∗\mathbf{c}^T \mathbf{x}^* = \mathbf{b}^T \mathbf{y}^*

即对偶间隙为零。该定理是线性规划单纯形法的理论保证，也是内点法的基础。

互补松弛条件

设 x∗\mathbf{x}^* 和 y∗\mathbf{y}^* 分别为原始和对偶最优解，则：

  • 若 xj∗>0\mathbf{x}_j^* > 0，则 (ATy∗)j=cj(A^T\mathbf{y}^*)_j = c_j（原始变量为正时，对偶约束紧）
  • 若 (ATy∗)j<cj(A^T\mathbf{y}^*)_j < c_j，则 xj∗=0\mathbf{x}_j^* = 0（对偶约束松弛时，原始变量为零）

互补松弛条件揭示了原始变量与对偶约束之间"一紧一松"的互补关系，在经济学中对应着"零利润"或"资源稀缺性"的直觉。

对偶的经济解释

在经济学框架下，对偶理论提供了一种"价格视角"来理解资源配置问题：

  • 原始问题（数量视角）：给定资源约束，求解最优生产计划（数量决策）。
  • 对偶问题（价格视角）：给定投入品价格，求解最优定价方案（价格决策）。

对偶变量 y\mathbf{y} 的本质是资源的影子价格，衡量资源稀缺性。这一思想贯穿成本函数与生产函数、支出函数与间接效用函数之间的对偶关系，是微观经济学中谢泼德引理和罗伊恒等式的基础。

拉格朗日对偶

对于一般的非线性规划问题：

min⁡xf(x)s.t.gi(x)≤0,  hj(x)=0\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{s.t.} \quad g_i(\mathbf{x}) \leq 0, \; h_j(\mathbf{x}) = 0

构造拉格朗日函数 L(x,λ,μ)=f(x)+∑iλigi(x)+∑jμjhj(x)\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = f(\mathbf{x}) + \sum_i \lambda_i g_i(\mathbf{x}) + \sum_j \mu_j h_j(\mathbf{x})，其中 λi≥0\lambda_i \geq 0 为不等式约束的拉格朗日乘子。拉格朗日对偶函数定义为：

θ(λ,μ)=inf⁡xL(x,λ,μ)\theta(\boldsymbol{\lambda}, \boldsymbol{\mu}) = \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\mu})

对偶问题为 max⁡λ≥0,μθ(λ,μ)\max_{\boldsymbol{\lambda} \geq \mathbf{0}, \boldsymbol{\mu}} \theta(\boldsymbol{\lambda}, \boldsymbol{\mu})。当原始问题是凸规划且满足约束品性时，强对偶性成立。

应用场景

  1. 支持向量机 (SVM)：原始问题是最大化分类间隔，其对偶问题引入核函数，使高维特征空间的计算成为可能。
  2. 经济学：支出最小化与效用最大化互为对偶，成本最小化与产出最大化互为对偶。
  3. 博弈论：零和博弈中，玩家1的最小最大策略与玩家2的最大最小策略构成线性规划对偶。
  4. 网络流问题：最大流问题与最小割问题构成对偶。

对偶理论不仅提供了求解优化问题的替代路径，更揭示了问题结构的深层对称性，是现代数学规划不可绕过的核心理论。