BFGS方法推导
可以构造一个二次函数来开始,假设第k次迭代为:
注意为n x n对称正定矩阵,可以在每次迭代中更新。注意到这个构造函数在p=0的时候,和和原函数是相同的。对其求导,得到
公式2即为搜索方向向量,由此第k+1次迭代为(其中可以用强Wolfe准则来计算):
为了不每次都计算(计算太复杂),Davidon提出用最近迭代的几步来计算它。
我们已经计算出,现在构造其在k+1次迭代的二次函数:
怎么求呢?函数应该在处和处和目标函数导数一致。对其求导,并令,即处得:(处自然相等,)
调整方程得:
令,方程6为:
令,得到另一个形式:
由此,方程2可以写为:
由于我们需要一个比较简单的更新的方法,令:
其中和为秩1或秩2的矩阵。
令为:
联立方程7,方程10和方程11得:
等价于:
通过方程13发现,和不唯一,令和分别平行于和,即和,带入方程11得:
把和带入方程13得:
整理后得到:
所以,,
即,。
最后联立方程14,代入到方程10得:
用同样的方式可以得到:
Sherman Morison Woodbury公式:
下面对方程18应用Sherman Morison Woodbury公式:(注意推导中的是方程中的)(参考文档):
现在我们得到结果:
令,方程19可得BFGS方法的迭代方程:
LBFGS方法推导
令,则BFGS方程可写成:
参考文档
则从k=0开始有:
由上面可见,计算需要用到组数据,数据量非常大,LBFGS算法就采取只去最近的m组数据来运算,即可以构造近似计算公式:
最后Numerial Optimization 这本书给出了LBFGS的双向循环算法:
具体实现代码可以参见Breeze LBFGS
最后验证算法对公式22的正确性:参考文档
令:
令,这里的m指的是从现在到历史记录m次的后一次,因为LBFGS只记录m次历史:
本作品采用知识共享署名 4.0 国际许可协议进行许可。