信頼領域のソースを表示

{{脚注の不足|date=2017年11月6日 (月) 11:33 (UTC)}}
{{翻訳直後|1=[https://en.wikipedia.org/w/index.php?title=Trust_region&oldid=684899212 英語版 Trust region 13:32, 9 October 2015]|date=2015年10月}}
{{Rough translation|en}}
'''信頼領域'''（しんらいりょういき、{{Lang-en-short|Trust region}}）とは、[[数理最適化]]の文脈で用いられる用語であり、目的関数をあるモデル関数（多くの場合[[二次関数]]である）で近似することが妥当である、と仮定する部分領域のことである。信頼領域法({{Lang-en-short|Trust region methods}}）はRestricted step methodsとも呼ばれる。

信頼領域内で、モデル関数が目的関数の適切な近似であったと判断された場合には、信頼領域を広げ、逆に近似が悪いと判断されれば信頼領域を狭くする。
近似の適切性の判断は、信頼領域内において、モデル関数の最適値と目的関数の値を比較することによって成されるが、目的関数とモデル関数の増分比を単純に閾値比較することが一般的である。

信頼領域法は、ある意味で[[直線探索|直線探索法]]と双対である。直線探索法では、まず降下方向を選択してからステップ幅を定めるのに対して、信頼領域法では、まずステップ幅（信頼領域半径）を定めてから、降下方向を選択する。

初めてこの用語を用いたのは{{Harv|Sorensen|1982}}であると考えられている。

==例==
Conceptually, in the [[Levenberg–Marquardt algorithm]], the objective function is iteratively approximated by a [[quadratic surface]], then using a linear solve, the estimate is updated. 
{{翻訳|概念的には、{{仮リンク|レーベンバーグ・マルカート解法|en|Levenberg–Marquardt algorithm|de|Levenberg-Marquardt-Algorithmus|fr|Algorithme de Levenberg-Marquardt|pl|Algorytm Levenberga-Marquardta|lt|Levenbergo-Markardo algoritmas|pt|Algoritmo de Levenberg–Marquardt|ru|Алгоритм Левенберга — Марквардта|zh|莱文贝格－马夸特方法|fa|الگوریتم لونبرگ-مارکارد}}において、目的関数が、線形求解を用いて反復推定値を更新させたその後に[[二次曲面]]で近似される。}}
This alone may not converge nicely if the initial guess is too far from the optimum. 
{{翻訳|初期推測値（{{Lang-en-short|initial guess}})があまりにもかけ離れた最適化である場合に、これだけではうまく収束しない場合もありえる。}}

For this reason, the algorithm instead restricts each step, preventing it from stepping "too far". 
{{翻訳|この理由のために、アルゴリズムは、各段階を制限する代わりに「遠く」の段階を防げる。}}

It operationalizes "too far" as follows.
{{翻訳|これは次のように「遠すぎる」場合の演算も可能としえる。}}

Rather than solving <math>A \Delta x = b</math> for <math>\Delta x</math>, it solves <math>(A + \lambda \operatorname{diag}(A) ) \Delta x = b</math> where <math>\operatorname{diag}(A)</math> is the diagonal matrix with the same diagonal as ''A'' and λ is a parameter that controls the trust-region size.
{{翻訳|むしろ<math>\Delta x</math>を解する<math>A \Delta x = b</math>を求解するよりも、それが<math>(A + \lambda \operatorname{diag}(A) ) \Delta x = b</math>によって求解された、<math>\operatorname{diag}(A)</math>は'' A''とλを同じ対角に持つ対角行列であり、その信頼領域サイズを制御するパラメータとなっている。}}
Geometrically, this adds a paraboloid centered at <math>\Delta x=0</math> to the [[quadratic form]], resulting in a smaller step. 
{{翻訳|幾何学的には、より小さな段階によりその結果は、二次関数で<math>\Delta x=0</math>を中心とする[[二次曲面]]が追加される。}}

The trick is to change the trust-region size (λ).
{{翻訳|トリックでは、信頼領域サイズ (λ)を変更できる。}}
At each iteration, the damped quadratic fit predicts a certain reduction in the cost function, <math>\Delta f_{\mathrm{pred}}</math>, which we would expect to be a smaller reduction than the true reduction.
{{翻訳|各反復において、減衰の二次適合は、真の縮小よりも小さく縮小することが期待されるコスト関数、あるいは<math>\Delta f_{\mathrm{pred}}</math>において一定の低減を予測できる。}}
Given <math>\Delta x</math> we can evaluate
: <math>\Delta f_{\mathrm{actual}} = f(x+\Delta x) - f(x)</math>
{{翻訳|与えられた<math>\Delta x</math>で<math>\Delta f_{\mathrm{actual}} = f(x+\Delta x) - f(x)</math>を評価できる。}}
By looking at the ratio <math>\Delta f_{\mathrm{pred}}/\Delta f_{\mathrm{actual}}</math> we can adjust the trust-region size.
{{翻訳|比<math>\Delta f_{\mathrm{pred}}/\Delta f_{\mathrm{actual}}</math>を見ることで、信頼領域サイズのを調整することができる。}}
In general, we expect <math>\Delta f_{\mathrm{pred}}</math> to be a bit less than <math>\Delta f_{\mathrm{actual}}</math> and so the ratio would be between, say, 0.25 and 0.5.
{{翻訳|一般的に、我々は、<math>\Delta f_{\mathrm{pred}}</math>が<math>\Delta f_{\mathrm{actual}}</math>よりも少し小さいことが期待されるので、たとえば比率は0.25と0.5との間になる。}}
If the ratio is more than 0.5, then we aren't damping the step much, so expand the trust region (decrease λ), and iterate.
{{翻訳|比が0.5以上である場合に、多くの段階が縮小されてないので、信頼領域（decrease λ）を展開し、反復させる。}}
If the ratio is smaller than 0.25, then the true function is diverging "too much" from the trust-region approximation, so shrink the trust region (increase λ) and try again.
{{翻訳|比が0.25よりも小さい場合に、真の関数は、「あまりにも多く」て、信頼領域の近似から発散してしまうので、信頼領域（increase λ）を縮小させて、再試行する。}}

==参考文献==
{{Refbegin|2}}
*{{Cite book|last=Andrew |first=R. Conn |last2=Nicholas |first2=I. M. |last3=Gould, |first4=Philippe |last4=L. Toint |url=http://books.google.com/books?id=5kNC4fqssYQC |title=Trust-Region Methods (MPS-SIAM Series on Optimization) |locatiomn=Philadelphia, PA |publisher=Society for Industrial and Applied Mathematics |date=2000 |oclc=43859543 |isbn=0898714605 |ref=harv}}
*{{Cite journal|last=Byrd |first=R. H, |first2=R. B. |last2=2Schnabel, |first3=G. A. |last3=Schultz. |url=http://epubs.siam.org/doi/abs/10.1137/0724076 |title=A trust region algorithm for nonlinearly constrained optimization |journal=SIAM J. Numer. Anal.|volume=24 |issue=5 |date=1987 |pages=1152–1170 |doi=10.1137/0724076 |ref=harv}}
*{{Cite journal|last=Sorensen |first=D. C. |url=http://epubs.siam.org/doi/abs/10.1137/0719026 |title=Newton’s Method with a Model Trust Region Modification |journal=SIAM J. Numer. Anal. |volume=19 |issue=2 |pages=409–426 |date=1982 |doi=10.1137/0719026 |ref=harv}}
* {{Cite book|last=Yuan |first=Y. |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.9964 |caption=A review of trust region algorithms for optimization |title=ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics |location=Edinburgh |date=2000 |publisher=Oxford University Press, USA. |ref=harv}}
* {{Cite journal|last=Yuan |first=Y |url=http://link.springer.com/article/10.1007%2Fs10107-015-0893-2 |title=Recent Advances in Trust Region Algorithms |journal=Math. Program |date=2015 |volume=151 |issue=1 |pages= 249-281 |ref=harv}}
{{Refend}}

== 外部リンク ==
{{Portal box|数学|物理学|コンピュータ}}
* [http://www.applied-mathematics.net/optimization/optimizationIntro.html Kranf site: Trust Region Algorithms]

{{iw-ref|en|Trust region|2015-20-09|oldid=684899212}}
{{最適化アルゴリズム}}

{{Applied-math-stub}}
{{デフォルトソート:しんらいりよういき}}
[[Category:最適化]]
[[Category:最適化アルゴリズム]]
[[Category:数学に関する記事]]
 <!-- [[:en:Trust region]]13:32, 9  October 2015の版より翻訳-->