信頼領域

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

近似が十分がどうかはモデル関数から期待される改善と目的関数で観測された実際の改善との比により評価される。この比を単純にしきい値と比較した結果に基き信頼領域を拡大・縮小する。モデル関数は妥当な近似値を与える領域内でのみ「信頼」される。

信頼領域法はある意味で直線探索法と双対を成す。信頼領域法ではまずステップサイズ（信頼領域のサイズ）を選択し、次にステップ方向を選択するが、直線探索法ではまずステップ方向を選択し、次にステップサイズを選択する。

信頼領域法の背後にある考え方には、多くの名前がある。信頼領域という用語が使用されたのは、が最初とされる。人気のある教科書では、これらのアルゴリズムを制限ステップ法（）と呼んでいる。さらに、この方法に関する初期の基礎研究、では二次山登り法（）と呼ばれている。

 例 
レーベンバーグ・マーカート法は目的関数を二次曲面で反復的に近似し、線形ソルバーにより推定値を更新する。初期推定が最適から乖離している場合、これだけではうまく収束しない可能性があるため、本法では代わりに各ステップを制限し、「行き過ぎ」ないようにする。具体的には、 を  について解く代わりに、 を解く。ここで  は  と同じ対角をもつ対角行列、 は信頼領域のサイズを制御するパラメータである。幾何学的には上記変更はを中心とする放物面を加算したことに相当し、このためステップサイズが小さく抑えられる。

推定値の発散を防ぎ、かつ迅速に解に収束させるためには、いかに信頼領域のサイズ（）を変更するかが重要である。真の減少は  を所与として次のように評価される。



この値と、減衰二次近似された目的関数から予測される目的関数の減少  の値とを比較、具体的には両者の比  の値に応じて信頼領域のサイズを調整する。一般的に、は よりも若干小さいと期待され、この比は0.25から0.5の間の値をとることが期待される。比率が 0.5 を超える場合は、減衰しすぎと考え、信頼領域を拡大（ を減少）させ次の反復を行なう。比率が 0.25 より小さい場合は、真の関数が近似関数から「大きく」離れているため、信頼領域を縮小（ を増加）させ次の反復を行なう。

 参考文献 





 Andrew R. Conn, Nicholas I. M. Gould, Philippe L. Toint "Trust-Region Methods (MPS-SIAM Series on Optimization)".
 Byrd, R. H, R. B. Schnabel, and G. A. Schultz. "A trust region algorithm for nonlinearly constrained optimization", SIAM J. Numer. Anal., 24 (1987), pp. 1152–1170.
 Yuan, Y. "A review of trust region algorithms for optimization" in ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics, Edinburgh, 2000  Oxford University Press, USA.
 Yuan, Y. "Recent Advances in Trust Region Algorithms", Math. Program., 2015

 関連項目 
 ドッグレッグ法

 外部リンク 
 Kranf site: Trust Region Algorithms
 Trust-region methods

Category:最適化アルゴリズムとメソッド
Category:数学に関する記事