牛顿法求解非线性优化

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

牛顿法

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

令导数为0即可求得最值

省略掉高阶项,则

$\therefore$

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

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

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

$\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)$,

$H_k$必为非奇异矩阵(满秩矩阵)

$\therefore$

此即为牛顿法的迭代式,$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. 拟牛顿法