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

記憶制限 BFGS アルゴリズム

以下に一般的な形式の問題を解くアルゴリズム [Byrd2015] を示します。

以下の項目を指定します。

• 開始点 x₀
• メモリー・パラメーター m
• 曲率推定計算の頻度 L
• ステップ長数列 α^k>0

k を 1 から nIterations まで反復します。

1. t = -1 を設定します。

2. 置換なしのインデックスのセット I = {i₁, i₂, ... , i_b}, 1 ≤ i_l < n, l ∈ {1, ..., b}, |I| = b = batchSize を選択します。

3. 次の項の勾配を計算します。
   

4. 次の場合に停止します。

   
   

5. x_k をインクリメントします。

   
   

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

6. L 反復の補正ペアを計算します。mod(k, L) = 0 の場合:

   1. t = t + 1 を設定します。

   2. t > 0 の場合:

      1. 置換なしのインデックスのセット I_H = {i₁, i₂, ... , i_bH}, 1 ≤ i_l < n, l ∈ {1, ..., b_H}, | I_H | = b_H = correctionPairBatchSize を選択します。

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

         
         

         ここで、

         
         

         
         

         は関数 F_i のヘッセ行列です。

      3. 補正ペア (s_t, y_t) を計算します。

         
         

         
         

結果は、ループ終了後の x_k の値です。

ヘッセ更新アルゴリズム

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

補正ペアのセットで以下の計算を行います。

1. H を設定します。

   
   

2. j を反復します。

   
   

   1. 
      

   2. BFGS (Broyden-Fletcher-Goldfarb-Shanno) 公式を適用します。

      
      

3. H を返します。