準ニュートン法

準ニュートン法とは

準ニュートン法（英: quasi-Newton method）は、非線形連立方程式の解や、連続最適化問題における関数の極値（最大値または最小値）を効率的に見つけ出すためのアルゴリズムです。この方法は、ニュートン法をベースにしていますが、ニュートン法とは異なり、ヘッセ行列を直接計算する必要がないという特徴があります。これにより、特に高次元の問題において計算コストを大幅に削減することが可能になります。

ニュートン法との比較

ニュートン法では、最適解の近傍で関数を二次関数で近似し、その一階および二階の導関数（勾配ベクトルとヘッセ行列）を解の探索に用います。しかし、高次元空間で定義された関数に対しては、ヘッセ行列の計算が非常に複雑になり、計算コストが大きくなるという問題がありました。準ニュートン法は、この問題を解決するために、ヘッセ行列を直接計算する代わりに、最適化の反復計算過程で得られる勾配ベクトルを用いてヘッセ行列を近似します。

準ニュートン法の概要

準ニュートン法は、多次元関数の零点を探索するアルゴリズムであるセカント法（割線法）を一般化したものと捉えることができます。多次元問題においては、セカント方程式が一意に定まらないため、準ニュートン法では近似の制約を設け、現在のヘッセ行列の推定値を低ランク行列成分を用いて更新します。

歴史的背景

最初の準ニュートン法のアルゴリズムは、物理学者のW.C. Davidonによって提案されました。彼の提案した方法は、後にDFP (Davidon-Fletcher-Powell) 法として知られるようになりましたが、1970年代後半に登場したより効率的なBFGS法（Broyden–Fletcher–Goldfarb–Shanno algorithm）の登場により、現在ではあまり用いられていません。現在、最も一般的に用いられている準ニュートン法のアルゴリズムには、SR1法（対称ランクワン法）、BHHH法、そしてBFGS法があります。また、大規模問題に対応させるための手法として、記憶制限準ニュートン法が提案されており、特にL-BFGS法が広く利用されています。

準ニュートン法の利点

準ニュートン法の最大の利点は、ヘッセ行列の逆行列を直接計算する必要がないという点です。ニュートン法や内点法などのアルゴリズムでは、ヘッセ行列の逆行列の計算が計算のボトルネックとなることが多いですが、準ニュートン法ではヘッセ行列の逆行列を直接近似することで、計算コストを大幅に削減することができます。

準ニュートン法の手法

準ニュートン法は、ニュートン法と同様に、関数の解を求めるために二次の近似を用います。関数 f(x) の二階のテイラー展開は以下のようになります。

math
f({oldsymbol x}_{k} + \Delta {oldsymbol x}) \approx f({oldsymbol x}_{k}) +
abla f({oldsymbol x}_{k})^{\intercal} \Delta {oldsymbol x} + \frac{1}{2} \Delta {oldsymbol x}^{\intercal} {\boldsymbol B} \Delta {\boldsymbol x}

ここで、∇f は勾配を、B はヘッセ行列の近似を表します。勾配∇fは、以下のように近似されます。

math

abla f({\boldsymbol x}_{k} + \Delta {\boldsymbol x}) \approx
abla f({\boldsymbol x}_{k}) + {\boldsymbol B} \Delta {\boldsymbol x}

この勾配が0になると仮定すると、ニュートンステップは以下の式で計算されます。

math
\Delta {\boldsymbol x} = -{\boldsymbol B}^{-1}
abla f({\boldsymbol x}_{k})

ヘッセ行列の近似Bは、以下のセカント方程式を満たすように更新されます。

math

abla f({\boldsymbol x}_{k} + \Delta {\boldsymbol x}) =
abla f({\boldsymbol x}_{k}) + {\boldsymbol B} \Delta {\boldsymbol x}

このセカント方程式は、多次元空間で定義された関数に対しては劣決定問題となります。準ニュートン法では、この問題を解決するために、様々な方法でBを更新します。多くの場合、Bは対称行列であると仮定し、以下の式を満たすように更新されます。

math
{\boldsymbol B}_{k+1} = \arg \min_{\boldsymbol B} \|{\boldsymbol B} - {\boldsymbol B}_{k}\|_{\boldsymbol V}

ここで、Vは正定値行列を表します。近似ヘッセ行列の初期値としては、単位行列などが用いられます。最適化の解 xk は、近似によって得られた Bk を用いたニュートンステップによって更新されます。具体的なアルゴリズムは以下の通りです。

1. ニュートンステップを計算

math
\Delta {\boldsymbol x}_{k} = -\alpha {\boldsymbol B}_{k}^{-1}
abla f({\boldsymbol x}_{k})

2. 解を更新

math
{\boldsymbol x}_{k+1} = {\boldsymbol x}_{k} + \Delta {\boldsymbol x}_{k}

3. 新しい点での勾配を計算

math

abla f({\boldsymbol x}_{k+1})

4. 勾配の変化を計算

math
{\boldsymbol y}_{k} =
abla f({\boldsymbol x}_{k+1}) -
abla f({\boldsymbol x}_{k})

5. yk を用いてヘッセ行列の逆行列を直接近似する。近似の式は各手法ごとに異なる。

実装

準ニュートン法は、現在広く利用されている最適化アルゴリズムであり、多くのプログラミング言語で実装されています。

NAG数値計算ライブラリには、準ニュートン法を用いた関数の最大化・最小化アルゴリズムが実装されています。
PythonのライブラリであるSciPyでは、scipy.optimize.minimize のデフォルトがBFGS法です。
GNU Octaveでは、関数'funcmin'においてBFGS法が用いられています。
MATLABのOptimization Toolboxにある関数fminuncでもBFGS法が実装されています。
MathematicaやRにも、一般的な関数の最適化法としてBFGS法が実装されています。

まとめ

準ニュートン法は、特に高次元の最適化問題において、効率的かつ安定した解を得るための強力なツールです。ヘッセ行列の直接計算を避けることで計算コストを削減しつつ、ニュートン法と同等の収束性を示すことができるため、多くの分野で広く利用されています。

準ニュートン法