拟牛顿法

思想

牛顿法中最困难的部分在于计算$H$和$H^{-1}$

拟牛顿法的思想就是不用二阶偏导数而构造出可以近似$H$和$H^{-1}$的正定对称矩阵,在拟牛顿的条件下优化目标函数。但是不可能随便一个矩阵都能近似$H$,所以我们要给近似矩阵开一个条件,也就是下面的拟牛顿条件

拟牛顿条件

由上一篇我写的文章可知(依然省略掉高阶导数无穷项,实际上应该用$≈$,为了方便这里都用$=$了

设$x=x_k$

记$s_k=x_{k+1}-x_k,y_k=g_{k+1}-g_k$

$\therefore y_k=H_{k+1}\cdot s_k$

或$s_k=H^{-1}_{k+1}\cdot y_k$

此即为拟牛顿条件

选择合适的$B_{k+1}$做$H_{k+1}$的近似,合适的$D_{K+1}$做$H^{-1}_{k+1}$的近似,使他们满足拟牛顿条件即可

相当于给拟合$H,H^{-1}$做了一个约束,使得在$f(x_k)与f(x_{k+1})$拟合矩阵与真实矩阵的一阶导相等

以下不同的算法实际上就是设计拟合矩阵的算法

DFP算法

DFP算法通过迭代的方法对$D_{K+1}$做$H^{-1}_{k+1}$的近似

主要设置$D_k$待定形式为

推导过程类似BFGS算法,略,见下

一般$D_0=I$

BFGS算法

BFGS算法通过迭代的方法对$B_{K+1}$做$H_{k+1}$的近似,直接逼近Hessian矩阵

采用迭代法

一般$B_0=I$

设置$B_k$的待定形式

$uu^T$和$vv^T$正好构成对称矩阵

代入$y_k=H_{k+1}\cdot s_k$中($B_{k+1}$逼近$H_{k+1}$)得

$u^Ts_k$和$v^Ts_k$都是常数,不妨令$\alpha u^Ts_k=1,\beta v^ts_k=-1,u=y_k,v=B_ks_k$,

但由于必须储存$D$,使得储存开销很大,不适用大数据大型模型

LBFGS算法

通过避免储存完整的Hessian逆运算近似$D$,降低BFGS的储存代价