牛顿法与拟牛顿法

牛顿法是数值优化算法中的大家族，她和她的改进型在很多实际问题中得到了应用。在机器学习中，牛顿法是和梯度下降法地位相当的的主要优化算法。

牛顿法不仅可以用来求解函数的极值问题，还可以用来求解方程的根，二者在本质上是一个问题，因为求解函数极值的思路是寻找导数为 0 的点，这就是求解方程。在本文中，我们介绍的是求解函数极值的牛顿法。

和梯度下降法一样，牛顿法也是寻找导数为 0 的点，同样是一种迭代法。核心思想是在某点处用二次函数来近似目标函数，得到导数为 0 的方程，求解该方程，得到下一个迭代点。因为是用二次函数近似，因此可能会有误差，需要反复这样迭代，直到到达导数为 0 的点处。下面我们开始具体的推导，先考虑一元函数的情况，然后推广到多元函数。

一元函数的情况

为了能让大家更好的理解推导过程的原理，首先考虑一元函数的情况。根据一元函数的泰勒展开公式，我们对目标函数在 $x_0$ 点处做泰勒展开，有： $f(x)=f\left(x_{0}\right)+f'\left(x_{0}\right)\left(x-x_{0}\right)+\frac{1}{2} f^{''}\left(x_{0}\right)\left(x-x_{0}\right)^{2}+\ldots+\frac{1}{n !} f^{(n)}\left(x_{0}\right)\left(x-x_{0}\right)^{n} \ldots$ 如果忽略 2 次以上的项，则有： $f(x)=f\left(x_{0}\right)+f'\left(x_{0}\right)\left(x-x_{0}\right)+\frac{1}{2} f^{''}\left(x_{0}\right)\left(x-x_{0}\right)^{2}$ 现在我们在 $x_0$ 点处，要以它为基础，找到导数为 0 的点，即导数为 0。对上面等式两边同时求导，并令导数为 0，可以得到下面的方程： $f^{\prime}(x)=f^{\prime}\left(x_{0}\right)+f^{\prime \prime}\left(x_{0}\right)\left(x-x_{0}\right)=0$ 可以解得： $x=x_{0}-\frac{f^{\prime}\left(x_{0}\right)}{f^{\prime \prime}\left(x_{0}\right)}$ 这样我们就得到了下一点的位置，从而走到 $x_1$。接下来重复这个过程，直到到达导数为 0 的点，由此得到牛顿法的迭代公式： $x_{t+1}=x_{t}-\frac{f^{\prime}\left(x_{t}\right)}{f^{\prime \prime}\left(x_{t}\right)}$ 给定初始迭代点 $x_0$ ，反复用上面的公式进行迭代，直到达到导数为 0 的点或者达到最大迭代次数。

多元函数的情况

无约束最优化问题 $\min _{x \in \mathbf{R}^{n}} f(x)$

其中 $x^{*}$ 为目标函数的极小点。

设 $f(x)$ 具有二阶连续偏导数，若第 $k$ 次迭代值为 $x^{k}$ ，则可将 $f(x)$ 在 $x^{k}$ 附近进行二阶泰勒展开 $f(x)=f\left(x^{(k)}\right)+g_{k}^{T}\left(x-x^{(k)}\right)+\frac{1}{2}\left(x-x^{(k)}\right)^{T} H\left(x^{(k)}\right)\left(x-x^{(x)}\right)$

其中 $g_{k}=g\left(x^{(k)}\right)=\nabla f\left(x^{(k)}\right)$ 是 $f(x)$ 的梯度向量在点 $x^{k}$ 的值，$H\left(x^{(k)}\right)$ 是 $f(x)$ 得黑塞矩阵： $H(x)=\left[\frac{\partial^{2} f}{\partial x_{i} \partial x_{j}}\right]_{n \times n}$ 在点 $x^{k}$ 的值。

函数 $f(x)$ 有极值的必要条件是在极值点处一阶导数为0，即梯度向量为0。特别的当 $H\left(x^{(k)}\right)$ 是正定矩阵时，函数 的 $f(x)$ 极值为极小值。

牛顿法利用极小点得必要条件： $\nabla f(x)=0$

每次迭代从点 $x^{k}$ 开始，求目标函数得极小点，作为第 $k+1$ 次迭代值 $x^{k+1}$，具体地，假设 $x^{k+1}$ 满足： $\nabla f\left(x^{(k+1)}\right)=0$

