BFGS算法

在數值優化中， Broyden–Fletcher–Goldfarb–Shanno（BFGS）算法是一種求解無約束非線性優化問題的迭代算法。 ^[1]和相關的Davidon–Fletcher–Powell算法類似，BFGS算法通過利用曲率信息對梯度進行預處理來確定下降方向。曲率信息則是通過維護一個使用廣義的割線法逐步近似的關於損失函數的Hessian矩陣來獲得。

算法

從起始點${\displaystyle \mathbf {x} _{0}}$和初始的Hessian矩陣${\displaystyle B_{0}}$，重複以下步驟，${\displaystyle \mathbf {x} _{k}}$會收斂到優化問題的解：

1. 通過求解方程${\displaystyle B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}$，獲得下降方向${\displaystyle \mathbf {p} _{k}}$。
2. 在${\displaystyle \mathbf {p} _{k}}$方向上進行一維的優化（線搜索），找到合適的步長${\displaystyle \alpha _{k}}$。如果這個搜索是完全的，則${\displaystyle \alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ 。在實際應用中，不完全的搜索一般就足夠了，此時只要求${\displaystyle \alpha _{k}}$滿足Wolfe條件。
3. 令${\displaystyle \mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}}$，並且令${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}}$。
4. ${\displaystyle \mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}}$。
5. ${\displaystyle B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} }B_{k}^{\mathrm {T} }}{\mathbf {s} _{k}^{\mathrm {T} }B_{k}\mathbf {s} _{k}}}}$。

${\displaystyle f(\mathbf {x} )}$表示要最小化的目標函數。可以通過檢查梯度的範數 ${\displaystyle ||\nabla f(\mathbf {x} _{k})||}$來判斷收斂性。如果${\displaystyle B_{0}}$初始化為${\displaystyle B_{0}=I}$，第一步將等效於梯度下降，但接下來的步驟會受到近似於Hessian矩陣的${\displaystyle B_{k}}$的調節。

拓展閱讀

• 梯度下降
• 擬牛頓法