二阶优化方法详解

前言

本文隶属于专栏《机器学习数学通关指南》，该专栏为笔者原创，引用请注明来源，不足和错误之处请在评论区帮忙指出，谢谢！

本专栏目录结构和参考文献请见《机器学习数学通关指南》

ima 知识库

知识库广场搜索：

正文

用二阶信息加速你的模型收敛

📚 引言

在机器学习的优化过程中，一阶方法（如梯度下降）虽然实现简单，但收敛速度常常不尽如人意。二阶优化方法通过利用目标函数的曲率信息（Hessian矩阵），能够显著提升收敛速度和优化效率。本文将深入介绍三种主流二阶优化算法，并结合实例分析其应用场景。

1. 牛顿法（Newton’s Method）🔍

核心思想

牛顿法基于目标函数的二阶泰勒展开，同时利用梯度方向和曲率信息进行参数更新：

$w^{t+1}=w^t-H^{-1}(w^t)\cdot \nabla f(w^t)$

其中：

• $H(w^t)$ 是在点 $w^t$ 处的Hessian矩阵
• $\nabla f(w^t)$ 是梯度向量

数学推导

牛顿法的基本原理来自于目标函数的二阶泰勒展开：

$f(w)\approx f(w^t)+\nabla f(w^t{)}^T(w-w^t)+\frac{1}{2}(w-w^t{)}^{T}H(w^t)(w-w^t)$

对此近似函数求导并令其为零，解得下一个迭代点：

$H(w^t)(w^{t+1}-w^t)=-\nabla f(w^t)$
$w^{t+1}=w^t-H^{-1}(w^t)\nabla f(w^t)$

特点 ✅❌

优点：

• 收敛速度快（二阶收敛率），特别是在接近最优点时
• 方向选择更精确，避免了梯度下降的"之字形"路径
• 对于二次函数，理论上一步可达最优解

缺点：

• 计算和存储 Hessian 矩阵成本高 ($O(d^3)$ 复杂度计算逆矩阵)
• 需要 Hessian 正定，否则可能不收敛或朝错误方向前进
• 在非凸问题上可能陷入鞍点或局部最小值

应用场景 🎯

• 小规模或中等维度的优化问题
• 凸优化问题，尤其是目标函数高度光滑
• 精确解的数值优化，如统计中的最大似然估计
• 需要快速收敛的场景，如微调模型的最后阶段

代码示例

import numpy as np
from scipy.optimize import minimize

# 定义目标函数及其梯度和Hessian
def objective(x):
    return x[0]**2 + x[1]**2

def gradient(x):
    return np.array([2*x[0], 2*x[1]])

def hessian(x):
    return np.array([[2, 0], [0, 2]])

# 初始点
x0 = np.array([1.0, 1.0])

# 使用Newton-CG方法（牛顿法的变种）
result = minimize(objective, x0, method='Newton-CG',
                  jac=gradient, hess=hessian,
                  options={'xtol': 1e-8, 'disp': True})

print(f"最优解: {result.x}")
print(f"迭代次数: {result.nit}")

2. 拟牛顿法（Quasi-Newton Methods）🧠

核心思想

拟牛顿法通过构建 Hessian 矩阵或其逆矩阵的近似，避免了直接计算这些昂贵的矩阵：

$w^{t+1}=w^t-B_t\cdot \nabla f(w^t)$

其中 $B_t$ 是 Hessian 逆矩阵的近似。

BFGS 算法

Broyden–Fletcher–Goldfarb–Shanno (BFGS) 算法是最流行的拟牛顿方法之一：

1. 计算梯度差 $y_t=\nabla f(w^{t+1})-\nabla f(w^t)$
2. 计算位移向量 $s_t=w^{t+1}-w^t$
3. 更新近似的 Hessian 逆矩阵：

$B_{t+1}=(I-{\rho }_t{s}_t{y}_t^T)B_t(I-{\rho }_t{y}_t{s}_t^T)+{\rho }_t{s}_t{s}_t^T$

其中 ${\rho }_t=\frac{1}{y_t^T{s}_t}$

