直線探索法

「ニュートン」法のようなメソッドはステップを選択するが,そのステップは,関数についてのニュートンの二次モデルが,その関数を本当に反映している限りにおいてのみ妥当である.直線探索法の考えは,以下のような最小化の一次元問題を解くことにより,選ばれたステップの方向を使い長さを制御するというものである.

ここで は位置 から選ばれた探索方向である.

上記の関係が成り立つので,勾配が計算できれば事実上導関数を使った一次元の探索ができる.

一般に,有効な直線探索法は の方向のみを見る.妥当なメソッドは探索方向が で表される降下方向であることを保証すべきだからである.

探索方向が厳密に正しい方向であることは滅多にないので, の現実な最小値を求めることは一般にそれほど努力に値するものではない.たいていは近付くだけで十分である.

進展を測る条件は候補 についてのArmijoすなわち十分な降下条件と呼ばれる.

この条件でメソッドが収束することがよくあるが,メソッドによってはArmijoだけでは滑らかな関数の収束は保証できないこともある.以下のように曲率条件を加えるてみる.

すると,多くのメソッドが滑らかな関数について収束することが証明できる.これらの条件は文字列Wolfe条件として知られている.パラメータ "DecreaseFactor"->μ オプションと"CurvatureFactor"->η オプションで制御することができる.

"CurvatureFactor"->η のデフォルト値は である.しかし,Method->"ConjugateGradient"のときは例外で,アルゴリズムが厳密な直線探索に近いほどうまくいくので,が使われる. が小さいほど厳密な直線探索に近くなる.

二次元での反復探索を表すグラフを見ると,評価が直線探索の方向に沿って広がっているのに気が付く.一般に,条件を満足する点は,数回の反復で求められる.しかし,直線探索は常に条件を満足する点を見付けられる訳ではない.たいていの場合,条件が満たせるほど近くで点を計算するには,精度が不十分であるためである.また,完全には滑らかではない関数,あるいは最小値の近傍を極めてゆっくり変化する関数の場合も,条件を満足する点が見付からないことがある.

いくつかのユーティリティ関数を含むパッケージをロードする.
In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

プロットからも分かるように,関数における実際の相違は,この点近くでの評価による相違に比べると無視できるほどなので,これでは問題に直面する.

In[24]:=
Click for copyable input
Out[24]=

関数の小さな変化がもっと重要なものとなるように,定数から引き算することも,役に立つことがある.

In[18]:=
Click for copyable input
Out[18]=

しかしこの場合,プロットからも分かるように,0付近で関数にかなり雑音があるので,近似はほんの少し近付くに過ぎない.

In[19]:=
Click for copyable input
Out[19]=

このように,正しい値のゼロに近付くほど,より正確に関数を計算するために,より高い精度が必要になる.

問題によっては,特に根または極小値から離れたところから始めた場合は,ステップを制限した方がよいかもしれない.このためには,直線探索法ではメソッドオプションを使う.そのデフォルト値は探索が制御できなくなるのを防ぎ,同時に,必要に応じて大きなステップを使った探索を妨げないようになっている.

以下は,ヤコビ行列(導関数)がほぼ特異行列になっている位置が初期値であるために,ニュートンステップが非常に大きくなっている例である.
In[3]:=
Click for copyable input
Out[3]=
次も同じ例であるが,刻み幅をもっと大胆に制限している.こうすると初期条件近くの根が求まる.
In[4]:=
Click for copyable input
Out[4]=

オプションを小さく設定し過ぎないように注意する必要がある.小さくし過ぎると,特に最小値や根がゼロ近くにある場合,収束に影響が出る.

次の表は直線探索法を制御するために使えるオプションのまとめである.

オプション名
デフォルト値
"Method"Automatic直線探索を実行するメソッド.Automaticのいずれか
"CurvatureFactor"AutomaticWolfe条件における0と1の間の因子 の値が小さいほど,直線探索の結果が正確になる
"DecreaseFactor"1/10000Wolfe条件における0と の間の因子
"MaxRelativeStepSize"10現行探索点のノルムと相対的に取られる最大ステップ.正の数を取り,制限がない場合はを取る

のメソッドオプション

以下のセクションではWolfram言語に実装されている3つの直線探索法について説明する.比較はRosenbrock関数を用いて行う.

狭く曲がった谷を持つ古典的な Rosenbrock関数を設定するために,制約条件のない問題のためのパッケージを使う.
In[5]:=
Click for copyable input
Out[5]=

