非線形共役勾配法のソースを表示

{{翻訳直後|[[:en:Special:Redirect/revision/877250373|Nonlinear conjugate gradient method]]|date=2019年1月}}

[[数理最適化]]において、'''非線形共役勾配法'''（ひせんけいきょうやくこうばいほう、{{Lang-en-short|nonlinear conjugate gradient method}}）とは[[非線形計画法|非線形最適化]]問題に[[共役勾配法]]を拡張したものをいう。

== 原理 ==
[[二次関数|2次関数]]

:: <math>\displaystyle f(x)=\|Ax-b\|^2</math>

の最小値問題は、次のように[[勾配 (ベクトル解析)|勾配]]が0となる点を得れば解ける。

:: <math>\nabla_x f=2 A^T(Ax-b)=0</math>.

線形共役勾配法は[[線形方程式]] <math>\displaystyle A^T Ax=A^T b</math> の求解に用いられるのに対して、非線形共役勾配法は、関数の[[極小値]]探索を[[勾配 (ベクトル解析)|勾配]]  <math>\nabla_x f</math>のみを用いて行う。この手法は、対象非線形関数が極小点近傍において近似的に2次関数的に振る舞う、すなわち極小点において2階微分可能でありかつ2階微分が非特異的である場合に適用可能である。

{{Mvar|N}} 変数関数 {{Math|''f''(''x'')}} が与えられたとき、その勾配 <math>\nabla_x f</math> はその関数を最も増大させる方向を示す。まずは、[[最急降下法]]と同じくその逆方向へと探索を行う。

:: <math>\Delta x_0=-\nabla_x f (x_0) </math>

この方向に直線探索を行うことにより{{mvar|f}} を最小とするようなステップ長 {{Mvar|α}} を求める。

:: <math>\displaystyle \alpha_0:= \arg \min_\alpha f(x_0+\alpha \Delta x_0)</math>
:: <math>\displaystyle x_1=x_0+\alpha_0 \Delta x_0</math>

このように最初のイテレーションで最急方向 <math>\Delta x_0</math> に降下した後は、以下の手順に従い、共役方向 <math>\displaystyle s_n</math> を計算してその方向へと降下する。ここで、<math>\displaystyle s_0=\Delta x_0</math> とする。

# 最急方向 <math>\Delta x_n=-\nabla_x f (x_n) </math> を算出
# 後述する式に従って <math>\displaystyle \beta_n</math> を算出
# 共役方向 <math>\displaystyle s_n=\Delta x_n+\beta_n s_{n-1}</math> を算出
# 直線探索 <math>\displaystyle \alpha_n=\arg \min_{\alpha} f(x_n+\alpha s_n)</math> を行う
# 位置を更新 <math>\displaystyle x_{n+1}=x_{n}+\alpha_{n} s_{n}</math>

純粋な二次関数では、{{Mvar|N}} 回反復すればかならず（丸め誤差を除いて）最小値に到達するが、非二次関数では収束はより遅くなる。後続の探索方向は共役性を失うため、最適化の進捗が止まる前に、少なくとも''Ｎ''回反復する毎に探索方向を最急降下方向にリセットする必要がある。しかし、反復する毎に毎回リセットを行ってしまうと、[[最急降下法]]と変わらなくなってしまう。このアルゴリズムは、方向リセットをした後（すなわち最急降下方向）でも進捗がないとき、または何らかの許容基準に達したときに最小値を見つけたとみなして停止する。

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

以下に示す4つの公式が {{Mvar|β<sub>n</sub>}} の算出方法として有名である。それぞれ、名前は開発者の名に因む。

* Fletcher–Reeves:<ref>R. Fletcher and C. M. Reeves, "Function minimization by conjugate gradients", Comput. J. 7
(1964), 149–154.</ref>

:: <math>\beta_{n}^{FR} = \frac{\Delta x_n^T \Delta x_n}
{\Delta x_{n-1}^T \Delta x_{n-1}}.
</math>

* Polak–Ribière:<ref>E. Polak and G. Ribière, "Note sur la convergence de directions conjugu´ee", Rev. Francaise
Informat Recherche Operationelle, 3e Ann´ee 16 (1969), 35–43.</ref>

:: <math>\beta_{n}^{PR} = \frac{\Delta x_n^T (\Delta x_n-\Delta x_{n-1})}
{\Delta x_{n-1}^T \Delta x_{n-1}}.
</math>

* Hestenes-Stiefel:<ref>M. R. Hestenes and E. Stiefel, "Methods of conjugate gradients for solving linear systems", J.
Research Nat. Bur. Standards 49 (1952), 409–436 (1953).</ref>

:: <math>\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})}.
</math>

* Dai–Yuan:<ref>Y.-H. Dai and Y. Yuan, "A nonlinear conjugate gradient method with a strong global convergence
property", SIAM J. Optim. 10 (1999), no. 1, 177–182.</ref>

:: <math>\beta_{n}^{DY} = -\frac{\Delta x_n^T \Delta x_n}
{s_{n-1}^T (\Delta x_n-\Delta x_{n-1})}
</math>

これらの公式は2次関数に対しては全て同一となるが、非線形最適化問題に際しては[[ヒューリスティクス]]もしくは好みにもとづいて選ばれる。<math>\displaystyle \beta=\max\{0, \beta^{PR}\}</math> のように選ぶと、自動的に降下方向のリセットも行われるため普及している<ref>J. R. Shewchuk, "[https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf An Introduction to the Conjugate Gradient Method Without the Agonizing Pain]", August 1994.</ref>。

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

== 関連項目 ==
* [[BFGS法]]
* [[共役勾配法]]
* [[L-BFGS法]]
* [[ネルダー–ミード法]]
* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.700.5917&rep=rep1&type=pdf MODIFIED FLETCHER-REEVES-TYPE]

== 脚注 ==
{{脚注ヘルプ}}
=== 出典 ===
{{Reflist|2}}

== 外部リンク ==
* [https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf An Introduction to the Conjugate Gradient Method Without the Agonizing Pain] by Jonathan Richard Shewchuk.
* [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.46.3325&rep=rep1&type=pdf A NONLINEAR CONJUGATE GRADIENT METHOD WITH A STRONG GLOBAL CONVERGENCE PROPERTY] by Y. H. DAI and Y. YUAN.
* [http://numerentur.org/gradiente-conjugado-no-lineal/ Different types of Nonlinear Conjugate Gradient] {{sp icon}}

{{最適化アルゴリズム}}

{{デフォルトソート:ひせんけいきようやくこうはいほう}}
[[Category:勾配法]]