KNOWECON WIKI

ARTICLE

弱对偶定理

弱对偶定理 (Weak Duality Theorem) 弱对偶定理（Weak Duality Theorem）是线性规划与凸优化理论中的基石性结论，揭示了原问题（Primal Problem）与对偶问题（Dual Problem）之间目标函数值的基本不等式关系。该定理断言：对于任意原可行解与任意对偶可行解，原问题的目标值在对偶问题的目标值之上（极小化原问题

浏览 3 更新 2025-10-26

弱对偶定理 (Weak Duality Theorem)

弱对偶定理（Weak Duality Theorem）是线性规划与凸优化理论中的基石性结论，揭示了原问题（Primal Problem）与对偶问题（Dual Problem）之间目标函数值的基本不等式关系。该定理断言：对于任意原可行解与任意对偶可行解，原问题的目标值在对偶问题的目标值之上（极小化原问题情形）或之下（极大化原问题情形）。弱对偶定理不仅是强对偶定理的逻辑前提，也是设计对偶单纯形法、分支定界算法以及推导经济学影子价格性质的关键工具。

线性规划中的弱对偶定理

考虑标准形式的线性规划原问题（P）及其对偶问题（D）。设原问题为极小化：

(P)min⁡c⊤xs.t.Ax=b,x≥0\begin{aligned} \text{(P)} \quad \min \quad & \mathbf{c}^\top \mathbf{x} \\ \text{s.t.} \quad & \mathbf{A}\mathbf{x} = \mathbf{b}, \\ & \mathbf{x} \geq \mathbf{0} \end{aligned}

其中 A∈Rm×n\mathbf{A} \in \mathbb{R}^{m \times n}，c,x∈Rn\mathbf{c}, \mathbf{x} \in \mathbb{R}^n，b∈Rm\mathbf{b} \in \mathbb{R}^m。对应的对偶问题为极大化：

(D)max⁡b⊤ys.t.A⊤y≤c\begin{aligned} \text{(D)} \quad \max \quad & \mathbf{b}^\top \mathbf{y} \\ \text{s.t.} \quad & \mathbf{A}^\top \mathbf{y} \leq \mathbf{c} \end{aligned}

其中 y∈Rm\mathbf{y} \in \mathbb{R}^m 为对偶变量（在经济学中常解释为影子价格）。注意对偶变量 y\mathbf{y} 在此形式下为自由变量，无符号约束。

弱对偶定理：若 x\mathbf{x} 是（P）的可行解，y\mathbf{y} 是（D）的可行解，则必有

c⊤x≥b⊤y\mathbf{c}^\top \mathbf{x} \geq \mathbf{b}^\top \mathbf{y}

即原问题目标值不小于对偶问题目标值。

证明：直接利用可行性条件即可完成简洁推导：

c⊤x−b⊤y=c⊤x−(Ax)⊤y\mathbf{c}^\top \mathbf{x} - \mathbf{b}^\top \mathbf{y} = \mathbf{c}^\top \mathbf{x} - (\mathbf{A}\mathbf{x})^\top \mathbf{y}

\quad (\because A\mathbf{A}x\mathbf{x} = b\mathbf{b})

=c⊤x−x⊤A⊤y=x⊤(c−A⊤y)≥0= \mathbf{c}^\top \mathbf{x} - \mathbf{x}^\top \mathbf{A}^\top \mathbf{y} = \mathbf{x}^\top (\mathbf{c} - \mathbf{A}^\top \mathbf{y}) \geq 0

最后一步成立，因为 x≥0\mathbf{x} \geq \mathbf{0}（原可行性）且 A⊤y≤c\mathbf{A}^\top \mathbf{y} \leq \mathbf{c}（对偶可行性），故两者内积非负。□\square

