牛顿法

牛顿法是一种高效的迭代算法，其被广泛应用于方程求根和凸函数最优化。

一、牛顿法在方程求根中的应用

函数$f(x)$f(x)的一阶泰勒展开式为：$f(x)=f(x_0)+f'(x_0)(x-x_0)$f(x)=f(x0​)+f′(x0​)(x−x0​)函数的根即为$f(x)=0$f(x)=0处，由此得到迭代公式：$x=x_0-\frac{f(x_0)}{f'(x_0)}$x=x0​−f′(x0​)f(x0​)​
利用牛顿法进行求根的迭代示意图如下：

利用牛顿法求得的方程的根严重依赖于迭代初始位置，且只能求得一个根。因此其适用范围较窄，大部分情况下仅用于二次函数的求根。

二、牛顿法在最优化中的应用

假设多元凸函数$f(\boldsymbol x)$f(x)连续二阶可导，基于二阶泰勒展开，可得：$f(\boldsymbol x)=f(\boldsymbol x_0)+\nabla f(\boldsymbol x_0)^T(\boldsymbol{x-x_0})+\frac{1}{2}(\boldsymbol{x-x_0})^TH(\boldsymbol x_0)(\boldsymbol{x-x_0})$f(x)=f(x0​)+∇f(x0​)T(x−x0​)+21​(x−x0​)TH(x0​)(x−x0​)函数取最小值的必要条件为梯度为$\boldsymbol 0$0，因此对上式两侧求梯度，可得：$\nabla f(\boldsymbol x)=\nabla f(\boldsymbol x_0)+(\boldsymbol{x-x_0})H(\boldsymbol x_0)=0$∇f(x)=∇f(x0​)+(x−x0​)H(x0​)=0由此，可进一步得到如下迭代公式：$\boldsymbol x=\boldsymbol x_0-\nabla f(\boldsymbol x_0)H^{-1}(\boldsymbol x_0)$x=x0​−∇f(x0​)H−1(x0​)

如果说梯度下降法是找到了迭代点处的一个超平面进行函数的拟合，并找到该平面上当前点梯度最快的下降方向；而牛顿法则是找到了迭代点处的一个曲面进行函数的拟合，并充分考虑二阶导数的信息来寻找下一个迭代点。当Hessen矩阵为正定阵时，可以保证牛顿法的搜索方向是函数的下降方向。

牛顿法的迭代速度较梯度下降法快，但其每次迭代中的矩阵运算量更大。尤其是需要计算迭代点处Hessen矩阵的逆，其有可能是不存在的。学者们提出了拟牛顿法来解决上述问题。

三、拟牛顿法

拟牛顿法的核心思想为：找到一个合适的正定阵计算方法$\boldsymbol G(x)$G(x)，使其能够代替$\boldsymbol H^{-1}(x)$H−1(x)。从而解决$\boldsymbol H(x)$H(x)不可直接求逆，或者求逆计算量过大的问题。

那这个$\boldsymbol G(x)$G(x)应该什么样的条件呢？根据牛顿法中如下推导公式：$\nabla f(\boldsymbol x_{k+1})=\nabla f(\boldsymbol x_k)+(\boldsymbol{x_{k+1}-x_k})H(\boldsymbol x_k)$∇f(xk+1​)=∇f(xk​)+(xk+1​−xk​)H(xk​)可令$\boldsymbol y_k=\nabla f(\boldsymbol x_{k+1})-\nabla f(\boldsymbol x_k)$yk​=∇f(xk+1​)−∇f(xk​)，$\boldsymbol \delta_k=\boldsymbol x_{k+1}-\boldsymbol x_k$δk​=xk+1​−xk​

因此，$\boldsymbol G(x)$G(x)需满足如下的拟牛顿条件：$\boldsymbol G_k(\boldsymbol x)\boldsymbol y_k= \boldsymbol \delta_k$Gk​(x)yk​=δk​

需要再次强调的是：
（1）$\boldsymbol G(x)$G(x)是一个迭代矩阵，其随着每轮迭代点的位置变化会做相应的迭代；
（2）$\boldsymbol G(x)$G(x)应当为正定阵，以保证每步迭代是沿着函数下降的方向。

常见的求解拟牛顿的算法有DFP算法、BFGS算法和Broyden类算法，其中BFGS算法以及其衍生出的L-BFGS算法是目前最流行的拟牛顿算法。