MoreThuente法

FindMinimumFindMaximumFindFitで使っているデフォルトの直線探索法は[MT94]でMoreとThuenteによって説明されている.この方法は,囲い込み法と二次および三次の補間法を使って降下条件と曲率条件の両方を満足する点を探そうとする.

これはニュートン法をデフォルトの直線探索パラメータで使って実行したステップと評価を示している.赤と緑だけの点は,関数と勾配が直線探索で評価されたが,ステップが取れるほどにはWolfe条件が満足されなかった点である.
In[10]:=
Click for copyable input

Out[10]=

関数と勾配のみが評価される点は,両方の条件を満足しなかった直線探索で試みられる点である.で制限されていない限り,直線探索は常にフルステップの長さ()から始まるので,フル(この場合はニュートン)ステップが直線探索の基準を満たせば,これが採用され,最小値近くにおける完全な収束率を保証する.

曲率の減少は,直線探索が厳密な最小値に近付いて終わったことを意味する.曲率が減少すると,ニュートン法で取られるステップ数が減るが,関数と勾配の合計評価回数は増える.

これは,デフォルトよりも小さい直線探索パラメータで,曲率因子を持つニュートン法を使ったステップと評価を示している.赤と緑だけの点は,関数と勾配が直線探索法で評価されたが,ステップが取れるほどにはWolfe条件が満足されなかった点である.
In[31]:=
Click for copyable input
Out[31]=

この例はより厳密な直線探索が必ずしもよい結果を生む訳ではないことの理由を示している.直線探索が狭い谷の底にステップを取ると,ニュートンステップは曲率を見ずに(谷の曲率は二次を超えている)谷に沿って動くので,ニュートンステップは,たとえ方向はよくとも,結果として長過ぎることになる.一方で,共役勾配法のようにメソッドによっては,収束を改善するためによりよい直線探索法が必要なものもある.

バックトラック法

これは,与えられた刻み幅で始め,刻み幅0に向けて後戻りし,十分な減少条件が見付かったところで止まる単純な直線探索である.一般的にいって,バックトラック法だけでは,たとえ洗練された関数でも曲率条件が満たせる保証はないので,メソッドの収束特性は保証されない.しかし,バックトラック直線探索法は各点で勾配を評価する必要がないので,勾配評価が相対的に高くつくのであれば,これを選ぶのがよいかもしれない.メリット関数の勾配評価には比較的コストの高いヤコビ行列の評価が含まれているので,FindRootの直線探索にはデフォルトでこのメソッドが使われている.

In[32]:=
Click for copyable input
Out[32]=

各バックトラックのステップは,多項式の補間を行い補間式の最小点を見付けることである.点 はそれが から までの間にある限り使われる.ここで はパラメータ の直前の値でありである.デフォルトにより, だが,メソッドオプションのを使えばこれを制御することができる.因数に単一の値を与えると となり,補間は行われない.値1/2により2等分となる.

この例では,比較的大きなバックトラック因子の影響が極めて明らかである.
In[33]:=
Click for copyable input
Out[33]=
オプション名
デフォルト値
"BacktrackFactors"{1/10, 1/2}試みられたバックトラックのステップ間の長さが減少しなければならないだけの最大因子と最小因子を決定する

直線探索Method->"Backtracking"のメソッドオプション

ブレント法

このメソッドは直線探索に,導関数を用いない1変量のブレント法[Br02]使う.これは,減少因子や曲率には関係なく,許容範囲内で の最小値を求めようとする.実際のところ,これには2つの段階がある.まず,これは根を囲い込もうとする.次に「ブレント」の補間法と黄金分割法を結合したものを使って最小値を求めようとする.この直線探索の利点は,このメソッドは最小値を囲い込もうとして両方向を見るため,他の2つのメソッドとは違ってステップが降下方向ではなくてもよい点である.このため,このメソッドは導関数を用いない「主軸」法に非常に適している.この直線探索法の欠点は,一般に多くの関数評価を使う点で,他の2つのメソッドに比べて効率面で劣る.

次の例は直線探索にブレント法を用いた際の効果を示している.この方法は根を囲い込む段階で, の負の値を用いることができる.この例ではニュートンステップの数は比較的少ないが,関数評価の総数は他の直線探索法に比べてはるかに多くなっている.
In[34]:=
Click for copyable input
Out[34]=