凸优化:一个谷与一百万个谷的差别

凸优化:一个谷与一百万个谷的差别

本节摘要:凸问题只有一个谷,神经网络有百万个。第 8 节教了梯度下降、动量、Adam,它们在任何曲面上下山,但无保证——非凸曲面上可能陷坏局部最小、卡鞍点、永远震荡。然而许多 ML 问题是凸的:线性回归、逻辑回归、SVM、Lasso、岭回归——对它们存在更强的东西:带数学保证的优化。凸问题恰好一个谷,任何下山算法都到全局最优,无需重启、无需学习率调度、无需祈祷。本节给出凸集与凸函数的定义(两点的线段在集内/在图上方)、三种凸性判据(二阶导 ≥0、Hessian 半正定、定义不等式);讲清Hessian 矩阵如何编码曲率(特征值全正=凸、全负=凹、混合=鞍点);实现**牛顿法**(用逆 Hessian 替代学习率,近极小处二次收敛)并与梯度下降比步数;推导**Lagrange 乘子**与 **KKT 条件**(把约束优化变无约束,互补松弛性解释 SVM 支持向量);把 L1/L2 正则揭示为约束优化(‖w‖₁≤t 是菱形造稀疏、‖w‖₂²≤t 是圆只收缩);用对偶性说明 SVM 为何在对偶形式下能用核技巧;最后回答:为何非凸的神经网络 SGD 仍可靠地找到好解(高维下临界点几乎全是鞍点、过参数化平滑地形、随机噪声作隐式正则偏向平坦极小)。

对应原课程:Phase 01 · Lesson 18 · convex-optimization(原英文 phases/01-math-foundations/18-convex-optimization/docs/en.md)。前置:第 4、8 节(微积分、优化)。

学习目标

阅读完本节,你应当能够:

1. 用定义、二阶导、Hessian 准则检验函数是否凸。
2. 实现牛顿法,对比其二次收敛与梯度下降。
3. 用 Lagrange 乘子解约束优化,解释 KKT 条件。
4. 说明为何神经网络损失面非凸但 SGD 仍能找到好解。

一、问题与直觉

第 8 节教了梯度下降、动量、Adam。这些优化器在任何曲面上下山,但无保证——非凸曲面上可能陷坏局部最小、卡鞍点、永远震荡。你之所以仍用它们,是因为神经网络非凸且无替代方案。但许多 ML 问题是凸的,对它们存在更强的东西:带数学保证的优化。理解凸性做三件事:① 告诉你问题何时易(凸)何时难(非凸);② 给你更快工具(如牛顿法);③ 解释贯穿 ML 的概念——正则化即约束、SVM 的对偶性、为何深度学习违反凸性的一切好性质却仍有效。

1.1 凸集

集 S 是凸的,若 S 中任意两点的线段也完全在 S 内。形式化:对任意 x,y ∈ S 与任意 t ∈ [0,1],点 tx + (1-t)y 也在 S 内。凸集例:直线、平面、整个 ℝⁿ、球(圆、球面、超球面)、半空间 {x : aᵀx ≤ b}、任意数量凸集的交。非凸例:甜甜圈(环)、两个不交圆的并、任何有「凹」或「洞」的集。

1.2 凸函数

函数 f 是凸的,若其定义域是凸集且对定义域内任意 x,y 与任意 t ∈ [0,1]:f(tx + (1-t)y) ≤ t·f(x) + (1-t)·f(y)。几何上:图上任意两点间的线段在图之上或触图。凸函数性质:线段测试——线上任意两点连线在曲线之上或触;形状——单个碗/谷向上弯;局部最小——每个局部最小都是全局最小。常见凸函数:x²、|x|、eˣ、max(0,x)(ReLU,虽逐段线性)、-log(x)(x>0)、任何线性函数 aᵀx + b(既凸又凹)。

1.3 凸性判据

三个实用判据,从易到严:

• 判据 1:二阶导(1D):若 f''(x) ≥ 0 对所有 x,则 f 凸。x²→f''=2≥0 凸;x³→f''=6x 在 x<0 为负,不凸;eˣ→f''=eˣ>0 凸。
• 判据 2:Hessian(多元):若 Hessian 矩阵 H(x) 对所有 x 半正定,则 f 凸。Hessian 是二阶偏导组成的矩阵。
• 判据 3:定义:直接检查不等式 f(tx+(1-t)y) ≤ t·f(x)+(1-t)·f(y),适合导数难算的函数。

1.4 凸性为何要紧

