非線形共役勾配法

数理最適化において、非線形共役勾配法︵ひせんけいきょうやくこうばいほう、英: nonlinear conjugate gradient method︶とは非線形最適化問題に共役勾配法を拡張したものをいう。

原理

2次関数

${\displaystyle \displaystyle f($x)=\|Ax-b\|^{2}} $\displaystyle f(x)=\|Ax-b\|^{2}$
の最小値問題は、次のように勾配が0となる点を得れば解ける。

$\nabla _{x}f=2A^{T}(Ax-b)=0$$\nabla _{x}f=2A^{T}(Ax-b)=0$.

線形共役勾配法は線形方程式 $\displaystyle A^{T}Ax=A^{T}b$$\displaystyle A^{T}Ax=A^{T}b$の求解に用いられるのに対して、非線形共役勾配法は、関数の極小値探索を勾配 $\nabla _{x}f$$\nabla _{x}f$のみを用いて行う。この手法は、対象非線形関数が極小点近傍において近似的に2次関数的に振る舞う、すなわち極小点において2階微分可能でありかつ2階微分が非特異的である場合に適用可能である。

N 変数関数 f(x) が与えられたとき、その勾配 $\nabla _{x}f$$\nabla _{x}f$はその関数を最も増大させる方向を示す。まずは、最急降下法と同じくその逆方向へと探索を行う。

$\Delta x_{0}=-\nabla _{x}f(x_{0})$$\Delta x_{0}=-\nabla _{x}f(x_{0})$
この方向に直線探索を行うことによりf を最小とするようなステップ長 α を求める。

$\displaystyle \alpha _{0}:=\arg \min _{\alpha }f(x_{0}+\alpha \Delta x_{0})$$\displaystyle \alpha _{0}:=\arg \min _{\alpha }f(x_{0}+\alpha \Delta x_{0})$
$\displaystyle x_{1}=x_{0}+\alpha _{0}\Delta x_{0}$$\displaystyle x_{1}=x_{0}+\alpha _{0}\Delta x_{0}$
このように最初のイテレーションで最急方向 $\Delta x_{0}$$\Delta x_{0}$に降下した後は、以下の手順に従い、共役方向 $\displaystyle s_{n}$$\displaystyle s_{n}$を計算してその方向へと降下する。ここで、$\displaystyle s_{0}=\Delta x_{0}$$\displaystyle s_{0}=\Delta x_{0}$ とする。

(一)最急方向 $\Delta x_{n}=-\nabla _{x}f(x_{n})$$\Delta x_{n}=-\nabla _{x}f(x_{n})$を算出

(二)後述する式に従って $\displaystyle \beta _{n}$$\displaystyle \beta _{n}$を算出

(三)共役方向 $\displaystyle s_{n}=\Delta x_{n}+\beta _{n}s_{n-1}$$\displaystyle s_{n}=\Delta x_{n}+\beta _{n}s_{n-1}$を算出

(四)直線探索 $\displaystyle \alpha _{n}=\arg \min _{\alpha }f(x_{n}+\alpha s_{n})$$\displaystyle \alpha _{n}=\arg \min _{\alpha }f(x_{n}+\alpha s_{n})$を行う

(五)位置を更新 $\displaystyle x_{n+1}=x_{n}+\alpha _{n}s_{n}$$\displaystyle x_{n+1}=x_{n}+\alpha _{n}s_{n}$
純粋な二次関数では、N 回反復すればかならず︵丸め誤差を除いて︶最小値に到達するが、非二次関数では収束はより遅くなる。後続の探索方向は共役性を失うため、最適化の進捗が止まる前に、少なくともＮ回反復する毎に探索方向を最急降下方向にリセットする必要がある。しかし、反復する毎に毎回リセットを行ってしまうと、最急降下法と変わらなくなってしまう。このアルゴリズムは、方向リセットをした後︵すなわち最急降下方向︶でも進捗がないとき、または何らかの許容基準に達したときに最小値を見つけたとみなして停止する。

線形近似の範囲内ではパラメータ α と β は線形共役勾配法と同一となるが、直線探索を用いて算出する。共役勾配法は、最急降下法ではジグザグパターンに陥ってしまい収束が遅くなってしまうような、狭い︵ill-conditionな︶谷に沿って最適化を進めることができる。

以下に示す4つの公式が β_n の算出方法として有名である。それぞれ、名前は開発者の名に因む。

●Fletcher–Reeves:

$\beta _{n}^{FR}={\frac {\Delta x_{n}^{T}\Delta x_{n}}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.$$\beta _{n}^{FR}={\frac {\Delta x_{n}^{T}\Delta x_{n}}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.$
●Polak–Ribière:

$\beta _{n}^{PR}={\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.$$\beta _{n}^{PR}={\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.$
●Hestenes-Stiefel:

$\beta _{n}^{HS}=-{\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}.$$\beta _{n}^{HS}=-{\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}.$
●Dai–Yuan:

$\beta _{n}^{DY}=-{\frac {\Delta x_{n}^{T}\Delta x_{n}}{s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}$$\beta _{n}^{DY}=-{\frac {\Delta x_{n}^{T}\Delta x_{n}}{s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}$
これらの公式は2次関数に対しては全て同一となるが、非線形最適化問題に際してはヒューリスティクスもしくは好みにもとづいて選ばれる。$\displaystyle \beta =\max\{0,\beta ^{PR}\}$$\displaystyle \beta =\max\{0,\beta ^{PR}\}$ のように選ぶと、自動的に降下方向のリセットも行われるため普及している。

ニュートン法に基くアルゴリズムはより急速に収束する可能性がある。それらのアルゴリズムは勾配とヘッセ行列の厳密値︵ニュートン法の場合︶もしくは推定値︵準ニュートン法の場合︶を用いてステップ方向とステップ長の両方を線形方程式系を解いて求める。しかし、高次元の問題においてはヘッセ行列の厳密値の計算は実行不可能なほど計算コストが高く、また推定値でさえその格納には $O(N^{2})$$O(N^{2})$のメモリを要するため格納すら難しい場合がある。

関連項目

• BFGS法
• 共役勾配法
• L-BFGS法
• ネルダー–ミード法
• MODIFIED FLETCHER-REEVES-TYPE

外部リンク

• An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Richard Shewchuk.
• A NONLINEAR CONJUGATE GRADIENT METHOD WITH A STRONG GLOBAL CONVERGENCE PROPERTY by Y. H. DAI and Y. YUAN.
• Different types of Nonlinear Conjugate Gradient （スペイン語）