牛顿法与二阶优化收敛

可视化演示

\u901a\u8fc7\u4e09\u9636\u6bb5\u4ea4\u4e92\u5c55\u793a\u725b\u987f\u6cd5\u5728\u635f\u5931\u66f2\u9762\u4e0a\u7684\u6536\u655b\u8f68\u8ff9\u3001\u4e0e\u68af\u5ea6\u4e0b\u964d\u7684\u6536\u655b\u901f\u5ea6\u5bf9\u6bd4\uff0c\u4ee5\u53ca\u963b\u5c3c\u725b\u987f\u6cd5\u7684\u4fe1\u8d56\u57df\u7b56\u7565\u3002

几何直觉

小齐的第一次下山经历，和他拿到新探杖的经历形成了鲜明对比。起初，他只能感受到脚下某一点的坡度：脚底向前倾斜，说明前面更低；向后倾斜，说明后面更低。沿着最陡下坡的方向走一小步，这就是最朴素的梯度下降。可小齐发现，单纯看坡度会走很多冤枉路：明明快到谷底了，坡度变小，步子也跟着变小，最后还要磨蹭很久。

新的探杖给了小齐第二种感觉：曲率。如果脚下是一块向上翘的凹地，那是碗形；如果是一块凸起的山脊，那是反碗形。知道了“坡度”和“曲率”这两个信息，小齐就能在脑海里给附近的地形画一张简单草图，判断谷底大约在哪里。这个“曲率”在数学上就是 Hessian 矩阵。

对一元函数而言，坡度是导数，曲率是二阶导数，两者合成了一张局部地图的完整描述：

有了这张地图，小齐不必再一小步一小步地试探。他从坡度判断山谷方向，从曲率判断山谷距离，一步就能跨到地图上的“最低点”。几何直觉就此成形：梯度是朝向，Hessian 是尺子。

数学原理

小齐在出发前想把地图画得更精确。他学过一个技巧：任何光滑的地形，在一个小范围内都能被一条抛物线近似替代。真实山谷可能歪歪扭扭，但在小齐脚下几米内，抛物线和真实地面几乎重合。这条抛物线由三个信息决定：当前高度、当前坡度、当前曲率。这就是二阶泰勒展开。

数学上，若当前位置是 $x_k$，移动方向是 $d$，局部二次模型写成：

当真实地形足够光滑，二次模型与真实的高差接近“高阶小量”。小齐于是信任这条抛物线：只要不迈出太远，误差就小。这就是为什么牛顿法本质上是一个“局部二次近似”的迭代过程。

牛顿迭代式

小齐有了二次模型，下一步是求解“这条抛物线的最低点在哪里”。抛物线最低点的条件是：斜率等于零。对上面的模型关于 $d$ 求导并令其为零，得到线性方程组：

解出 $d_k$ 后，小齐从当前位置出发，直接移动到：

注意，这里不是直接计算 $d_k = -H_k^{-1} g_k$ 作为最终步长，而是把它当作候选方向。如果地形真是理想碗形，这一步就会精确落到碗底；如果地形更复杂，小齐还要像后文那样给步子加上阻尼或边界。

收敛性质

小齐最惊喜的发现，出现在一片被大雪覆盖、形状几乎完美的碗形山谷中。他闭上眼睛，直接按牛顿方向跳了一步，睁开眼睛时，已经站在谷底。数学上说，如果目标函数本身就是二次函数，牛顿法具有“二次终止性”：无论从哪里出发，一步到达最优解。

在更真实、非二次的山谷里，小齐依然感到震撼。每一步之后，他与谷底的距离不是按比例缩小，而是被不断“平方”。如果上一步误差是 $0.1$，下一步大约是 $0.001$，再下一步是 $10^{-7}$。这种收敛叫二次收敛：

而更一般的描述是“超线性收敛”：相邻两步误差之比趋于零：

这就是牛顿法“又快又猛”的收敛魅力，也是它被称为二阶优化方法的原因：它不只利用坡度，还利用了地形弯曲带来的高阶信息。

阻尼策略

小齐在山谷里用牛顿法跳了几次，发现一个危险：如果脚下的地形不是标准碗形，他按抛物线预测的“谷底”可能跑到了很远的地方，甚至比原地还高。为了避免这种情况，小齐不再盲目地完全跳过去，而是先朝牛顿方向伸出一只脚，试探着走一小段路。如果地形开始好转，就继续走；如果发现不妙，就立即缩回半步。这个“考虑步长”的做法，就是阻尼牛顿法。

阻尼牛顿法的迭代式改成：

