信頼しんらい領域りょういき

数理すうり最適さいてき化かにおいて、信頼しんらい領域りょういき（しんらいりょういき、英えい: 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. https://digital.library.unt.edu/ark:/67531/metadc283479/. 
• 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

外部がいぶリンク

• Kranf site: Trust Region Algorithms
• Trust-region methods

関連かんれん項目こうもく

• ドッグレッグ法ほう