凸优化的中心定理:对凸函数,每个局部最小都是全局最小。

这意味着梯度下降不会被陷——任何下山路径都到同一答案,算法保证收敛到最优解。

推论:无需随机重启;无需复杂学习率调度;可证收敛率;解唯一(平坦区除外)。

1.5 ML 中的凸 vs 非凸

带凸损失的线性模型是凸的;一旦加隐藏层与非线性激活,凸性就破了。

1.6 Hessian 矩阵

函数 f: ℝⁿ → ℝ 的 Hessian H 是 n×n 的二阶偏导矩阵:H[i][j] = ∂²f/(∂x_i ∂x_j)。以 f(x,y) = x² + 3xy + y² 为例:

∂f/∂x = 2x+3y  ∂²f/∂x² = 2  ∂²f/∂x∂y = 3
∂f/∂y = 3x+2y  ∂²f/∂y² = 2  ∂²f/∂y∂x = 3
H = |2 3|
    |3 2|
​

Hessian 告诉你曲率:特征值全正——各方向上弯(该点凸);全负——各方向下弯(凹,局部最大);混合符号——鞍点(某些方向上、某些方向下);零特征值——该方向平坦(退化)。凸性要求 Hessian 处处半正定,不只一点。

1.7 牛顿法

梯度下降用一阶信息(梯度),牛顿法用二阶信息(Hessian)。它在当前点拟合二次近似,直接跳到该二次的最小:

更新:x_new = x - H⁻¹·梯度       ← 对比梯度下降 x_new = x - lr·梯度
​

牛顿法用逆 Hessian 替代标量学习率,自动据局部曲率调步长与方向。

优点:近极小处二次收敛(误差每步平方);无学习率可调;尺度无关。缺点:算 Hessian 需 O(n²) 内存、O(n³) 求逆;百万权重网络意味着 10¹² 项与 10¹⁸ 运算——深度学习不实用。

1.8 约束优化

无约束:对所有 x 最小化 f(x)。约束:在约束下最小化 f(x)。真实问题有约束:你想最小化成本但预算有限,想最小化误差但模型复杂度有界。

1.9 Lagrange 乘子

Lagrange 乘子法把约束问题变成无约束问题。问题:在 g(x) = 0 约束下最小化 f(x)。解:引入新变量(Lagrange 乘子 λ)解无约束问题 L(x,λ) = f(x) + λ·g(x)。在解处 L 的梯度为零:∂L/∂x = ∂f/∂x + λ·∂g/∂x = 0,∂L/∂λ = g(x) = 0。

几何直觉:在约束最小处,f 的梯度必须与约束 g 的梯度平行——若不平行,你能沿约束面移动进一步降 f。

例:在 x + y = 1 约束下最小化 f(x,y) = x² + y²。解 L = x² + y² + λ(x+y-1),得 2x+λ=0、2y+λ=0、x+y-1=0,故 x=y=0.5、λ=-1——直线 x+y=1 上离原点最近的点是 (0.5, 0.5)。

1.10 KKT 条件

Karush-Kuhn-Tucker 条件把 Lagrange 乘子推广到不等式约束。问题:在 g_i(x) ≤ 0(i=1..m)下最小化 f(x)。KKT 条件(最优性的必要条件):

1. 平稳性:    ∂f/∂x + Σ λ_i·∂g_i/∂x = 0
2. 原问题可行: g_i(x) ≤ 0  对所有 i
3. 对偶可行:   λ_i ≥ 0  对所有 i
4. 互补松弛性: λ_i·g_i(x) = 0  对所有 i
​

互补松弛性是关键洞见:要么约束起作用(g_i=0,解在边界),要么乘子为零(约束无关)——不影响解的约束 λ=0。KKT 是 SVM 的核心:支持向量是约束起作用(λ>0)的数据点,其余点 λ=0、不影响决策边界。

1.11 正则化即约束优化

L1、L2 正则不是任意花招,它们是伪装的约束优化问题。

L2 正则(岭):在 ‖w‖² ≤ t 下最小化 Loss(w),等价无约束形式 min Loss(w) + λ·‖w‖²。约束 ‖w‖² ≤ t 定义一个球(2D 圆),解是损失等高线首次触该球处。

L1 正则(Lasso):在 ‖w‖₁ ≤ t 下最小化 Loss(w),等价 min Loss(w) + λ·‖w‖₁。约束 ‖w‖₁ ≤ t 定义一个菱形(2D 旋方形)。

这解释了为何 L1 造稀疏模型(特征选择)而 L2 只收缩权重:菱形有对齐轴的角,损失等高线更易触角,使一个或多个权重恰为零。