由 $f(x)=f\left(x^{(k)}\right)+g_{k}^{T}\left(x-x^{(k)}\right)+\frac{1}{2}\left(x-x^{(k)}\right)^{T} H\left(x^{(k)}\right)\left(x-x^{(x)}\right)$ ，根据二阶泰勒展开，对 $\nabla f(x)$ 在 $x^{k}$ 进行展开得（也可以对上述泰勒公式再进行求导）得： $\nabla f(x)=g_{k}+H_{k}\left(x-x^{(k)}\right)$ 其中 $H_{k}=H\left(x^{(k)}\right)$ ，这样, $\nabla f\left(x^{(k+1)}\right)=0$ 成为： $g_{k}+H_{k}\left(x^{(k+1)}-x^{(k)}\right)=0$

因此， $x^{(k+1)}=x^{(k)}-H_{k}^{-1} g_{k}$ 或者： $x^{(k+1)}=x^{(k)}+p_{k}$

其中， $H_{k} p_{k}=-g_{k}$

式 $x^{(k+1)}=x^{(k)}-H_{k}^{-1} g_{k}$ 作为迭代公式得算法就是牛顿法

算法步骤

牛顿法与梯度下降法

梯度下降法和牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法是用二阶的海森矩阵的逆矩阵求解。相对而言，使用牛顿法收敛更快（迭代更少次数）。但是每次迭代的时间比梯度下降法长。

梯度下降法：$x_{(k+1)}=x_{(k)}-\lambda \nabla f\left(x_{k}\right)$

牛顿法：$x_{(k+1)}=x_{(k)}-\lambda\left(H_{(k)}\right)^{-1} \nabla f\left(x_{k}\right)$

梯度下降法中，每一次 $\mathbf{x}$ 增加的方向一定是梯度相反的方向 $-\epsilon_{k} \nabla_{k}$。增加的幅度由 $\epsilon_{k}$ 决定，若跨度过大容易引发震荡。

而牛顿法中，每一次 $\mathbf{x}$ 增加的方向是梯度增速最大的反方向 $-\mathbf{H}_{k}^{-1} \nabla_{k}$（它通常情况下与梯度不共线）。增加的幅度已经包含在 $\mathbf{H}_{k}^{-1}$ 中（也可以乘以学习率作为幅度的系数）。

对于不带约束条件的问题，我们可以将x的初始值设定为任意值，最简单的，可以设置为全0的向量。迭代终止的判定规则和梯度下降法相同，是检查梯度是否接近于0。

面临的问题

牛顿法并不能保证每一步迭代时函数值下降，也不保证一定收敛。为此，提出了一些补救措施，其中的一种是直线搜索（line search）技术，即搜索最优步长。具体做法是让 $\gamma$ 取一些典型的离散值，如0.0001,0.001,0.01等，比较取哪个值时函数值下降最快，作为最优步长。

和梯度下降法相比牛顿法有更快的收敛速度，但每一步迭代的成本也更高。在每次迭代中，除了要计算梯度向量还要计算Hessian矩阵，并求解Hessian矩阵的逆矩阵。

牛顿法面临的另外一个问题是Hessian矩阵可能不可逆，从而导致这种方法失效。此外，求解Hessian矩阵的逆矩阵或者求解线性方程组计算量大，需要耗费大量的时间。为此，提出了拟牛顿法这种改进方案

除此之外，牛顿法在每次迭代时序列xi可能不会收敛到一个最优解，它甚至不能保证函数值会按照这个序列递减。解决第一个问题可以通过调整牛顿方向的步长来实现，目前常用的方法有两种：直线搜索和可信区域法。

拟牛顿法

牛顿法在每次迭代时需要计算出Hessian矩阵，然后求解一个以该矩阵为系数矩阵的线性方程组，这非常耗时，另外Hessian矩阵可能不可逆。为此提出了一些改进的方法，典型的代表是拟牛顿法（Quasi-Newton）。

在牛顿法的迭代中，需要计算海森矩阵的逆矩阵 ，这一计算比较复杂，考虑用一个 阶矩阵 来近似代替 。这就是拟牛顿法的基本想法。

先看下牛顿法迭代中海森矩阵 ${H_{k}}$ 满足的条件。首先 ${H_{k}}$满足以下关系：