对于对称形式的线性规划——原问题为 max⁡{c⊤x∣Ax≤b,x≥0}\max \{ \mathbf{c}^\top \mathbf{x} \mid \mathbf{A}\mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0} \}，对偶为 min⁡{b⊤y∣A⊤y≥c,y≥0}\min \{ \mathbf{b}^\top \mathbf{y} \mid \mathbf{A}^\top \mathbf{y} \geq \mathbf{c}, \mathbf{y} \geq \mathbf{0} \}——弱对偶不等式方向反转：

c⊤x≤b⊤y\mathbf{c}^\top \mathbf{x} \leq \mathbf{b}^\top \mathbf{y}

即极大化原问题的目标值不超过极小化对偶问题的目标值。无论哪种形式，弱对偶的核心直观是一致的：原问题目标值永远不可能优于对偶问题目标值——两者之间存在的"对偶间隙"（Duality Gap）始终非负。

弱对偶定理的推论

弱对偶定理本身仅给出不等式关系，但从中可推导出若干极具实用价值的结构性结论：

  1. 有界性蕴含对偶可行：若原问题存在可行解且目标值有下界，则对偶问题必然可行。反之，若对偶问题不可行，则原问题或不可行或无下界。
  2. 无界性蕴含不可行：若原问题无下界（目标值趋于 −∞-\infty），则对偶问题必定不可行。对称地，若对偶问题无上界，则原问题必定不可行。这一逻辑是单纯形算法中检测无界性的理论基础。
  3. 最优性的充分条件：若能找到一对可行解 x∗\mathbf{x}^* 和 y∗\mathbf{y}^* 使得 c⊤x∗=b⊤y∗\mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^*（对偶间隙为零），则 x∗\mathbf{x}^* 和 y∗\mathbf{y}^* 必分别为原问题与对偶问题的最优解。此即强对偶定理的核心前提：若两者相等，则已达最优。
  4. 互补松弛性的推导基础：弱对偶证明中的不等式 x⊤(c−A⊤y)≥0\mathbf{x}^\top(\mathbf{c} - \mathbf{A}^\top \mathbf{y}) \geq 0 若取等号，意味着对于每个分量 jj，要么 xj=0x_j = 0，要么 (c−A⊤y)j=0(\mathbf{c} - \mathbf{A}^\top \mathbf{y})_j = 0，此即互补松弛定理（Complementary Slackness）的内在逻辑。

对偶间隙的经济解释

在经济学语境中，弱对偶定理具有清晰的福利含义。以企业利润最大化为例：设原问题为 max⁡{p⊤x∣Ax≤b,x≥0}\max \{ \mathbf{p}^\top \mathbf{x} \mid \mathbf{A}\mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0} \}，其中 p\mathbf{p} 为产品价格向量，x\mathbf{x} 为产量，b\mathbf{b} 为资源禀赋。对偶变量 y\mathbf{y} 的每一个分量 yiy_i 对应第 ii 种资源的影子价格（Shadow Price）——即该资源对总利润的边际贡献。

弱对偶 p⊤x≤b⊤y\mathbf{p}^\top \mathbf{x} \leq \mathbf{b}^\top \mathbf{y} 的含义是：按影子价格计算的资源总价值 b⊤y\mathbf{b}^\top \mathbf{y} 不会低于按市场价格计算的产品总收益 p⊤x\mathbf{p}^\top \mathbf{x}。这反映了经济学中的基本直觉——任何可行生产计划的利润不可能超出其所用资源的"内在价值"。对偶间隙 b⊤y−p⊤x≥0\mathbf{b}^\top \mathbf{y} - \mathbf{p}^\top \mathbf{x} \geq 0 衡量的正是资源配置效率的潜在改善空间：间隙为零时，投入物的估价恰好等于产出物的价值，资源配置达到帕累托效率。

在成本最小化框架中（原问题极小化），弱对偶表明实际成本不会低于影子成本，影子价格提供了成本的下界估计。这一性质在成本效益分析与规制经济学中被广泛用于评估公共项目的经济可行性。

凸优化中的推广

弱对偶定理的成立范围远不止线性规划，它可自然地推广至任意凸优化问题的拉格朗日对偶框架。考虑一般约束优化问题：

