像梯度下降这样的一阶方法仅依赖损失函数的斜率(梯度)来确定更新方向。它们虽然有效,但收敛可能较慢,尤其是在曲率复杂的区域,例如狭窄的山谷或接近平坦的区域。二阶方法纳入了关于函数曲率的信息,旨在实现更直接、可能更快的收敛到最小值。牛顿法是基本的二阶优化算法。它的主要思想是迭代地使用一个更简单的函数,特别是二次模型,来近似当前迭代点 $x_k$ 周围的目标函数 $f(x)$,然后找出该模型的最小值。这个最小值作为下一个迭代点 $x_{k+1}$。回顾函数 $f: \mathbb{R}^n \to \mathbb{R}$ 在点 $x_k$ 处的二阶泰勒展开式: $$ f(x_k + p) \approx f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T \nabla^2 f(x_k) p $$ 这里,$p = x - x_k$ 是我们希望从 $x_k$ 迈出的步长。$\nabla f(x_k)$ 是 $f$ 在 $x_k$ 处的梯度向量,而 $\nabla^2 f(x_k)$ 是 $f$ 在 $x_k$ 处的黑塞矩阵,它包含所有二阶偏导数。我们将 $x_k$ 处的黑塞矩阵记为 $H_k = \nabla^2 f(x_k)$。牛顿法将函数 $f$ 在 $x_k + p$ 处的二次模型定义为 $m_k(p)$: $$ m_k(p) = f(x_k) + \nabla f(x_k)^T p + \frac{1}{2} p^T H_k p $$ 为了找到最佳步长 $p$,我们寻求使这个二次模型 $m_k(p)$ 最小的 $p_k$ 值。假设 $m_k(p)$ 有一个唯一最小值(这需要黑塞矩阵 $H_k$ 是正定的),我们可以通过将 $m_k(p)$ 对 $p$ 的梯度设为零来找到它: $$ \nabla_p m_k(p) = \nabla f(x_k) + H_k p = 0 $$ 求解这个关于步长 $p$ 的线性系统,我们称之为牛顿步长 $p_k$,得到: $$ H_k p_k = - \nabla f(x_k) $$ 假设黑塞矩阵 $H_k$ 可逆,我们得到: $$ p_k = - H_k^{-1} \nabla f(x_k) $$ 这个 $p_k$ 表示导致局部二次近似模型最小值的步长方向和大小。牛顿法的更新规则定义为: $$ x_{k+1} = x_k + p_k = x_k - H_k^{-1} \nabla f(x_k) $$几何解释将此与梯度下降更新规则进行比较:$x_{k+1} = x_k - \alpha \nabla f(x_k)$,其中 $\alpha$ 是学习率。梯度下降总是沿着负梯度的方向移动,即局部最速下降的方向。牛顿法通过将负梯度乘以黑塞矩阵的逆 $H_k^{-1}$ 来调整这个方向。黑塞矩阵 $H_k$ 捕捉了函数 $f$ 在 $x_k$ 处的曲率。乘以其逆矩阵,可以根据这种曲率有效地重新调整梯度分量的大小。在曲率高(函数急剧增加)的方向上,步长会减小。在曲率低(函数更平坦)的方向上,步长会增大。这使得算法能够更直接地朝着最小值移动,尤其是在梯度下降容易出现锯齿形的长谷中。如果目标函数 $f(x)$ 本身是一个严格凸二次函数,牛顿法将从任意起点一步找到精确的最小值,因为二次模型 $m_k(p)$ 将与 $f(x_k+p)$ 完全相同。digraph G { rankdir=LR; node [shape=box, style=rounded, fontname="sans-serif", fontsize=10]; edge [fontname="sans-serif", fontsize=9]; subgraph cluster_0 { style=filled; color="#e9ecef"; // gray label = "牛顿法步长计算"; xk [label="当前点\nx_k"]; grad_fk [label="计算梯度\n∇f(x_k)", shape=ellipse, style=filled, fillcolor="#a5d8ff"]; // blue hess_fk [label="计算黑塞矩阵\nH_k = ∇²f(x_k)", shape=ellipse, style=filled, fillcolor="#a5d8ff"]; // blue inv_hess [label="计算黑塞矩阵的逆\nH_k⁻¹", shape=ellipse, style=filled, fillcolor="#bac8ff"]; // indigo newton_step [label="计算牛顿步长\np_k = -H_k⁻¹ ∇f(x_k)", shape=ellipse, style=filled, fillcolor="#bac8ff"]; // indigo update [label="更新点\nx_{k+1} = x_k + p_k", shape=ellipse, style=filled, fillcolor="#96f2d7"]; // teal xk -> grad_fk; xk -> hess_fk; hess_fk -> inv_hess [label="需要可逆性与计算成本"]; grad_fk -> newton_step; inv_hess -> newton_step; xk -> update; newton_step -> update; update -> xk [label="下一次迭代", style=dashed]; } }流程图说明了牛顿法单一步骤中涉及的计算。请注意对计算梯度和黑塞矩阵的依赖性,以及随后的矩阵求逆操作。收敛性质在特定条件下,牛顿法表现出非常快的局部二次收敛。这意味着一旦迭代点 $x_k$ 足够接近实际最小值 $x^$,每一步的误差都会呈二次方下降。形式上,如果 $e_k = |x_k - x^|$,那么二次收敛意味着对于某个常数 $C$,有 $|e_{k+1}| \le C |e_k|^2$。这种快速收敛速度相对于一阶方法通常的线性收敛速度(对于 $c < 1$,有 $e_{k+1} \le c e_k$)是一个显著的优点。然而,这种理想的收敛依赖于几个假设:函数 $f$ 必须是二阶连续可微的。在解 $x^*$ 附近,黑塞矩阵 $H_k$ 必须是正定的。如果黑塞矩阵不是正定的,牛顿步长 $p_k$ 甚至可能不是下降方向(它可能指向最大值或鞍点)。每一步的黑塞矩阵都必须是可逆的(非奇异的)。初始点 $x_0$ 必须足够接近解 $x^*$。远离解时,牛顿法不保证收敛,甚至可能发散。这些假设,特别是形成和求逆黑塞矩阵的计算负担(对于 $n \times n$ 的稠密矩阵为 $O(n^3)$)以及正定性要求,促使了改进方法和替代方案的发展,例如拟牛顿法,我们将在后面进行讨论。