基础 · 04

凸优化基础

拉格朗日乘子、KKT 条件、对偶问题——约束优化的三板斧。一篇文章把 SVM、正则化、EM 的数学地基铺好。

18 min read

为什么 ML 是优化问题

几乎所有机器学习算法最终都归结为同一件事：

定义一个"好坏"的数，然后调参让它尽量好。

Logistic 回归最小化交叉熵，神经网络最小化某种 loss + 正则项，SVM 最小化 ∥w∥2\|\mathbf{w}\|^2。区别只在于目标函数的形状和约束条件。

微积分那篇我们已经建立了无约束优化的直觉：算梯度，沿反方向走。但很多 ML 问题带约束——比如 SVM 要求"所有点都在间隔外面"，概率分布要求"所有分量非负且加和为 1"。

带约束的优化不能简单地"梯度等于零"，需要更精巧的工具。这篇我们铺好这套工具：拉格朗日乘子处理等式约束，KKT 条件处理不等式约束，对偶问题把困难的原始问题变成有时更容易的等价形式。

凸函数与凸集

先定义"凸"——它决定了优化问题是"好"的还是"难"的。

凸集（convex set）：集合 CC 中任意两点的连线段完全在 CC 内。圆盘是凸集，月牙形不是。

凸函数（convex function）：函数图像上方的区域是凸集。等价定义：

f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y),∀λ∈[0,1]f(\lambda \mathbf{x} + (1-\lambda)\mathbf{y}) \leq \lambda f(\mathbf{x}) + (1-\lambda)f(\mathbf{y}), \quad \forall \lambda \in [0, 1]

几何上：曲线总在弦的下方。切换下面的两个标签看区别：

凸集 ✓非凸集 ✗连线段始终在内部穿出!连线段穿出了集合

凸集：任意两点的连线段完全在集合内。月牙形有连线穿出去的点对——不是凸集。

凸性的核心判据：两点连线不跑出去（集合）/ 不穿下去（函数）。

用二阶条件判断更方便——如果 ff 二阶可微，ff 是凸的当且仅当 Hessian 矩阵 ∇2f\nabla^2 f 半正定。

凸函数有一个让优化变得简单的核心性质：

任何局部最小值都是全局最小值。

非凸函数（如神经网络的 loss landscape）有很多局部极小——梯度下降可能卡住。凸函数没有这个问题：只要找到一个梯度为零的点，就是全局最优。

凸优化问题 = 最小化凸函数 + 凸集上的约束。SVM 的原始问题就是凸的：12∥w∥2\frac{1}{2}\|\mathbf{w}\|^2 是凸二次函数，线性不等式约束定义的可行域是凸集。这保证了 SVM 有唯一的全局最优解。

常见的凸函数：

  • 线性函数 a⋅x+b\mathbf{a} \cdot \mathbf{x} + b（既凸又凹）
  • 二次函数 x⊤Ax\mathbf{x}^\top A \mathbf{x}（当 AA 半正定时）
  • 范数 ∥x∥p\|\mathbf{x}\|_p（所有 p≥1p \geq 1）
  • −log⁡x-\log x（在 x>0x > 0 上）
  • 指数 exe^x
  • 交叉熵损失（对模型参数是凸的，在 logistic 回归中）

等式约束：拉格朗日乘子

最简单的约束优化：

min⁡xf(x)s.t.h(x)=0\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{s.t.} \quad h(\mathbf{x}) = 0

为什么不能简单地"令梯度为零"？因为最优点不在无约束最优处——它被约束面拉住了。

几何直觉：在约束面 h(x)=0h(\mathbf{x}) = 0 上移动时，ff 能继续下降的条件是 ∇f\nabla f 有一个沿约束面切方向的分量。当 ∇f\nabla f 完全垂直于约束面时——也就是 ∇f\nabla f 平行于 ∇h\nabla h——在约束面上已经无处可走了。这就是约束最优点。

数学表述：在最优点，∇f=λ∇h\nabla f = \lambda \nabla h，即目标函数的梯度是约束梯度的倍数。λ\lambda 叫拉格朗日乘子。

拉格朗日函数把约束和目标合并：

L(x,λ)=f(x)+λ h(x)\mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) + \lambda \, h(\mathbf{x})

令 ∇xL=0\nabla_{\mathbf{x}} \mathcal{L} = 0 和 ∂L∂λ=0\frac{\partial \mathcal{L}}{\partial \lambda} = 0 同时成立——后者自动恢复了约束 h=0h = 0。这把约束问题变成了无约束的联立方程组。

下面的交互演示展示了这个几何：目标函数的等高线（紫色）和约束直线（黄色）。约束最优点在等高线与约束相切处——正是 −∇f-\nabla f 和 ∇g\nabla g 平行的点：

f(x,y) = (x−2.5)² + (y−2.5)²min = 0.00
(2.5, 2.5)