这种更新确保了 $B_{t+1}$ 保持对称正定，同时满足"割线条件"。

L-BFGS 算法

Limited-memory BFGS (L-BFGS) 是针对高维问题的内存优化版本：

• 不存储完整的 $B_t$ 矩阵，只保存最近 m 次迭代的向量对 $(s_i,y_i)$
• 通过这些向量对隐式地表示 $B_t$
• 内存需求从 $O(d^2)$ 降至 $O(md)$，其中 m≪d

特点 ✅❌

优点：

• 避免了直接计算 Hessian 矩阵，大幅降低计算成本
• 保持了超线性收敛速度（介于一阶和二阶之间）
• L-BFGS 适用于高维问题，内存需求低
• 比牛顿法更稳定，不易受非正定 Hessian 影响

缺点：

• 收敛速度略逊于完全牛顿法
• 需要存储历史信息，BFGS 在极高维问题上仍有内存瓶颈
• L-BFGS 中历史长度 m 是需要调优的超参数

应用场景 🎯

• 中大规模机器学习问题的训练
• 许多常见 ML 模型的求解器：逻辑回归、线性 SVM、CRF 等
• scikit-learn 中的 lbfgs 和 liblinear 求解器
• 深度学习框架中的高级优化器选项

代码示例

import numpy as np
from scipy.optimize import minimize

# 定义目标函数及其梯度
def rosenbrock(x):
    return sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0)

def rosenbrock_grad(x):
    xm = x[1:-1]
    xm_m1 = x[:-2]
    xm_p1 = x[2:]
    der = np.zeros_like(x)
    der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm)
    der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0])
    der[-1] = 200*(x[-1]-x[-2]**2)
    return der

# 初始点 - 5维 Rosenbrock 函数
x0 = np.array([0.5, 0.5, 0.5, 0.5, 0.5])

# 使用L-BFGS-B方法
result_lbfgs = minimize(rosenbrock, x0, method='L-BFGS-B', 
                        jac=rosenbrock_grad, 
                        options={'gtol': 1e-6, 'disp': True})

print(f"L-BFGS 最优解: {result_lbfgs.x}")
print(f"L-BFGS 迭代次数: {result_lbfgs.nit}")

3. 共轭梯度法（Conjugate Gradient Method）⚙️

核心思想

共轭梯度法通过构建一组"共轭方向"来实现高效优化，避免在搜索过程中重复已经优化过的方向：

1. 初始方向为负梯度：$d^0=-\nabla f(w^0)$
2. 后续方向通过组合当前梯度和前一个方向得到：

$d^{t+1}=-\nabla f(w^{t+1})+{\beta }_t{d}^t$

其中 ${\beta }_t$ 通过不同公式计算（如 Fletcher-Reeves 或 Polak-Ribière 公式）：

Fletcher-Reeves：${\beta }_t=\frac{||\nabla f(w^{t+1})|{|}^2}{||\nabla f(w^t)|{|}^2}$

Polak-Ribière：${\beta }_t=\frac{\nabla f(w^{t+1}{)}^T[\nabla f(w^{t+1})-\nabla f(w^t)]}{||\nabla f(w^t)|{|}^2}$

数学原理

在二次函数情况下，共轭梯度确保了搜索方向 $d^i$ 和 $d^j$ 关于 Hessian 矩阵 $H$ 是共轭的：

$d^{i}H{d}^j=0,\forall i\ne j$

这保证了算法在 n 维空间中最多需要 n 步即可达到最优解。

特点 ✅❌

优点：

• 内存需求极低，只需存储几个向量（$O(d)$ 空间复杂度）
• 理论上，对于 n 维二次函数，最多 n 步收敛
• 不需要矩阵存储或操作，适合大规模稀疏问题
• 与预处理技术结合效果显著

缺点：

• 对非二次函数需要重启策略，防止共轭性失效
• 收敛速度通常慢于拟牛顿法
• 线性收敛，对病态问题性能可能不佳
• 步长选择对收敛影响较大

应用场景 🎯