1.12 对偶性

每个约束优化问题(原问题)都有伴生问题(对偶问题)。对凸问题,原问题与对偶问题最优值相同,这是强对偶。Lagrange 对偶函数:原问题 min f(x) s.t. g(x)≤0;Lagrange 函数 L(x,λ) = f(x) + λ·g(x);对偶函数 d(λ) = min_x L(x,λ);对偶问题 max d(λ) s.t. λ≥0。

对偶性为何要紧:① 对偶问题有时比原问题易解;② SVM 在对偶形式下解,问题依赖数据点间点积(启用核技巧);③ 对偶给原问题最优值的下界,用于检查解质量。SVM:原问题找 w,b 使间隔 2/‖w‖ 最大;对偶问题只涉及点积 x_iᵀx_j,把 x_iᵀx_j 换成 K(x_i,x_j) 即得核技巧。

1.13 为何非凸的深度学习仍有效

神经网络损失函数剧烈非凸,按经典标准优化它应失败,但 SGD 可靠地找到好解。几个因素解释:

• 大多数局部最小足够好:高维空间里,随机临界点(梯度为零处)绝大多数是鞍点而非局部最小;少数存在的局部最小损失值接近全局最小。参数空间百万维时陷坏局部最小极不可能。
• 鞍点才是真障碍:n 参数的函数,鞍点有正负曲率方向混合。高维随机临界点所有 n 个特征值全正(局部最小)的概率约 2⁻ⁿ——几乎全是鞍点。SGD 的噪声帮逃鞍点。
• 过参数化平滑地形:参数比训练样本多的网络有更平滑、更连通的损失面,更宽的网络坏局部最小更少(反直觉但经验一致)。
• 随机噪声作隐式正则:mini-batch SGD 加噪声防陷入尖锐极小——尖锐极小过拟合,平坦极小泛化好。噪声把优化偏向损失面的平坦区。

1.14 二阶方法的实战

纯牛顿法对大模型不实用,几种近似让二阶信息可用:

• L-BFGS(有限内存 BFGS):用最近 m 个梯度差近似逆 Hessian,O(mn) 内存而非 O(n²),适合至约 1 万参数的问题,用于经典 ML(逻辑回归、CRF),不用于深度学习。
• 自然梯度:用 Fisher 信息矩阵(对数似然的期望 Hessian)替代标准 Hessian,考虑概率分布几何;K-FAC 把 Fisher 矩阵近似为 Kronecker 积,使神经网络可用。
• 无 Hessian 优化:用共轭梯度解 Hx = g 而不形成 H,只需 Hessian-向量积(可经自动微分 O(n) 算)。
• 对角近似:Adam 的二阶矩是 Hessian 对角近似;AdaHessian 用 Hutchinson 估计器扩展为真实对角元。

二、从零实现

完整源码见 phases/01-math-foundations/18-convex-optimization/code/。

2.1 凸性检查器(经验)

def check_convexity(f, dim, bounds=(-5, 5), samples=1000):
    violations = 0
    for _ in range(samples):
        x = [random.uniform(*bounds) for _ in range(dim)]
        y = [random.uniform(*bounds) for _ in range(dim)]
        t = random.uniform(0, 1)
        mid = [t*xi + (1-t)*yi for xi, yi in zip(x, y)]
        if f(mid) > t*f(x) + (1-t)*f(y) + 1e-10:
            violations += 1
    return violations == 0, violations
​

2.2 2D 牛顿法

def newtons_method(f, grad_f, hessian_f, x0, steps=50, tol=1e-12):
    x = list(x0); history = [x[:]]
    for _ in range(steps):
        g = grad_f(x); H = hessian_f(x)
        det = H[0][0]*H[1][1] - H[0][1]*H[1][0]
        if abs(det) < 1e-15: break
        H_inv = [[H[1][1]/det, -H[0][1]/det], [-H[1][0]/det, H[0][0]/det]]   # 2D 逆
        dx = [H_inv[0][0]*g[0] + H_inv[0][1]*g[1], H_inv[1][0]*g[0] + H_inv[1][1]*g[1]]
        x = [x[0]-dx[0], x[1]-dx[1]]
        history.append(x[:])
        if sum(gi**2 for gi in g) < tol: break
    return history
​

2.3 Lagrange 乘子求解器

在 Lagrange 函数上做梯度下降:x 用梯度下降,λ 用梯度上升(因对偶问题最大化):

