主軸法

「ガウス・ニュートン法」「共役勾配法」には導関数が用いられる.Wolfram言語が記号的な導関数を計算できないときは,有限差分が使われる.有限差分を用いて導関数を計算するのは,場合によっては非常に大きなコストがかかり,導関数の妥当性にも影響し,究極的には最小値へどれほどまで近似できるかに影響する.記号的な導関数が使えない関数については,近似モデルが関数の評価による値のみを使って構築される,導関数を使わないアルゴリズムを使うこともできる.

Wolfram言語では,導関数を使わないアルゴリズムとしてブレント[Br02]の主軸法を使う. 変数の問題では,一連の探索方向 と点 を取る.から 方向に沿って を最小化する点だとする(つまり,から「直線探索」を行う).次に で置換する.最後に,で置換する.理想的には,新たな反復ができるように,新たな は線形に独立でなければならないが,実際にはそうはならない.ブレントのアルゴリズムでは,局所的な二次形式の主方向に を再調整するのに,行列 の特異値分解が使われる(固有分解を行ってもよいが,ブラントは特異値分解の方が有効であることを示している).新たに獲得した の集合を使って,もう一度反復を行うことができる.

ベクトル の大きさを決定するのに使うため,このメソッドでは,それぞれの変数に2つの異なる初期条件が必要である.事実,各変数について2つの初期条件を指定する場合はいつも,FindMinimumFindMaximumFindFitはデフォルトで主軸法を使う.

いくつかのユーティリティ関数を含むパッケージをロードする.
In[1]:=
Click for copyable input
これは関数の極小値を求めるためのFindMinimumの探索パスと関数の評価を示している.
In[2]:=
Click for copyable input
Out[2]=

導関数を使わない直線探索アルゴリズムは極めて多数の関数評価を必要とするため,この探索アルゴリズムの基本はこのプロットからよく分かる.まず, 方向に直線探索が行われる.次に,その点から 方向への直線探索が行われ,ステップの方向が決定される.一旦ステップが取られると,ベクトル は局所的な二次形式近似の主方向に適切に再調整され,次のステップが同じように計算される.

このアルゴリズムは収束率という点で効果的である.これはステップについて二次収束するからである.しかし,関数評価の点から見ると,導関数を使わない直線探索が必要となるため極めて高くなっている.直線探索に与えられる方向(特に最初で)は,必ずしも降下方向である必要はないので,直線探索は両方向の探索が行えなければならないという点に注意のこと.多変数の問題では,全方向での別個の直線探索は非常に高くつく.そのため,この方法は変数が多過ぎない問題に適している.