信頼領域のソースを表示

{{翻訳直後|[[:en:Special:Permalink/1082586778|en: Trust region]]|date=2022年9月}}

'''信頼領域'''（しんらいりょういき、{{Lang-en-short|trust region}}）は、[[数理最適化]]において[[目的関数]]を近似するモデル関数（多くの場合[[二次関数]]）が有効とみなされる領域をいう。目的関数のモデル関数による近似が信頼領域内で十分であるならば、信頼領域を拡大して[[反復法 (数値計算)|反復]]を継続し、逆に近似が不十分な場合、信頼領域を縮小して続行する。

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

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

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

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

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

: <math>\Delta f_\text{actual} = f(x) - f(x + \Delta x)</math>

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

== 参考文献 ==
{{refbegin}}
* {{Cite journal|last=Sorensen|first=D. C.|year=1982|title=Newton's Method with a Model Trust Region Modification|url=https://digital.library.unt.edu/ark:/67531/metadc283479/|journal=SIAM J. Numer. Anal.|volume=19|issue=2|pages=409–426|DOI=10.1137/0719026|ref=harv}}
* {{Cite book|first=Roger|last=Fletcher|chapter=Restricted Step Methods|title=Practical Methods of Optimization|publisher=Wiley|edition=Second|origyear=1980|year=1987|isbn=0-471-91547-5|ref={{sfnref|Fletcher|1980}}}}
* {{Cite journal|last=Goldfeld|first=Stephen M.|authorlink1=:en:Stephen_Goldfeld|last2=Quandt|first2=Richard E.|authorlink2=:en:Richard_E._Quandt|last3=Trotter|first3=Hale F.|authorlink3=:en:Hale_Trotter|year=1966|title=Maximization by Quadratic Hill-Climbing|journal=[[Econometrica]]|volume=34|issue=3|pages=541–551|DOI=10.2307/1909768|JSTOR=1909768|ref=harv}}
* {{Cite book|first=J. E., Jr.|last=Dennis|first2=Robert B.|last2=Schnabel|chapter=Globally Convergent Modifications of Newton's Method|title=Numerical Methods for Unconstrained Optimization and Nonlinear Equations|location=Englewood Cliffs|publisher=Prentice-Hall|year=1983|isbn=0-13-627216-9|pages=111–154}}
* Andrew R. Conn, Nicholas I. M. Gould, Philippe L. Toint "[https://books.google.com/books?id=5kNC4fqssYQC Trust-Region Methods (MPS-SIAM Series on Optimization)]".
* Byrd, R. H, R. B. Schnabel, and G. A. Schultz. "[http://epubs.siam.org/doi/abs/10.1137/0724076 A trust region algorithm for nonlinearly constrained optimization]", SIAM J. Numer. Anal., 24 (1987), pp.&nbsp;1152–1170.
* Yuan, Y. "[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.9964 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. "[https://link.springer.com/article/10.1007%2Fs10107-015-0893-2 Recent Advances in Trust Region Algorithms]", Math. Program., 2015
{{refend}}

== 関連項目 ==
* [[ドッグレッグ法]]

== 外部リンク ==
* [http://www.applied-mathematics.net/optimization/optimizationIntro.html Kranf site: Trust Region Algorithms]
* [https://optimization.mccormick.northwestern.edu/index.php/Trust-region_methods Trust-region methods]

{{最適化アルゴリズム}}

{{DEFAULTSORT:しんらいりよういきほう}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:数学に関する記事]]