def lagrange_solve(f_grad, g_val, g_grad, x0, lr=0.01, lr_lambda=0.01, steps=5000):
    x = list(x0); lam = 0.0; history = []
    for _ in range(steps):
        fg = f_grad(x); gv = g_val(x); gg = g_grad(x)
        x = [xi - lr*(fgi + lam*ggi) for xi, fgi, ggi in zip(x, fg, gg)]
        lam = lam + lr_lambda * gv                    # λ 上升
        history.append((x[:], lam, gv))
    return history
​

2.4 一阶 vs 二阶对比

对二次函数 f(x) = 5x₁² + x₂²(Hessian 特征值 10 与 2,条件数 5,造细长谷),牛顿法 1 步收敛(对二次精确),梯度下降需数百步。

三、框架对比

凸性分析直接用于选 ML 模型与解器:

from scipy.optimize import minimize
# 凸问题:用 L-BFGS-B
result = minimize(fun=lambda w: sum((y - X@w)**2) + 0.1*sum(w**2),
                  x0=np.zeros(d), method='L-BFGS-B',
                  jac=lambda w: -2*X.T@(y - X@w) + 0.2*w)

from sklearn.svm import SVC                       # SVM 对偶形式启用核技巧
svm = SVC(kernel='rbf', C=1.0).fit(X_train, y_train)
​

凸问题(逻辑回归、SVM、Lasso)用专用解器(liblinear、CVXPY、scipy.optimize.minimize method='L-BFGS-B'),期望唯一全局解,二阶方法实用且快。非凸问题(神经网络)用一阶法(SGD、Adam),接受解依赖初始化与随机性,用过参数化、噪声、学习率调度作隐式正则,别浪费时间找全局最小——好局部最小就够。

四、可复用产物

• 凸性检查器、牛顿法、Lagrange 求解器的从零实现。
• 一份「何时问题凸、何时用二阶法」的决策指南。

源码见 phases/01-math-foundations/18-convex-optimization/code/。

五、练习

1. (Easy) 凸性画廊:用检查器测 x⁴、sin(x)、x²+y²、x·y、max(x,0),解释每个结果为何合理。
2. (Medium) 牛顿 vs 梯度下降赛跑:对 f(x,y) = 50x² + y² 从 (10,10) 出发,各需几步到 loss<1e-10?当 Hessian 条件数增大时梯度下降会怎样?
3. (Medium) Lagrange 乘子几何:在 x + 2y = 4 约束下最小化 (x-3)² + (y-3)²,验证解处 f 的梯度与 g 的梯度平行。
4. (Hard) 正则化约束:实现 L1 约束优化——在 |x|+|y| ≤ 1 下最小化 (x-3)² + (y-2)²,展示解有一个坐标为零(菱形约束的稀疏性)。
5. (Hard) Hessian 特征值分析:算 Rosenbrock 函数在 (1,1) 与 (-1,1) 的 Hessian 与特征值,特征值告诉你极小处与远离处的曲率什么?

本节要点回顾

1. 凸集:任意两点线段在集内;凸函数:任意两点连线在图之上——单碗向上弯。
2. 凸函数每个局部最小是全局最小,梯度下降不会被陷,无需重启/调度/祈祷。
3. 三种凸性判据:二阶导 ≥0(1D)、Hessian 半正定(多元)、定义不等式。
4. Hessian 编码曲率:特征值全正=凸、全负=凹、混合=鞍点;凸性要求处处半正定。
5. 线性模型 + 凸损失 = 凸问题:线性/逻辑回归、SVM、Lasso、岭回归都凸;加隐藏层非线性激活就破凸性。
6. 牛顿法 用逆 Hessian 替代学习率,近极小二次收敛,但 O(n²) 内存 + O(n³) 求逆,深度学习不实用。
7. Lagrange 乘子把约束变无约束;KKT 推广到不等式约束,互补松弛性(约束起作用或乘子为零)是 SVM 支持向量的根源。
8. L1 正则=菱形约束造稀疏(角处相切使权重为零),L2 正则=圆约束只收缩(光滑处相切,权重变小非零)。
9. 对偶性:凸问题原与对偶同最优值(强对偶),SVM 对偶形式只涉及点积,启用核技巧。
10. 非凸神经网络 SGD 仍有效:高维临界点几乎全鞍点、过参数化平滑地形、mini-batch 噪声偏向平坦极小(泛化好)。

下一节,我们打开 -1 的平方根——面向 AI 的复数:它不是「想象」的,而是旋转、频率与半个信号处理的关键,是 DFT、FFT、RoPE 的语言。