信頼領域法

信頼領域法は,現行の探索点付近の領域である.この領域では「極小値探索」の二次モデル

が正しいと「信頼されて」おり,この領域に収まるようにステップが選ばれる.信頼領域の大きさは,モデルが現実の関数評価とどれほど一致するかに基づいて,探索の過程で修正される.

非常に典型的な例では,信頼領域はとなるよう楕円となる. は対角スケーリング(しばしば近似ヘッセ行列の対角線から取られる)で,は信頼領域の半径である.この半径は各ステップごとに更新される.

二次モデルのみに基づいたステップだけが信頼領域内にあるときは,関数の値が小さくなっていくと仮定すると,そのステップが選ばれる.従って,「直線探索法」と同じように,刻み幅制御は二次モデルがよい状態である最小値近くのアルゴリズムの収束を妨げない.二次モデルに基づいたステップが信頼領域の外にある場合は,そのステップが信頼領域の境界上にある二次モデルの近似最小化になるような,信頼領域の境界までのステップのみが選ばれる.

一旦ステップ が選ばれると,関数は新しい点で評価され,実際の関数値と二次モデルで予測された値とが比較される.実際に計算されているのは実際の減少と予想された減少との割合である.

が1に近ければ,二次モデルの予想はきわめて正確で,領域を広げることができる.一方で, が小さすぎると,領域は小さくなる. が閾値 よりも小さい場合,このステップは拒絶され再計算される.この閾値はメソッドオプションの"AcceptableStepRatio"->η を使って制御できる.典型的な の値は,最小値に向かって進むステップが拒絶されるのを防ぐように,極めて小さくなっている.しかし,ある点における二次モデルを求めるのにかなりコストがかかるならば(例えばヘッセ行列の評価は比較的長時間かかる), の値を大きくすることでヘッセ行列の評価回数を減らすことはできるが,関数の評価回数は増えることがある.

信頼領域アルゴリズムの開始には,初期半径を決定しなければならない.デフォルトで,Wolfram言語は比較的ゆったりした相対刻み幅制限によって限定されたモデル(1)に基づいた刻み幅を用いる.しかし,これでは興味ある領域外に出てしまうこともある.そんなときは,オプションを使って初期半径を指定することができる.このオプションの名前にはScaledが含まれているが,これは信頼領域の半径は対角スケーリング を通して作用するもので,絶対刻み幅ではないからである.

いくつかのユーティリティ関数を含むパッケージをロードする.
In[1]:=
Click for copyable input
以下は,ニュートン法で信頼領域の刻み幅制御を用いて,Rosenbrock関数に似た関数の極小値を探索している間に取られたステップと行われた評価を示している.
In[2]:=
Click for copyable input
Out[2]=

探索範囲が広がり過ぎて関数の細かい構造がこのスケールからは読み取れなくなっているので,このプロットは極めて質が悪い.

次は同じ関数についてのステップと評価を示している.今回は制限された信頼領域の初期半径を使っている.前に比べ,探索範囲が初期条件に近い範囲に収まっていて狭い谷に沿っている.
In[3]:=
Click for copyable input
Out[3]=

任意のステップで となるように,オプション を使って,信頼領域の半径の全体的な最大範囲を設定することも可能である.

信頼領域法は,関数計算において数値的丸めを含む問題があるために滑らかではない関数を扱う際にも問題があることがある.関数が十分に滑らかでないと,信頼領域の半径がどんどん小さくなる.そして,結局のところ,半径が事実上ゼロになってしまう.

次はOptimization`UnconstrainedProblems`パッケージに含まれているフロイデンシュタイン・ロス(FreudensteinRoth)のテスト問題を,FindMinimumを使って解けるような形式で取り出す(「テスト問題」を参照).
In[4]:=
Click for copyable input
Out[4]=
次はデフォルトのメソッドを使って関数の極小値を求める.この場合のデフォルトメソッドは,関数が平方和なので(信頼領域の)LevenbergMarquardt法である.
In[5]:=
Click for copyable input
Out[5]=

このメッセージは,信頼領域の大きさが探索点との大きさとの比較で事実上ゼロになったので,取られたステップが無視できる程度の効果しかないことを意味している.注:プラットフォームによっては機械演算における微妙な違いによりメッセージが表示されないことがある.これは数値的な不確かさによってメッセージが出るためで,この数値的不確かさはプラットフォームによって異なる.

これは,求まった最終点で 方向に沿った変動関数のプロットを作成する.
In[6]:=
Click for copyable input
Out[6]=

一方向のプロットによって,何故これ以上の改善が望めないがよく分かる.LevenbergMarquardt法がこのような状況で問題に陥った理由のひとつは,最小値で剰余が非零であるために,収束が比較的遅いということである.「ニュートン」法では収束がより速く,完全な二次モデルによってよりうまく刻み幅が見積もれるので,FindMinimumでデフォルトの許容範囲が満足されていることがより確実になる.

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

次の表は信頼領域の刻み幅制御のオプションのまとめである.

オプション名
デフォルト値
"AcceptableStepRatio"1/10000予想に対する実際の減少が のとき,探索が計算されたステップに移動する閾値
"MaxScaledStepSize"すべてのステップについて信頼領域の大きさが となるような値
"StartingScaledStepSize"Automatic信頼領域の最初の大きさ

のメソッドオプション