无约束时，最小值在等高线的中心 (2.5, 2.5)，f = 0。

约束优化的几何：最优点在约束边界上，且目标函数的梯度与约束的梯度平行（= 没有沿约束可以继续下降的方向）。

多个等式约束的推广自然：每个约束配一个乘子：

L(x,λ)=f(x)+∑jλjhj(x)\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_j \lambda_j h_j(\mathbf{x})

不等式约束：KKT 条件

ML 中更常见的是不等式约束：

min⁡xf(x)s.t.gi(x)≤0,i=1,…,m\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{s.t.} \quad g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m

不等式约束比等式复杂一点：最优点可能在约束边界上（约束"起作用"），也可能在可行域内部（约束"不起作用"）。

Karush-Kuhn-Tucker (KKT) 条件是不等式约束优化的一阶必要条件。在最优点 x∗\mathbf{x}^*，配合乘子 μi≥0\mu_i \geq 0，必须同时满足：

∇f(x∗)+∑iμi∇gi(x∗)=0（驻点条件）\nabla f(\mathbf{x}^*) + \sum_i \mu_i \nabla g_i(\mathbf{x}^*) = 0 \qquad \text{（驻点条件）} gi(x∗)≤0（原始可行性）g_i(\mathbf{x}^*) \leq 0 \qquad \text{（原始可行性）} μi≥0（对偶可行性）\mu_i \geq 0 \qquad \text{（对偶可行性）} μi gi(x∗)=0（互补松弛）\mu_i \, g_i(\mathbf{x}^*) = 0 \qquad \text{（互补松弛）}

互补松弛是最重要的一条。它说的是：

  • 如果约束 gig_i 不起作用（gi<0g_i < 0，点在约束内部），则 μi=0\mu_i = 0 —— 这个约束对最优解没有影响。
  • 如果 μi>0\mu_i > 0（约束有"力"），则必须 gi=0g_i = 0 —— 点恰好在约束边界上。

翻译成 ML 语言：

SVM 对应KKT 含义
αi=0\alpha_i = 0点在间隔外面，约束不起作用，不是支持向量
αi>0\alpha_i > 0约束起作用，点恰好在间隔边界上，是支持向量

互补松弛给出了 SVM 解的稀疏性——大部分约束不起作用（αi=0\alpha_i = 0），只有少数支持向量有非零乘子。

凸问题中，KKT 条件不仅必要而且充分——满足 KKT 的点一定是全局最优。

对偶问题与强对偶

拉格朗日对偶把原始问题（可能困难）变换成另一个（有时更简单的）优化问题。

对于一般问题：

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

定义拉格朗日函数：

L(x,μ)=f(x)+∑iμigi(x),μi≥0\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}) = f(\mathbf{x}) + \sum_i \mu_i g_i(\mathbf{x}), \quad \mu_i \geq 0

对偶函数是 L\mathcal{L} 对 x\mathbf{x} 取下确界：

d(μ)=inf⁡xL(x,μ)d(\boldsymbol{\mu}) = \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\mu})

对偶问题是最大化对偶函数：

max⁡μ≥0d(μ)\max_{\boldsymbol{\mu} \geq 0} d(\boldsymbol{\mu})

弱对偶定理（always holds）：对偶最优值 ≤\leq 原始最优值。差距叫对偶间隙（duality gap）。

强对偶定理：如果原始问题是凸的且满足 Slater 条件（存在一个严格可行的点，即所有 gi<0g_i < 0），则对偶间隙为零——原始和对偶有完全相同的最优值。

强对偶为什么重要？

  1. 解对偶可能更容易——SVM 的原始问题有 d+1d+1 个变量（w\mathbf{w} 和 bb），对偶有 nn 个变量（αi\alpha_i）。当 d≫nd \gg n 时对偶更高效。
  2. 对偶揭示结构——SVM 对偶只含内积 xi⋅xj\mathbf{x}_i \cdot \mathbf{x}_j，这是核技巧的入口。
  3. KKT 条件连接原始和对偶——在强对偶成立时，满足 KKT 的点同时是原始和对偶的最优解。

实际推导对偶的步骤（以 SVM 为例）：

  1. 写出拉格朗日函数 L(w,b,α)\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha})。
  2. 对 w\mathbf{w} 和 bb 求导令为零，得到 w∗(α)\mathbf{w}^*(\boldsymbol{\alpha}) 和约束 ∑αiyi=0\sum \alpha_i y_i = 0。
  3. 代回 L\mathcal{L}，消掉 w\mathbf{w} 和 bb，得到只含 α\boldsymbol{\alpha} 的对偶函数。
  4. 最大化对偶函数（加上 αi≥0\alpha_i \geq 0 和等式约束）。

这个推导我们将在下一篇 SVM 文章中具体展开。

这个想法在前沿里