BFGS算法

佇數值優化中，Broyden–Fletcher–Goldfarb–Shanno（BFGS）算法是一種求解無約束非線性優化問題迵天代算法。佮相關的 Davidon–Fletcher–Powell 算法類似，BFGS 算法通過利用曲率信息對梯度進行預處理來確定下降方向。曲率信息若是通過維護一个使用廣義的割線法沓沓仔親像的關於損失函數的 Hessian 矩陣來得著。

算法

對起頭點 $ \ mathbf { x } _ { 零 } $ 佮初的 Hessian 矩陣 $ B _ { 零 } $，重複以下步數，$ \ mathbf { x } _ { k } $ 會收斂著優化問題的解說：

一 . 通過求解方程 $ B _ { k } \ mathbf { p } _ { k }=-\ nabla f ( \ mathbf { x } _ { k } ) $，得著降低的方向 $ \ mathbf { p } _ { k } $。二 . 佇咧 $ \ mathbf { p } _ { k } $ 方向上進行一維的優化（線搜索），揣著合適的步長 $ \ alpha _ { k } $。抑若這个搜查是完全的，著 $ \ alpha _ { k }=\ arg \ min f ( \ mathbf { x } _ { k } + \ alpha \ mathbf { p } _ { k } ) $。佇實際應用中，無完全的搜查一般就夠額矣，現此時只要求 $ \ alpha _ { k } $ 滿足 Wolfe 條件。三 . 令 $ \ mathbf { s } _ { k }=\ alpha _ { k } \ mathbf { p } _ { k } $，並且令 $ \ mathbf { x } _ { k + 一 }=\ mathbf { x } _ { k } + \ mathbf { s } _ { k } $。四 . $ \ mathbf { y } _ { k }={ \ nabla f ( \ mathbf { x } _ { k + 一 } )-\ nabla f ( \ mathbf { x } _ { k } ) } $。五 . $ B _ { k + 一 }=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 } } } $。六 .

$ f ( \ mathbf { x } ) $ 表示欲上細化的目標函數。會當通過檢查梯度的範數 $ | | \ nabla f ( \ mathbf { x } _ { k } ) | | $ 來判斷收斂性。若是 $ B _ { 零 } $ 初初化為 $ B _ { 零 }=I $，第一步欲等效佇梯度下降，毋過紲落來的步數會受著將近若像 Hessian 矩陣的 $ B _ { k } $ 調節。

拓展閱讀

梯度降落來
擬牛頓法

參考文獻