インテル® DAAL 2018 デベロッパー・ガイド

記憶制限 BFGS (Broyden-Fletcher-Goldfarb-Shanno) アルゴリズム

記憶制限 BFGS (Broyden-Fletcher-Goldfarb-Shanno) アルゴリズム [Byrd2015] は、反復ソルバーのアルゴリズム・フレームワークに従います。アルゴリズム固有の変換 T および組込みパラメーターのセット St は、メモリー・パラメーター m、曲率推定計算の頻度 L、ステップ長数列 αt > 0 で、次のように定義されます。

変換

:



ここで、H は、ヘッセ更新アルゴリズムにより m 補正ペアから計算された逆ヘッセ行列の近似です。

組込みパラメーター

記憶制限 BFGS アルゴリズムでは、組込みパラメーターのセット St は次の項目を含みます。

組込みパラメーター (si, yi ) の定義および更新フローは次のとおりです。インデックスはメインループの最初の 2L-1 反復ではゼロのままです。反復 2L から、アルゴリズムはメインループの L 反復ごとに次のステップを実行します。

  1. k:=k+1。

  2. 置換なしのインデックスのセット IH = {i1, i2, ..., ibH}, 1 ≤ il < n, l ∈ {1, ..., bH}, | IH | = bH = correctionPairBatchSize を選択します。

  3. サブサンプリングされたヘッセ行列を計算します。



    その項のヘッセ行列を使用して目的関数の で計算を行います。


  4. 補正ペア (sk, yk) を計算します。

  • 組込みパラメーターのセット Sk はメジャーループの L 反復ごとに一回更新されます。L の倍数の反復間では変更されません。

  • 補正ペアを格納する循環バッファー。アルゴリズムは 1 つずつペアをバッファーに格納します。バッファーが一杯になると、初めに戻り、前の補正ペアを上書きします。

ヘッセ更新アルゴリズム

このアルゴリズムは、補正ペアのセットから逆ヘッセ行列の近似を計算します [Byrd2015]。

補正ペアのセット (sj, yj ), j = k - min (k, m) +1, ..., k で以下の計算を行います。

  1. を設定します。

  2. jk - min (k, m)+1 から k まで反復します。





  3. H を返します。