準ニュートン法

準ニュートン法にはいろいろな変形がある．そのすべてに共通する概念は，下の二次モデル

の行列 が，関数から構築されたヘッセ行列式の近似，および，以前に取られたステップの一部あるいはすべての勾配値に基づくというものである．

上記の経路でまず目に付くのはこれが間違った方向に向かって始まっている点である．最初のステップではすべての方法がその勾配に従わなければならないために，最急降下のこの方向が選ばれたのである．しかし，後続のステップでは，ヘッセ行列の近似モデルの構築のために取られたステップにおける関数値および勾配値からの情報が組込まれている．

Mathematica は，BFGS (Broyden-Fletcher-Goldfarb-Shanno)更新法を使い，大規模システムでは，メモリ節約型のL-BFGS法を使う．L-BFGS法ではモデル は明示的には保存されず，過去のステップから保存された勾配とステップ方向によって が計算される．

BFGSメソッドは，各ステップでヘッセ行列の近似 を形成する代りに，回の操作で 変数の問題の系 [DS96]が解けるように，= を計算するコレスキー因子 を実装している．

大規模で疎な問題の場合，BFGS法には少々問題がある．一般にコレスキー因子（あるいはヘッセ行列の近似 またはその逆行列）は密なので，のメモリと操作の必要条件が，疎性を利用するアルゴリズムに比べて抑制的になるからである．L-BFGSアルゴリズム[NW99]は，最後の ステップに基づいてヘッセ行列の逆行列の近似行列を形成し，保存する．ヘッセ行列の近似はそれほど完全ではないかもしれないが， 変数の問題の操作メモリと順序は に限られている．Mathematica 5では，250以上の変数を持つ問題になると自動的にアルゴリズムがL-BFGSに切り換えられる．これは，メソッドオプションの"StepMemory"->m を使って制御することができる．m=∞のときは，完全なBFGSメソッドが常に使われる． の適切な値を選択することで，収束速度と各ステップでの作業量との間にトレードオフの関係が生じる．m<3の場合は，「共役勾配」アルゴリズムを使った方が結果がよくなることが多い．

準ニュートン法は，一般に極めて速く，記号計算と数値評価の両方でかなり高くつくヘッセ行列の計算を必要としないので，Mathematica はデフォルトでこのメソッドを使う．準ニュートン法で適切な「直線探索」を行うと，ヘッセ行列が正定値行列となる極小値に超直線的に収束する[NW99] ．つまり，以下の式

が成り立つ．言い換えれば，ステップがどんどん小さくなっている．しかし，非常に高精度の場合は，「ニュートン」法の -二次収束率とは比較にならない．

ニュートン法は二次収束率が高いので，同じ桁数をより少ないステップで10倍速く見付けることができる．しかし，準ニュートン法は誤差の割合が明かにゼロに近付いているために，収束がなおも超線形的なのが分かる．

次の表は準ニュートン法で使えるオプションのまとめである．