• 大规模线性系统求解（如 $Ax=b$ 问题）
• 深度学习中的参数优化，特别是内存受限场景
• 稀疏问题，如大规模图像处理和信号处理
• 结合预处理技术用于加速训练神经网络

代码示例

import numpy as np
from scipy.optimize import minimize

# 定义二次函数及其梯度
def quadratic(x):
    A = np.array([[2, 1], [1, 4]])
    b = np.array([1, 2])
    return 0.5 * x.dot(A).dot(x) - b.dot(x)

def quadratic_grad(x):
    A = np.array([[2, 1], [1, 4]])
    b = np.array([1, 2])
    return A.dot(x) - b

# 初始点
x0 = np.array([0.0, 0.0])

# 使用共轭梯度法
result_cg = minimize(quadratic, x0, method='CG',
                     jac=quadratic_grad,
                     options={'gtol': 1e-6, 'disp': True})

print(f"CG最优解: {result_cg.x}")
print(f"CG迭代次数: {result_cg.nit}")

方法对比 📊

实践中的选择指南 🧭

1. 问题规模是决定因素：

   • 低维问题（<100维）：牛顿法或BFGS
   • 中等维度（100-10000维）：L-BFGS
   • 高维问题（>10000维）：共轭梯度法或随机近似方法

2. 结合深度学习框架：

   • TensorFlow/PyTorch中可通过scipy.optimize接口使用这些优化器
   • 深度学习框架通常提供这些优化器的随机变种

3. 预处理技术：

   • 对于病态问题，结合对角Hessian近似或AdaGrad类预处理器
   • 共轭梯度法特别推荐使用预处理增强性能

实战案例：优化器性能对比 🔬

import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize
import time

# 创建Rosenbrock函数（著名的优化测试函数）
def rosen(x):
    return sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0)

def rosen_grad(x):
    xm = x[1:-1]
    xm_m1 = x[:-2]
    xm_p1 = x[2:]
    der = np.zeros_like(x)
    der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm)
    der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0])
    der[-1] = 200*(x[-1]-x[-2]**2)
    return der

# 测试不同优化器
methods = ['BFGS', 'L-BFGS-B', 'CG', 'Newton-CG']
results = {}

# 10维Rosenbrock函数
dim = 10
x0 = np.ones(dim) * 1.2

for method in methods:
    start_time = time.time()
    if method == 'Newton-CG':
        # 为Newton-CG定义Hessian
        def rosen_hess(x, p):
            # 为示例简化，返回对角Hessian近似
            return 200 * p
        
        result = minimize(rosen, x0, method=method, jac=rosen_grad, 
                          hessp=rosen_hess)
    else:
        result = minimize(rosen, x0, method=method, jac=rosen_grad)
    
    runtime = time.time() - start_time
    results[method] = {
        'success': result.success,
        'iterations': result.nit,
        'function_calls': result.nfev,
        'runtime': runtime
    }

# 打印结果
for method, res in results.items():
    print(f"\n{method} 优化器结果:")
    print(f"成功: {res['success']}")
    print(f"迭代次数: {res['iterations']}")
    print(f"函数评估次数: {res['function_calls']}")
    print(f"运行时间: {res['runtime']:.4f}秒")

总结 📝

二阶优化方法是机器学习中处理复杂优化问题的强大工具：

• 🚀 牛顿法直接利用Hessian矩阵提供最快收敛，但计算成本高。
• 🔋 拟牛顿法（尤其是L-BFGS）通过近似Hessian提供了最佳平衡，是机器学习中的主力优化方法。
• ⚡ 共轭梯度法以极低内存需求处理超大规模问题，在深度学习领域仍有重要应用。

实际应用中，L-BFGS通常是训练传统机器学习模型的首选算法，而在深度学习中，人们通常使用这些方法的随机变体以处理海量数据。

优化器选择应综合考虑问题规模、内存限制、精度要求和收敛速度需求，没有"放之四海而皆准"的最佳选择，而是根据具体场景灵活选用。

希望这篇文章对你理解机器学习中的二阶优化方法有所帮助！如有疑问，欢迎在评论区讨论交流。🤗