BFGS演算法剖析與實現

05-17

BFGS演算法剖析與實現

來自專欄 ML隨筆

之前介紹DFP演算法是用以進行Hessian逆矩陣的近似，這裡所的BFGS是從逼近Hessian原始矩陣出發，然後進行一系列推導的過程。其最後通過Sherman-Morrison公式將輸出進行變換，仍然以更新Hessian逆矩陣來實現的，所不同的是由於其推導的初始目標不同，因此最後的迭代公式與DFP不同。最後一步的更新公式為： $H_{k+1}=(I-frac{{s_k}{{y_k}^T}}{{{y_k}^T}{s_k}})D_k(I -frac{{y_k}{{s_k}^T}}{{{y_k}^T}{s_k}})+frac{{s_k}{{s_k}^T}}{{{y_k}^T}{s_k}}$ 其它步驟可見擬牛頓法之DFP演算法剖析。

代碼

代碼位置見：https://github.com/sloth2012/scalaML/blob/master/src/main/scala/com/lx/algos/ml/optim/newton/BFGS.scala。

使用見：https://github.com/sloth2012/scalaML/blob/master/src/test/scala/com/lx/algos/ml/NewtonTest.scala。

小收穫（bug fix備忘）

修正版的DFP或者BFGS，其要求 ${{y_k}^T}{s_k}$ 正定，其中 $y_k=g_{k+1} - g_k$ 以及 ${s_k}={X_{k+1}}-{X_k}$ 。這裡的 $X$ 並非是輸入，而是權重。計算需要知道的是 $g_k$ 用一階原始梯度就行，不用加負號，之前加了負號後，導致迭代無法正定約束。因此之前的DFP演算法剖析中，那個正定放鬆約束可去除，即直接 ${{y_k}^T}{s_k}>0$ 。

數值實驗指出, BFGS演算法是最好的變尺度演算法, 當變數個數不超過100時, 通常BFGS法比共軛梯度法效果好.

參考文獻

牛頓法與擬牛頓法學習筆記（四）BFGS 演算法