思想
牛顿法中最困难的部分在于计算$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的储存代价