信頼領域

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

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

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

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

例

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

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

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

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

参考文献

Sorensen, D. C. (1982). “Newton's Method with a Model Trust Region Modification”. SIAM J. Numer. Anal. 19 (2): 409–426. doi:10.1137/0719026.
Fletcher, Roger (1987) [1980]. “Restricted Step Methods”. Practical Methods of Optimization (Second ed.). Wiley. ISBN 0-471-91547-5
Goldfeld, Stephen M.; Quandt, Richard E.; Trotter, Hale F. (1966). “Maximization by Quadratic Hill-Climbing”. Econometrica 34 (3): 541–551. doi:10.2307/1909768. JSTOR 1909768.
Dennis, J. E., Jr.; Schnabel, Robert B. (1983). “Globally Convergent Modifications of Newton's Method”. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice-Hall. pp. 111–154. ISBN 0-13-627216-9
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

信頼領域

例

参考文献

外部リンク

関連項目