信頼領域

信頼領域法とは

数理最適化において、信頼領域法は、目的関数を近似するモデル関数（多くの場合、二次関数）が有効であるとみなされる領域を指します。この領域内でモデル関数による近似が十分な精度を持つならば、信頼領域を拡大して反復を継続し、逆に近似の精度が不十分な場合は、信頼領域を縮小して再度最適化を行います。

信頼領域の評価

近似の精度を評価するために、モデル関数から期待される改善量と、実際の目的関数で観測された改善量との比率を用います。この比率をあらかじめ設定したしきい値と比較することで、信頼領域を拡大するか縮小するかを決定します。モデル関数は、妥当な近似値を与える領域内でのみ「信頼」できるという考え方が、この手法の根幹にあります。

直線探索法との比較

信頼領域法は、ある意味で直線探索法と双対の関係にあります。信頼領域法では、まずステップサイズ（信頼領域のサイズ）を決定し、次にステップの方向を決定します。一方、直線探索法では、まずステップの方向を決定し、その後にステップサイズを決定します。このアプローチの違いが、両手法の特性を分けています。

信頼領域法の歴史

信頼領域法の背後にある概念には、様々な名前が存在します。信頼領域という用語が最初に用いられたのは、Sorensen（1982）による研究とされています。また、教科書として有名なFletcher（1980）では、これらのアルゴリズムを制限ステップ法と呼んでいます。さらに、この方法に関する初期の基礎研究であるGoldfeld, Quandt & Trotter（1966）では、二次山登り法という名称で言及されています。

レーベンバーグ・マルカート法を例にした詳細

ここでは、レーベンバーグ・マルカート法を例に、信頼領域法の具体的な適用方法を説明します。この手法では、目的関数を二次曲面で反復的に近似し、線形ソルバーを用いて推定値を更新します。初期推定値が最適値から大きく離れている場合、そのままでは収束がうまくいかない可能性があるため、各ステップを制限して「行き過ぎ」を防ぎます。

具体的には、以下のような連立一次方程式を解く代わりに、

math
A\Delta x = b


次のような式を解きます。

math
(A + \lambda \operatorname{diag}(A))\Delta x = b


ここで、`diag(A)`はAと同じ対角成分を持つ対角行列であり、`λ`は信頼領域のサイズを制御するパラメータです。幾何学的には、この変更は`\Delta x = 0`を中心とする放物面を加えることに相当し、ステップサイズを小さく抑える効果があります。


推定値の発散を防ぎつつ、迅速に解へ収束させるためには、信頼領域のサイズ(`λ`)を適切に変更することが重要です。真の減少量`\Delta f_{\text{actual}}`は、以下の式で評価されます。

math
\Delta f_{\text{actual}} = f(x) - f(x + \Delta x)


この値と、減衰二次近似された目的関数から予測される減少量`\Delta f_{\text{pred}}`との比率を比較します。

math
\frac{\Delta f_{\text{pred}}}{\Delta f_{\text{actual}}}


通常、`\Delta f_{\text{pred}}`は`\Delta f_{\text{actual}}`よりもわずかに小さくなると期待され、この比率は0.25から0.5の範囲に収まることが理想的です。比率が0.5を超える場合は、減少量が過剰であるとみなし、信頼領域を拡大（`λ`を減少）して次の反復を行います。逆に、比率が0.25よりも小さい場合は、近似関数と真の関数との乖離が大きいと判断し、信頼領域を縮小（`λ`を増加）して次の反復を行います。

このように、信頼領域法はモデル関数の信頼度を評価し、その結果に基づいて最適化のステップを調整することで、効率的な最適化を実現します。

参考文献

Kranf site: Trust Region Algorithms
Trust-region methods

関連項目

* ドッグレッグ法

もう一度検索