非線形共役勾配法とは？意味をやさしく解説

非線形共役勾配法

数理最適化における非線形共役勾配法は、非線形最適化問題を解くためのアルゴリズムです。この方法は、線形共役勾配法を非線形問題へと拡張したものであり、関数の勾配情報のみを用いて効率的に極小値を探索します。特に、目的関数のヘッセ行列の計算が困難な場合や、高次元の問題に対して有効な手法です。

原理

非線形共役勾配法は、目的関数が極小点の近傍で2次関数的に振る舞う、すなわち極小点で2階微分可能であり、かつ2階微分が非特異である場合に適用できます。基本的な考え方は、現在の探索点における勾配の逆方向（最急降下方向）に進みながら、過去の探索方向の情報を利用して、より効率的な探索方向を決定することです。

アルゴリズム

1. 初期化:
- 初期点 x₀ を設定します。
- 初期探索方向 s₀ を最急降下方向 -∇f(x₀) とします。

2. 反復:
各反復 n において、以下の手順を繰り返します。

a. 最急降下方向の計算:
- 現在の点 xₙ における最急降下方向 Δxₙ = -∇f(xₙ) を計算します。

b. βₙ の算出:
- 次の探索方向を決定するための係数 βₙ を計算します。βₙ の計算方法にはいくつかのバリエーションがあり、代表的なものとして、Fletcher-Reeves、Polak-Ribière、Hestenes-Stiefel、Dai-Yuan の公式があります。

c. 共役方向の計算:
- 共役方向 sₙ = Δxₙ + βₙsₙ₋₁ を計算します。

d. ステップサイズの決定:
- 直線探索を用いて、目的関数 f(xₙ + αsₙ) を最小化するステップサイズ αₙ を求めます。

e. 位置の更新:
- 次の探索点 xₙ₊₁ = xₙ + αₙsₙ に更新します。

3. 収束判定:
- 目的関数の変化が十分に小さい、または反復回数が最大値に達した場合、アルゴリズムを終了します。

βₙ の算出方法

βₙ の算出には、以下の4つの有名な公式が用いられます。これらの公式は、2次関数に対しては同一の結果を与えますが、非線形最適化問題では異なる挙動を示すため、問題に応じて使い分けられます。

1. Fletcher-Reeves (FR) 公式:

βₙᶠᴿ = (ΔxₙᵀΔxₙ) / (Δxₙ₋₁ᵀΔxₙ₋₁)

2. Polak-Ribière (PR) 公式:

βₙᴾᴿ = (Δxₙᵀ(Δxₙ - Δxₙ₋₁)) / (Δxₙ₋₁ᵀΔxₙ₋₁)

3. Hestenes-Stiefel (HS) 公式:

βₙᴴˢ = - (Δxₙᵀ(Δxₙ - Δxₙ₋₁)) / (sₙ₋₁ᵀ(Δxₙ - Δxₙ₋₁))

4. Dai-Yuan (DY) 公式:

βₙᴰʸ = - (ΔxₙᵀΔxₙ) / (sₙ₋₁ᵀ(Δxₙ - Δxₙ₋₁))

実際には、β = max{0, βᴾᴿ} のように選ぶことで、自動的に探索方向のリセットが行われるため、この方法が広く用いられています。

特徴

- メリット:

- ヘッセ行列を必要としないため、計算コストが低い。
- 高次元問題にも適用可能。
- 最急降下法と比較して収束が速い。
- 狭い谷のような形状の目的関数に対しても、効率的に最適化を進めることができる。

- デメリット:

- 非線形性が強い問題では、収束が遅くなる可能性がある。
- 探索方向のリセットが必要な場合がある。

ニュートン法との比較

ニュートン法や準ニュートン法は、ヘッセ行列を利用してより迅速に収束する可能性がありますが、ヘッセ行列の計算や格納に大きな計算コストやメモリが必要となります。一方、非線形共役勾配法は、ヘッセ行列を必要としないため、これらの問題を回避しつつ、効率的な最適化が可能です。

まとめ

非線形共役勾配法は、非線形最適化問題を解くための強力なツールであり、特に高次元問題やヘッセ行列の計算が困難な場合に有効です。適切なβの算出方法と探索方向のリセット戦略を選択することで、さまざまな問題に対して良好な結果を得ることができます。

非線形共役勾配法