信頼領域

信頼領域（しんらいりょういき、英: Trust region）とは、数理最適化の文脈で用いられる用語であり、目的関数をあるモデル関数（多くの場合二次関数である）で近似することが妥当である、と仮定する部分領域のことである。信頼領域法(英: Trust region methods）はRestricted step methodsとも呼ばれる。

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

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

初めてこの用語を用いたのは(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. （→概念的には、レーベンバーグ・マルカート解法において、目的関数が、線形求解を用いて反復推定値を更新させたその後に二次曲面で近似される。） This alone may not converge nicely if the initial guess is too far from the optimum. （→初期推測値（英: 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 $A\Delta x=b$ for $\Delta x$, it solves $(A+\lambda \operatorname {diag} (A))\Delta x=b$ where $\operatorname {diag} (A)$ is the diagonal matrix with the same diagonal as A and λ is a parameter that controls the trust-region size. （→むしろ$\Delta x$を解する$A\Delta x=b$を求解するよりも、それが$(A+\lambda \operatorname {diag} (A))\Delta x=b$によって求解された、$\operatorname {diag} (A)$は Aとλを同じ対角に持つ対角行列であり、その信頼領域サイズを制御するパラメータとなっている。） Geometrically, this adds a paraboloid centered at $\Delta x=0$ to the quadratic form, resulting in a smaller step. （→幾何学的には、より小さな段階によりその結果は、二次関数で$\Delta x=0$を中心とする二次曲面が追加される。）

The trick is to change the trust-region size (λ). （→トリックでは、信頼領域サイズ (λ)を変更できる。） At each iteration, the damped quadratic fit predicts a certain reduction in the cost function, $\Delta f_{\mathrm {pred} }$, which we would expect to be a smaller reduction than the true reduction. （→各反復において、減衰の二次適合は、真の縮小よりも小さく縮小することが期待されるコスト関数、あるいは$\Delta f_{\mathrm {pred} }$において一定の低減を予測できる。） Given $\Delta x$ we can evaluate

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

（→与えられた$\Delta x$で$\Delta f_{\mathrm {actual} }=f(x+\Delta x)-f(x)$を評価できる。） By looking at the ratio $\Delta f_{\mathrm {pred} }/\Delta f_{\mathrm {actual} }$ we can adjust the trust-region size. （→比$\Delta f_{\mathrm {pred} }/\Delta f_{\mathrm {actual} }$を見ることで、信頼領域サイズのを調整することができる。） In general, we expect $\Delta f_{\mathrm {pred} }$ to be a bit less than $\Delta f_{\mathrm {actual} }$ and so the ratio would be between, say, 0.25 and 0.5. （→一般的に、我々は、$\Delta f_{\mathrm {pred} }$が$\Delta f_{\mathrm {actual} }$よりも少し小さいことが期待されるので、たとえば比率は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 λ）を縮小させて、再試行する。）

参考文献

• Andrew, R. Conn; Nicholas, I. M.; Gould,; L. Toint, Philippe (2000). Trust-Region Methods (MPS-SIAM Series on Optimization). Society for Industrial and Applied Mathematics. ISBN 0898714605. OCLC 43859543. http://books.google.com/books?id=5kNC4fqssYQC 
• Byrd, R. H,; 2Schnabel,, R. B.; Schultz., G. A. (1987). “A trust region algorithm for nonlinearly constrained optimization”. SIAM J. Numer. Anal. 24 (5): 1152–1170. doi:10.1137/0724076. http://epubs.siam.org/doi/abs/10.1137/0724076. 
• 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. http://epubs.siam.org/doi/abs/10.1137/0719026. 
• Yuan, Y. (2000). ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics. Edinburgh. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.9964 
• Yuan, Y (2015). “Recent Advances in Trust Region Algorithms”. Math. Program 151 (1): 249-281. http://link.springer.com/article/10.1007%2Fs10107-015-0893-2. 

外部リンク

• Kranf site: Trust Region Algorithms

この記事は英語版ウィキペディアにある同じ項目の記事の2015-20-09の版から翻訳された記事である。