牛顿法：理论与推导

像梯度下降 (gradient descent)这样的一阶方法仅依赖损失函数 (loss function)的斜率（梯度）来确定更新方向。它们虽然有效，但收敛可能较慢，尤其是在曲率复杂的区域，例如狭窄的山谷或接近平坦的区域。二阶方法纳入了关于函数曲率的信息，旨在实现更直接、可能更快的收敛到最小值。

牛顿法是基本的二阶优化算法。它的主要思想是迭代地使用一个更简单的函数，特别是二次模型，来近似当前迭代点 $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$ 处的梯度向量 (vector)，而 $\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)$$

几何解释

将此与梯度下降 (gradient descent)更新规则进行比较：$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)$ 完全相同。

流程图说明了牛顿法单一步骤中涉及的计算。请注意对计算梯度和黑塞矩阵的依赖性，以及随后的矩阵求逆操作。

收敛性质

在特定条件下，牛顿法表现出非常快的局部二次收敛。这意味着一旦迭代点 $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$）是一个显著的优点。

然而，这种理想的收敛依赖于几个假设：

1. 函数 $f$ 必须是二阶连续可微的。
2. 在解 $x^*$ 附近，黑塞矩阵 $H_k$ 必须是正定的。如果黑塞矩阵不是正定的，牛顿步长 $p_k$ 甚至可能不是下降方向（它可能指向最大值或鞍点）。
3. 每一步的黑塞矩阵都必须是可逆的（非奇异的）。
4. 初始点 $x_0$ 必须足够接近解 $x^*$。远离解时，牛顿法不保证收敛，甚至可能发散。

这些假设，特别是形成和求逆黑塞矩阵的计算负担（对于 $n \times n$ 的稠密矩阵为 $O(n^3)$）以及正定性要求，促使了改进方法和替代方案的发展，例如拟牛顿法，我们将在后面进行讨论。