 |
非線形共役勾配法
非線形共役勾配法の基礎は，実質的に線形共役勾配法を適用し，剰余を勾配で置き換えるものである．モデル二次関数は決して明示的には形成されないので，常に「直線探索法」と一緒に使われる．
最初の非線形共役勾配法はFletcherとReevesによって提唱された次のようなものである．ステップの方向 
が与えられると，直線探索を使って 
が成り立つ 
を求めて，次に以下
を計算する．
を求めるための直線探索は，強いWolfe条件を満たさなければならない．このことは，方向 
が確実に降下方向 [NW99]となるために必要である．
これに代る方法で，実際には大抵の場合で（常にではないが）これよりうまくいく方法は，PolaktとRibiereによるものである．ここでは式(2)が以下で置き換えられる．
式(3)では 
が負になることも可能である．そのような場合には，Mathematica が 
を使って変更されたアルゴリズムを使用する．Mathematica ではデフォルトの共役勾配法はPolak-Ribiereであるが，メソッドオプション
Method->{"ConjugateGradient", Method->"FletcherReeves"}.
を使ってFletcher-Reevesメソッドを選ぶこともできる．共役勾配法の利点は，大規模問題でも比較的少量のメモリしか使わず，数値線形代数は必要としないので，各ステップが非常に速いという点である．不利な点は一般に「ニュートン法」や「準ニュートン法」に比べて収束に時間がかるという点である．また，長さに対するステップのスケールが貧弱なので，「直線探索」アルゴリズムで許容し得るステップを求めようとするたびに必要な反復回数が多くなることがある．
| In[1]:= |
| In[2]:= |
| Out[2]= |  |
非線形共役勾配法における問題点のひとつは，いつ再スタートするかということである．探索が動くにつれて，関数の局所二次近似の性質が根本的に変化する可能性がある．このメソッドの局所的収束は，二次関数が一定となる線形共役勾配法の収束に依存している．n 変数の一定の二次関数と厳密な直線探索で，線形アルゴリズムが n 回以下の反復回数で収束する．再スタートする（
で最急降下ステップを取る）ことで，現行の探索点における局所二次モデルには無関係な前のステップからの情報を除去できることがしばしばある．例題を注意深く見ると，メソッドが再スタートされ，最急降下ステップが取られた点が分かる．ひとつのオプションとして k 回（ここで 
）の反復毎に再スタートするというものがある．これはメソッドオプションの"RestartIterations"->k で指定することができる．あるいは，下記のテスト
の結果，連続する勾配が十分に直角ではない場合に再スタートすることも可能である．閾値 
は0から1までの間である．これはメソッドオプションの"RestartThreshold"-> を使って指定することができる．
次の表は，共役勾配法で使うことができるオプションのまとめである．
オプション名 | デフォルト値 | |
| "Method" | "PolakRibiere" | 非線形共役勾配法は あるいは である |
| "RestartThreshold" | 1/10 | それ以下では再スタートする勾配直角の閾値 |
| "RestartIterations" | ∞ | 次の再スタートまでの反復回数 |
| "StepControl" | "LineSearch" |  でなければならないが，これを使って直線探索のオプションが指定できる |
Method->"ConjugateGradient"のメソッドオプション
Mathematica 4におけるFindMinimumのデフォルトオプションは，ほぼ厳密な直線探索を使う共役勾配法であった点に注意のこと．これはレガシーとして残っており，FindMinimumオプションのMethod->"Gradient"でアクセスすることができる．一般にこちらの方が新しいMethod->"ConjugateGradient"よりも関数や勾配の評価回数が多い．この新しい方でも，Mathematica が現在デフォルトで使うメソッドよりもはるかに多くのメソッドを使っている．
