Math-04.优化-07.二阶与牛顿法

本页介绍二阶优化：利用 Hessian（或近似）加速收敛，及 XGBoost 中的二阶展开。

段末注释：牛顿法（Newton’s method）更新 $\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - H^{-1}\nabla L$，$H=\nabla^2 L$ 为 Hessian；收敛二次快但每步 $O(d^3)$ 或需近似。

系列入口：00.系列规划 | 前置：01 总论、Math-03/07 正定

1. 牛顿法（D2–D3）

$图 1　二次近似与牛顿步$

Taylor 展开：

$$
L(\boldsymbol{\theta} + \Delta) \approx L(\boldsymbol{\theta}) + \nabla L^\top \Delta + \frac{1}{2}\Delta^\top H \Delta
$$

令导数为零得牛顿方向：

$$
\Delta = -H^{-1} \nabla L
$$

优点	缺点
强凸附近二次收敛	$H$ 求逆 $O(d^3)$
自动缩放各维步长	$H$ 不定 → 非下降方向
	深网 $d$ 巨大不可行

修正：Levenberg–Marquardt 加 $\lambda I$ 使 $H+\lambda I$ 正定。

2. 拟牛顿与 L-BFGS（D3）

$图 2　用梯度历史近似 H$

拟牛顿（quasi-Newton）：不形成完整 $H$，维护 $H^{-1}$ 的低秩近似。

L-BFGS：仅用最近 $m$ 次 $(\boldsymbol{\theta}_t, \nabla L_t)$ 对，$O(md)$ 每步。

方法	适用
L-BFGS	中小规模凸/光滑问题
sklearn Logistic `lbfgs`	默认求解器
深网	极少用全二阶

3. Gauss-Newton 与 Levenberg–Marquardt（D3）

最小二乘 $L(\boldsymbol{\theta}) = \frac{1}{2}\sum_i r_i(\boldsymbol{\theta})^2$，Jacobian $J$：

$$
H \approx J^\top J, \quad \Delta = -(J^\top J)^{-1} J^\top \mathbf{r}
$$

用于非线性最小二乘、神经网络小模型（现在少见）。

4. XGBoost 二阶近似（D7）

$图 3　树分裂用 g_i, h_i$

加性模型 $ \hat{y}i = \sum{t=1}^T f_t(\mathbf{x}_i)$，第 $t$ 步拟合残差。对损失 Taylor 到二阶：

$$
\mathcal{L}^{(t)} \approx \sum_i \left[ g_i f_t(\mathbf{x}_i) + \frac{1}{2} h_i f_t(\mathbf{x}_i)^2 \right] + \Omega(f_t)
$$

$g_i = \partial_{\hat{y}} \ell(y_i, \hat{y}^{(t-1)}_i)$
$h_i = \partial^2_{\hat{y}} \ell(y_i, \hat{y}^{(t-1)}_i)$

叶节点最优权重闭式解 → 分裂增益公式。详见存量 XGBoost。

5. 与一阶方法对比（D6–D8）

$图 4　一阶 vs 二阶选型$

	SGD/Adam	牛顿/L-BFGS
每步代价	$O(d)$	$O(d^3)$ 或 $O(md)$
深网 $d$ 百万+	✓ 标准	✗
凸 logistic	可行	L-BFGS 常更快
非光滑 L1	SGD/坐标下降	不适用

自然梯度、K-FAC 等：用 Fisher 信息矩阵近似 $H$，研究向，工业少。

6. scipy 示例（D12）

import numpy as np
from scipy.optimize import minimize

def rosen(x):
    return sum(100*(x[1:]-x[:-1]**2)**2 + (1-x[:-1])**2)

x0 = np.zeros(5)
res = minimize(rosen, x0, method="L-BFGS-B")
print("L-BFGS-B:", res.fun, res.success)

7. 小结

二阶在中小凸问题与XGBoost 中强大；深网靠一阶 Adam + 工程技巧（10 DL 实践）。

系列导航：03 SGD | 20 大模型