在公式 $\nabla f(x)=g_{k}+H_{k}\left(x-x^{(k)}\right)$ 中，取 $x=x^{(k+1)}$ 既得： $g_{k+1}-g_{k}=H_{k}\left(x^{(k+1)}-x^{(k)}\right)$

记 $y_{k}=g_{k+1}-g_{k}, \delta_{k}=x^{(k+1)}-x^{(k)}$ ，则 $y_{k}=H_{k} \delta_{k}$

或 $H_{k}^{-1} y_{k}=\delta_{k}$

上式称为拟牛顿条件

其次，如果 ${H_{k}}$ 是正定的（ ${H_{k}^{-1}}$也是正定的），那么保证牛顿法的搜索方向 $p_{k}$ 是下降方向。这是因为搜索方向是 $p_{k}=-H_{k}^{-1} g_{k}$ ，由 $x^{(k+1)}=x^{(k)}-H_{k}^{-1} g_{k}$ 有： $x=x^{(k)}+\lambda p_{k}=x^{(k)}-\lambda H_{k}^{-1} g_{k}$

所以 $f(x)$ 在 $x^{k}$ 得泰勒展开式 ： $f(x)=f\left(x^{(k)}\right)+g_{k}^{\mathrm{T}}\left(x-x^{(k)}\right)+\frac{1}{2}\left(x-x^{(k)}\right)^{\mathrm{T}} H\left(x^{(k)}\right)\left(x-x^{(k)}\right)$ 可以近似写成： $f(x)=f\left(x^{(k)}\right)-\lambda g_{k}^{\mathrm{T}} H_{k}^{-1} g_{k}$ 因 ${H_{k}^{-1}}$ 正定，故有 $g_{k}^{\mathrm{T}} H_{k}^{-1} g_{k}>0$ ， 。当 为一个充分小的正数时，总有 $f(x)<f\left(x^{(k)}\right)$ ，也就是说 是下降方向。

因此拟牛顿法将 ${G_{k}}$ 作为 ${H_{k}^{-1}}$ 近似。要求 满 ${G_{k}}$ 足同样的条件。首先，每次迭代矩阵 ${G_{k}}$ 是正定的。同时， ${G_{k}}$ 满足下面的拟牛顿条件： $G_{k+1} y_{k}=\delta_{k}$

按照拟牛顿条件，在每次迭代中可以选择更新矩阵 ${G_{k+1}}$ $G_{k+1}=G_{k}+\Delta G_{k}$ 根据此条件，构造出了多种拟牛顿法，典型的有 DFP 算法、BFGS算法、L-BFGS算法等，

BFGS algorithm

BFGS（Broyden-Fletcher-Goldfarb-Shanno）

BFGS 算法是最流行得拟牛顿算法。

可以考虑用 $G_k$ 逼近海森矩阵得逆矩阵 $H^{-1}$，也可以考虑用 $B_k$ 逼近海森矩阵。

这时，相应得拟牛顿条件是 $B_{k+1} \delta_{k}=y_{k}$ 可以用到同样得方法得到另一个迭代公式。首先令 $\begin{array}{c} B_{k+1}=B_{k}+P_{k}+Q_{k} \\ B_{k+1} \delta_{k}=B_{k} \delta_{k}+P_{k} \delta_{k}+Q_{k} \delta_{k} \end{array}$

考虑使 $P_k$ 和 $Q_k$ 满足： $\begin{array}{c} P_{k} \delta_{k}=y_{k} \\ Q_{k} \delta_{k}=-B_{k} \delta_{k} \end{array}$ 找出适合条件得 $P_k$ 和 $Q_k$ ，得到 BFGS 算法矩阵 $B_{k+1}$ 得迭代公式： $B_{k+1}=B_{k}+\frac{y_{k} y_{k}^{\mathrm{T}}}{y_{k}^{\mathrm{T}} \delta_{k}}-\frac{B_{k} \delta_{k} \delta_{k}^{\mathrm{T}} B_{k}}{\delta_{k}^{\mathrm{T}} B_{k} \delta_{k}}$ 可以证明，如果初始矩阵 $B_0$ 是正定的，则迭代过程中的每个矩阵 $B_k$ 都是正定的。

BFGS 算法流程

参考

• 最优化算法之牛顿法
• 理解牛顿法
• 最优化算法之牛顿法
• 最优化算法之牛顿法