min⁡f0(x)s.t.fi(x)≤0,i=1,…,m,hj(x)=0,j=1,…,p\begin{aligned} \min \quad & f_0(\mathbf{x}) \\ \text{s.t.} \quad & f_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m, \\ & h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p \end{aligned}

其中 f0,f1,…,fmf_0, f_1, \ldots, f_m 为可微函数（不强求凸性即可建立弱对偶）。构造拉格朗日函数：

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑j=1pνjhj(x)\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f_0(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i f_i(\mathbf{x}) + \sum_{j=1}^{p} \nu_j h_j(\mathbf{x})

其中 λ≥0\boldsymbol{\lambda} \geq \mathbf{0} 为不等式约束的乘子。拉格朗日对偶函数定义为：

g(λ,ν)=inf⁡x∈DL(x,λ,ν)g(\boldsymbol{\lambda}, \boldsymbol{\nu}) = \inf_{\mathbf{x} \in \mathcal{D}} \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu})

对偶问题为 max⁡λ≥0,νg(λ,ν)\max_{\boldsymbol{\lambda} \geq \mathbf{0}, \boldsymbol{\nu}} g(\boldsymbol{\lambda}, \boldsymbol{\nu})。

弱对偶定理（一般形式）：对于任意原可行解 x\mathbf{x} 和任意对偶可行乘子 (λ,ν)(\boldsymbol{\lambda}, \boldsymbol{\nu})（即 λ≥0\boldsymbol{\lambda} \geq \mathbf{0}），有

g(λ,ν)≤f0(x)g(\boldsymbol{\lambda}, \boldsymbol{\nu}) \leq f_0(\mathbf{x})

证明与线性情形同源：对于原可行 x\mathbf{x}，fi(x)≤0f_i(\mathbf{x}) \leq 0，hj(x)=0h_j(\mathbf{x}) = 0，又 λ≥0\boldsymbol{\lambda} \geq \mathbf{0}，故

L(x,λ,ν)=f0(x)+∑iλifi(x)⏟≤0+∑jνjhj(x)⏟=0≤f0(x)\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f_0(\mathbf{x}) + \underbrace{\sum_{i} \lambda_i f_i(\mathbf{x})}_{\leq 0} + \underbrace{\sum_{j} \nu_j h_j(\mathbf{x})}_{= 0} \leq f_0(\mathbf{x})

取关于 x\mathbf{x} 的下确界即得 g(λ,ν)≤f0(x)g(\boldsymbol{\lambda}, \boldsymbol{\nu}) \leq f_0(\mathbf{x})。

这一推广使弱对偶定理适用于二次规划、半定规划、锥规划（包括二阶锥规划）乃至所有满足凸性假设的非线性规划。只要原问题为凸，且满足适当的约束规范（如斯莱特条件），弱对偶即可升级为强对偶，对偶间隙归零。

方法论意义

弱对偶定理在现代优化方法论中的核心地位源于其无条件性：该不等式对任意可行解对均成立，不依赖任何凸性或光滑性假设。这一简单而强健的性质带来了三重方法论价值。其一，它为分支定界算法提供了天然的下界（对极小化原问题）：每个对偶可行解给出一个目标值的下界估计，随着对偶可行解不断改进，下界不断提升并逼近期望的最优值。其二，在列生成与丹齐格-沃尔夫分解（Dantzig-Wolfe Decomposition）中，弱对偶提供了定价子问题的终止判据。其三，对偶间隙的大小在数值实验中作为收敛性度量与停止准则，广泛用于大规模运筹学计算的实用实施中。

弱对偶定理的哲学意涵同样值得关注。它表明任何一个"松弛"或"定价"视角下得到的估值，都构成原始问题目标值的客观界限——这意味着即便无法求解原问题，也能通过构造并优化对偶问题获得有用且可靠的信息。正是这一逻辑，使对偶理论超越了纯粹数学美的范畴，成为经济学实证研究与工程优化中不可或缺的分析工具。