机器学习数学基础 120 章

对偶问题与强/弱对偶

层级：B｜按需

1. 为什么要看另一个问题

Lagrange 对偶把约束原问题转成关于乘子的优化。它可以给原问题下界、提供最优性证书、揭示活跃样本与稀疏结构，并让 SVM 只通过内积出现，从而使用核技巧。

2. 原问题

p∗=min⁡xf(x)s.t.gi(x)≤0,hj(x)=0.\begin{aligned} p^*=\min_x\quad&f(x)\\ \text{s.t.}\quad&g_i(x)\le0,\\ &h_j(x)=0. \end{aligned}

Lagrangian：

L(x,α,λ)=f(x)+∑iαigi(x)+∑jλjhj(x),\mathcal L(x,\alpha,\lambda) =f(x)+\sum_i\alpha_ig_i(x) +\sum_j\lambda_jh_j(x),

α≥0\alpha\ge0。

3. 对偶函数

q(α,λ)=inf⁡xL(x,α,λ).q(\alpha,\lambda) =\inf_x\mathcal L(x,\alpha,\lambda).

对任意原始可行 xx：

L(x,α,λ)≤f(x)\mathcal L(x,\alpha,\lambda)\le f(x)

因为 αigi(x)≤0\alpha_i g_i(x)\le0、等式项为零。再对所有 xx 取下确界：

q(α,lambda)≤f(x).q(\alpha,lambda)\le f(x).

所以每个对偶可行点都给原最优值一个下界。

4. 对偶问题

为了得到尽可能紧的下界：

d∗=max⁡α≥0,λq(α,lambda).d^*=\max_{\alpha\ge0,\lambda}q(\alpha,lambda).

无论原问题是否凸，对偶函数都是凹函数，因为它是关于乘子的仿射函数族的逐点下确界。因此对偶问题是凹最大化（等价凸优化）。

5. 弱对偶

总有

d∗≤p∗.d^*\le p^*.

这叫弱对偶。差值

p∗−d∗≥0p^*-d^*\ge0

称最优对偶间隙。任意原始可行目标值给上界，任意对偶可行值给下界，两者接近时形成最优性证书。

6. 强对偶

若

d∗=p∗,d^*=p^*,

称强对偶。凸问题在 Slater 等条件下通常成立；线性规划在适当可行情形也有强对偶。非凸问题可能存在正间隙。

强对偶加最优解存在时，KKT 条件把原始与对偶最优连接起来。

7. 简单例子

min⁡xx2s.t. 1−x≤0.\min_x x^2\quad\text{s.t. }1-x\le0.

Lagrangian：

L=x2+α(1−x),α≥0.\mathcal L=x^2+\alpha(1-x),\quad\alpha\ge0.

对 xx 取下确界。驻点 2x−α=02x-\alpha=0，x=α/2x=\alpha/2：

q(α)=α−α24.q(\alpha)=\alpha-\frac{\alpha^2}{4}.

最大化 qq 得 α∗=2\alpha^*=2，d∗=1d^*=1。原问题 x∗=1,p∗=1x^*=1,p^*=1，强对偶成立。

8. SVM 对偶的结构

硬间隔原问题：

min⁡w,b12∥w∥2s.t. yi(wTxi+b)≥1.\min_{w,b}\frac12\|w\|^2 \quad\text{s.t. }y_i(w^Tx_i+b)\ge1.

消去 w,bw,b 后对偶：

max⁡α≥0∑iαi−12∑i,jalphaiαjyiyjxiTxj\max_{\alpha\ge0} \sum_i\alpha_i -\frac12\sum_{i,j}alpha_i\alpha_jy_iy_jx_i^Tx_j s.t. ∑iαiyi=0.\text{s.t. }\sum_i\alpha_iy_i=0.

原始特征只通过内积 xiTxjx_i^Tx_j 出现，可替换成核函数 k(xi,xj)k(x_i,x_j)。并且

w=∑iαiyixi,w=\sum_i\alpha_iy_ix_i,

非零乘子样本是支持向量。

9. 原始还是对偶更容易

取决于维度与结构：

  • 原变量 dd 很小、样本 nn 很大：原问题可能更合适；
  • 核 SVM 无显式有限 dd：必须依赖对偶/核表示；
  • 约束多但结构稀疏：对偶可能分解；
  • 分布式优化：对偶变量可与数据块对应。

“对偶一定更快”是错误的。

10. 对偶乘子的敏感性

最优乘子表示约束轻微放宽的边际价值。大乘子说明约束紧且昂贵；零乘子说明局部放宽它不改善目标。这种解释在资源分配、软间隔代价和公平约束中很有用。

11. 共轭函数预览

凸函数的 Fenchel 共轭：

f∗(y)=sup⁡x(yTx−f(x)).f^*(y)=\sup_x(y^Tx-f(x)).

许多无显式约束问题也可通过共轭构造 Fenchel 对偶。L1、log-sum-exp、熵和最大间隔模型有漂亮的共轭关系。第一次阅读西瓜书不必掌握全部细节，但要知道对偶不只来自手工 Lagrangian 消元。

易错点

  1. 对偶值对最小化原问题给下界，不是上界。
  2. 弱对偶总成立，强对偶需条件。
  3. 对偶函数定义是对原变量取下确界。
  4. 原问题非凸时对偶仍凸，但可能有间隙。
  5. 对偶形式漂亮不代表数值上更便宜。

常见问答

Q1：为什么核技巧主要在 SVM 对偶中出现？

对偶目标只依赖样本内积，把内积替换成合法核即可隐式进入高维特征空间。

Q2：原—对偶间隙为零是否证明最优？

若有一个原始可行点和对偶可行点目标相等，弱对偶夹逼说明二者最优。数值中看容差。

Q3：对偶变量是否就是概率？

不是。它们是约束乘子，可能有非负、和约束等结构，但语义由问题决定。

练习

  1. 写出对偶函数与对偶问题的一般定义。
  2. 证明弱对偶的关键不等式。
  3. 原始可行值 10、对偶可行值 9.8，能说明什么？
  4. 为什么 SVM 对偶可用核？
  5. 强对偶是否对所有非凸问题成立？

答案与提示

  1. q=inf⁡xLq=\inf_x\mathcal L，最大化 qq 且 α≥0\alpha\ge0。
  2. 对可行 xx，L≤f(x)\mathcal L\le f(x)，所以 q≤f(x)q\le f(x)。
  3. 最优值在 [9.8,10][9.8,10]，间隙至多 0.2。
  4. 数据只通过两两内积出现。
  5. 否，可能有正对偶间隙。