2025.8.6 非線形共役勾配法

$ f(x)を$ N変数関数とする。

第１ステップ

１－１）$ \Delta x_0 = - \nabla_x f(x_0) ... $ x_0における$ fの勾配

１－２）直線探索により$ \alpha_0 = \argmin_\alpha f(x_0 + \alpha \Delta x_0)を決定する

１－３）$ x_1 = x_0 + \alpha_0 \Delta x_0 ... 勾配方向に$ xを更新

以降、$ n = 1,2,3,\ldots

２－１）$ \Delta x_n = -\nabla_x f(x_n) ... $ x_nにおける$ fの勾配

２－２）手法に応じて$ \beta_n = \max(0, \beta)を決定、ただし少なくとも$ N回毎に$ \beta=0とする。

２－３） $ s_n = \Delta x_n + \beta_n s_{n-1} ... 共役勾配の決定、前ステップの共役勾配を引き継いでいることに注意

２－４）直線探索により$ \alpha_n = \argmax_{\alpha} f(x_n + \alpha s_n)を決定

２－５）$ x_{n+1} = x_{n} + \alpha_n s_n ... 共役勾配方向に更新

$ \beta_n の決定方法

Fletcher–Reeves:

$ \frac{\Delta x_n^\top\Delta x_n}{\Delta x_{n-1}^\top\Delta x_{n-1}}

Polak–Ribière:

$ \frac{\Delta x_n^\top(\Delta x_n - \Delta x_{n-1})}{\Delta x_{n-1}^\top\Delta x_{n-1}}

Hestenes-Stiefe

$ - \frac{\Delta x_n^\top(\Delta x_n-\Delta x_{n-1})}{s_{n-1}^\top(\Delta x_n -\Delta x_{n-1})}

Dai-Yuan:

$ - \frac{\Delta x_n^\top\Delta x_n}{s_{n-1}^\top(\Delta x_n-\Delta x_{n-1})}

※ ヘッセ行列の計算を回避している