牛顿类算法
梯度法仅仅依赖函数值和梯度的信息（一阶信息），如果函数 \(f(x)\) 充分光滑，则可以利用二阶导数信息构造下降方向 \(d^k\)。
经典牛顿法
对二次可微函数，考虑 \(f(x)\) 在迭代点 \(x^k\) 处的二阶泰勒展开：
\[
f(x^k + d^k) = f(x^k) + \nabla f(x^k)^\top d^k + \frac{1}{2}(d^k)^\top \nabla^2f(x^k)^\top d^k + \mathcal{o}\left( \Vert d^k \Vert^2 \right)
\]
目标是根据这个泰勒展开选取下降方向。如果忽略高阶无穷小，并将等式看作关于 \(d^k\) 的二次函数并对其取极小，则有
\[
\nabla^2f(x^k)d^k = -\nabla f(x^k)
\]
上式被称为牛顿方程，容易看出当 \(\nabla^2f(x^k)\) 非奇异时，更新方向 \(d^k = -\nabla^2f(x^k)^{-1}\nabla f(x^k)\)，称其为牛顿方向。由此得到经典牛顿法的迭代格式为：
\[
x^{k + 1} = x^k - \nabla^2f(x^k)^{-1}\nabla f(x^k)
\]
其中，步长 \(\alpha^k = 1\) 为常数。
收敛性分析
经典牛顿法有很好的局部收敛性质。
经典牛顿法的收敛性
假设目标函数 \(f\) 是二阶连续可微的函数，且海瑟矩阵在最优值点 \(x^*\) 的一个领域 \(N_\delta (x^*)\) 内是利普希茨连续的，即存在常数 \(L > 0\) 使得
\[
\Vert \nabla^2 f(x) - \nabla^2 f(y) \Vert \leqslant L \Vert x - y \Vert, \forall x, y \in N_\delta (x^*)
\]
如果函数 \(f(x)\) 在点 \(x^*\) 处满足 \(\nabla f(x^*) = 0, \nabla^2 f(x^*) \succ 0\)，则对于经典牛顿法有如下结论：
- 如果初始点离 \(x^*\) 足够近，则牛顿法产生的迭代点列 \(\{ x^k \}\) 收敛到 \(x^*\)；
- \(\{ x^k \}\) 收敛到 \(x^*\) 的速度是 \(\mathcal{Q}\)-二次的；
- \(\{ \nabla f(x^k) \}\) \(\mathcal{Q}\)-二次收敛到 0。
另外，对于正定二次函数而言，牛顿法一步即可达到最优解。