BFGS算法

一種求解無約束非線性優化問題的疊代算法

数值优化中, Broyden–Fletcher–Goldfarb–Shanno(BFGS)算法是一种求解无约束非线性优化问题的迭代算法[1]和相关的Davidon–Fletcher–Powell算法类似,BFGS算法通过利用曲率信息对梯度进行预处理来确定下降方向。曲率信息则是通过维护一个使用广义的割线法逐步近似的关于损失函数Hessian矩陣来获得。

算法

从起始点 和初始的Hessian矩阵 ,重复以下步骤, 会收敛到优化问题的解:

  1. 通过求解方程 ,获得下降方向 
  2.  方向上进行一维的优化(线搜索),找到合适的步长 。如果这个搜索是完全的,则  。在实际应用中,不完全的搜索一般就足够了,此时只要求 满足Wolfe条件
  3.  ,并且令 
  4.  
  5.  

 表示要最小化的目标函数。可以通过检查梯度范数  判斷收敛性。如果 初始化为 ,第一步将等效于梯度下降,但接下来的步骤会受到近似于Hessian矩阵 的调节。

拓展阅读

参考文献

  1. ^ Fletcher, Roger, Practical Methods of Optimization 2nd, New York: John Wiley & Sons, 1987, ISBN 978-0-471-91547-8