深度学习优化算法（牛顿法

拟牛顿法(Quasi-Newton Methods)是求解非线性优化问题最有效的方法之一，于20世纪50年代提出。DFP、BFGS和L-BFGS算法都是重要的拟牛顿法。考虑如下无约束的极小化问题\(\underset{x} {min} f(x)\)，其中\({\tt x}=(x_1,x_2,...,x_N)^T \in R^N\)这里假设\(f\)为凸函数，且两阶连续可微，此外记极小问题的解为\(x^*\)

为简单起见，首先考虑\(N=1\)的简单清醒。牛顿法的基本思想是：在现有极小点估计值的附近对\(f(x)\)做二阶泰勒展开，进而找到极小点的下一个估计值，设\(x_k\)为当前的极小点的估计值，则

\(\varphi(x)=f(x_k) + f'(x_k)(x-x_k)+\frac{1}{2}f''(x_k)(x-x_k)^2\)

表示\(f(x)\)在\(x_k\)附近的二阶泰勒展开式（略去了关于\(x-x_k\)的高阶项），由于求的是最值，由极值必要条件可值

\(\varphi'(x)=0\)， 即 \(f'(x)+f''(x)(x-x_k)=0\)

从而求得\(x = x_k - \frac{f'(x_k)}{f''(x_k)}\)

如是若给定初始值\(x_0\)则可以构造如下的迭代格式\(x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)}\)

产生序列\(\{x_k\}\)来逼近\(f(x)\)的极小点。在一定条件下，\(\{x_k\}\)可以收敛到\(f(x)\)的极小点

对于\(N>1\)的情形，二阶泰勒展开式可以做推广，此时

\(\varphi({\tt x})=f({\tt x}_k) +\nabla f({\tt x}_k)({\tt x}-{\tt x}_k)+\frac{1}{2}({\tt x}-{\tt x}_k)^T\nabla^2 f({\tt x}_k)({\tt x}-{\tt x}_k)\)

其中\(\nabla f\)为\(f\)的梯度向量，\(\nabla^2f\)为\(f\)的海森矩阵(Hessian matrix)，其定义分别为：

\(\nabla f=\begin{bmatrix} \partial f/ \partial x_1 \\ \partial f/ \partial x_2 \\ \vdots \\\partial f/ \partial x_N \end{bmatrix}\), \(\nabla^2 f=\begin{bmatrix} \partial^2 f/ \partial x_1^2 & \partial^2 f/ \partial x_1 \partial x_2 & \cdots & \partial^2 f/ \partial x_1 \partial x_N\\ \partial^2 f/ \partial x_2 \partial x_1 & \partial^2 f/ \partial x_2^2 & \cdots & \partial^2 f/ \partial x_2 \partial x_N \\ \vdots & \vdots & \cdots & \vdots \\\partial^2 f/ \partial x_N \partial x_1 & \partial^2 f/ \partial x_N \partial x_2 & \cdots & \partial^2 f/ \partial x_N^2 \end{bmatrix}\)

以下分别将其简记为\(g\) 和\(H\)，特别的，若\(f\)的混合偏导数可交换次序，即对\(\forall i,j, \partial^2 f/\partial x_i \partial x_j = \partial^2 f/\partial x_j \partial x_i\)，则海森矩阵\(H\)为对称矩阵。其中\(\nabla f(x_k)\)和\(\nabla^2f(x_k)\)表示\(\tt x\)去值为\(x_k\)后得到的实值向量和矩阵，分别记为\(g_k\)和\(H_k\)

​ 同样地，由于是求极小点，极值必要条件要求它为\(\varphi(x)\)的驻点，即\(\nabla\varphi(x)=0\)，亦即

\(g_k + H_k({\tt x}-{\tt x}_k)=0\)

进一步，若矩阵\(H_k\)非奇异，则可解得\({\tt x}={\tt x}_k - H_k^{-1}·g_k\)，于是给定初始值\(\tt x_0\)，同样可以构造出迭代格式：\({\tt x}_{k+1}={\tt x}_k - H_k^-·g_k\)

这就是原始牛顿迭代法，其迭代格式中的搜索方向\(d_k=-H_k^{-1}·g_k\)称为牛顿方向

为了消除原始牛顿法不能保证函数值稳定的下降的弊病，人们提出了阻尼牛顿法，每次迭代的方向仍采用\(d_k\)，但每次迭代需沿此方向作一维搜索(line search)，寻求最优的步长因子\(\lambda_k\)即

\(\lambda_k = \underset{\lambda \in R}{argmin}f({\tt x}_k + \lambda d_k)\)