其中 $d_k = -H_k^{-1} g_k$ 是牛顿方向，$\alpha_k$ 是线搜索得到的步长。为了判断步长是否合适，小齐使用 Armijo 条件：

有了阻尼，牛顿法不再只在一个小邻域内有效，而是能应对更崎岖的地形，从而获得全局收敛性。

信赖域方法

除了给步长踩刹车，小齐还有另一种策略：给自己画一个圆圈，只在这个圆圈内相信抛物线地图，圆圈之外的地形一律不信。这个圆圈就是信赖域。每次迭代，小齐在圆内寻找抛物线的极小点，并真正走过去。

信赖域子问题写成：

信赖域方法与阻尼牛顿是两种互补的“安全阀”。阻尼通过缩短步长保护迭代，信赖域通过限制搜索范围保护模型的正确性。许多二次收敛算法都会结合两者，从而兼顾速度与稳健。

适用条件

小齐发现，不是所有地形都适合用牛顿法。首先，抛物线地图必须开口朝上，也就是碗形而不是倒扣的碗。数学上，这要求 Hessian 矩阵正定：

如果 Hessian 不正定，牛顿方向可能把小齐引向高处，而不是谷底。

此外，牛顿法每次迭代都要求解 $n$ 元线性方程组，存储 $n\times n$ 的 Hessian 矩阵，成本约 $O(n^3)$。因此它最适合小规模、光滑、可微两次的优化问题。

工程实践

在实际工作中，小齐学会了三条经验。第一，初始点要选得离谷底别太远。牛顿法的二次收敛是局部性质，好的初始化能让它直接进入“误差平方收缩”的快车道；第二，直接求 Hessian 的逆矩阵并不明智，应该通过求解线性方程组得到牛顿方向，并用 Cholesky 分解等数值稳定算法处理；第三，要结合阻尼或信赖域，防止非凸区域中的意外跳跃。

这里用条件数描述求解难度：Hessian 的条件数 $\kappa(H)$ 越大，线性方程组越难解，牛顿步的数值误差也越大：

回到小齐的故事：他带着坡度手杖和曲率探杖，学会了在光滑的碗形山谷里一步到底，在陌生崎岖地形上则用阻尼和信赖域稳住脚步。这就是牛顿法与二阶优化收敛的全貌。

AI 应用场景

Python 演示

import math  def func(x):    # 目标函数：最小值在 x=1 附近    d = x - 1.0    return d * d + 0.08 * math.pow(d, 4)  def grad(x):    # 一阶导数：坡度    d = x - 1.0    return 2.0 * d + 0.32 * math.pow(d, 3)  def hess(x):    # 二阶导数：曲率    d = x - 1.0    return 2.0 + 0.96 * d * d  def armijo_line_search(x, d, c=1e-4, rho=0.5):    alpha = 1.0    fx = func(x)    gx = grad(x)    while func(x + alpha * d) > fx + c * alpha * gx * d:        alpha *= rho    return alpha  def damped_newton(x0, max_iter=20, tol=1e-9):    xs = [x0]    x = x0    for _ in range(max_iter):        g = grad(x)        h = hess(x)        direction = -g / h        alpha = armijo_line_search(x, direction)        x = x + alpha * direction        xs.append(x)        if abs(grad(x)) < tol:            break    return xs  def gradient_descent(x0, lr=0.16, max_iter=500, tol=1e-9):    xs = [x0]    x = x0    for _ in range(max_iter):        x = x - lr * grad(x)        xs.append(x)        if abs(grad(x)) < tol:            break    return xs  if __name__ == "__main__":    start = 4.0    newton_path = damped_newton(start)    gd_path = gradient_descent(start)    print("阻尼牛顿法迭代次数:", len(newton_path) - 1)    print("梯度下降迭代次数:", len(gd_path) - 1)    print("阻尼牛顿法解:", newton_path[-1])    print("梯度下降法解:", gd_path[-1])

1. def damped_newton(x0, max_iter=20, tol=1e-9):定义阻尼牛顿法主体，每次迭代先算牛顿方向，再做线搜索。
2. direction = -g / h一元函数情形下，牛顿方向就是负梯度除以曲率；在多维问题中这里会变成求解线性方程组。
3. alpha = armijo_line_search(x, direction)用 Armijo 回溯找到安全步长，防止牛顿步跨过谷底。
4. while func(x + alpha * d) > fx + c * alpha * gx * d:Armijo 条件：实际下降量必须达到线性模型预测下降量的一定比例。
5. gradient_descent(start, lr=0.16, ...)固定步长梯度下降作为对照，可以看到它需要更多步才能收敛。

常见误区

面试题