牛顿法求解非线性优化

前面在风格迁移的时候用到了LBFGS，很好奇只需要设置一个闭包迭代即可，不需要像动量算法等一阶优化算法一样设置步长学习率等，于是系统地去了解了一下牛顿法与拟牛顿法

牛顿法

首先回想起泰勒展开，此式子即为$f(x)$在$x_k$附近的二阶泰勒展开式

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

令导数为0即可求得最值

$$\phi'(x)=0$$

省略掉高阶项，则

$$f'(x_k)+f''(x_k)(x-x_k)=0$$

$\therefore$

$$x = x_k-\frac{f'(x_k)}{f''(x_k)},k=0,1,2,···$$

于是我们就可以从初始$x_0$值开始用此式进行迭代来逼近极小值点，其逼近就是在每次迭代的时候直接跳到近似函数的最小点

那么对于高维度的情形，原泰勒公式就可以表示为

$$\phi(X) = \nabla f(X_k)·(X-X_k)+\frac{1}{2}(X-X_k)^T·\nabla^2f(X_k)·(X-X_k)$$

这里的$\nabla^2 f(X_k)$即为Hessian矩阵，其实就是二阶梯度

$$\nabla^2 f(X_k)= \begin{bmatrix} {\frac{\partial^2 f}{\partial x_1^2}}&{\frac{\partial^2 f}{\partial x_1\partial x_2}}&{\cdots}&{\frac{\partial^2 f}{\partial x_1\partial x_n}}\\ {\frac{\partial^2 f}{\partial x_2\partial x_1}}&{\frac{\partial^2 f}{\partial x_2^2}}&{\cdots}&{\frac{\partial^2 f}{\partial x_2\partial x_n}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {\frac{\partial^2 f}{\partial x_n\partial x_1}}&{\frac{\partial^2 f}{\partial x_2^2}}&{\cdots}&{\frac{\partial^2 f}{\partial x_n\partial x_n}}\\ \end{bmatrix}$$

$\nabla f(X_k)$就是一阶梯度，不展开了

因为Hessian矩阵是实对称矩阵，我们可以将其分解为一组实特征值和一组特征向量的正交基。在特定方向$d$的二阶导数可以写成$d^THd$。

当$d$是$H$的一个特征向量的时候，这个方向的二阶导数就是对应的特征值。对于其他方向$d$，方向二阶导数是所有特征值的加权平均，权重在0和1之间，且与$d$夹角越小的特征值权重越大。最大特征值确定最大二阶导数，最小特征值确定最小二阶导数。

记$g_k=\nabla f(X_k)$,$H_k=\nabla^2 f(X_k)$，

$$\nabla \phi(X)=0$$

则

$$g_k+H_k(X-X_k)=0$$

$H_k$必为非奇异矩阵（满秩矩阵）

$\therefore$

$$X = X_k-H_k^{-1}·g_k ,k=0,1,2,\cdots$$

此即为牛顿法的迭代式，$d_k=-H_k^{-1}·g_k$称为牛顿方向

牛顿法求出的方向是一个逼近，因为其省略了泰勒的高阶展开项（但如果是二次函数，那就不是逼近了，这时候Hessian矩阵退化为常数矩阵，只需要一次运算即可到达最优点）

缺陷

1. 使用牛顿法可以比一阶优化算法更快的收敛，因为每次它都是直接跳到近似函数的最小点（对于二次函数，直接一步收敛），但是这种特性在鞍点附近会造成病态。

2. 会造成局部收敛

3. Hessian矩阵的计算量是其它一阶优化方法的平方倍，所以对硬件计算负担要求极高

4. 由于步长是定的，所以牛顿方向$-H_k^{-1}·g_k$并不能保证稳定下降，其并不是梯度下降算法

5. 函数必须二阶可导，Hessian矩阵必须为正定矩阵

深度学习通常都有很多局部极值，鞍点，且计算量巨大，所以很少在深度学习中使用牛顿法

改进

1. 针对第四个缺陷，可以对其进行改进，加入线搜索，称作阻尼牛顿法，这个思想和动量算法思想一样

   仍然用$d_k$在方向上进行迭代，但是每次迭代的时候需要进行一次线搜索，寻求最优步长因子$\lambda_k $

   $d_k\to\lambda_k d_k$

   $\lambda_k=arg\min f(x_k+\lambda_k d_k)$

2. 可以通过多种手段避免直接对Hessian矩阵求逆

   比如共轭梯度法（PCG），代数多重网格法（AMG）等

   补充PCG思想：结合梯度下降与牛顿法，在一个方向上用牛顿法，一次性迭代完，理论上N个方向N次即可收敛

3. 拟牛顿法