信頼領域
数理最適化において、信頼領域(しんらいりょういき、英: trust region)は、目的関数を近似するモデル関数(多くの場合二次関数)が有効とみなされる領域をいう。目的関数のモデル関数による近似が信頼領域内で十分であるならば、信頼領域を拡大して反復を継続し、逆に近似が不十分な場合、信頼領域を縮小して続行する。
近似が十分がどうかは、モデル関数から期待される改善と、目的関数で観測された実際の改善との比により評価される。この比を単純にしきい値と比較した結果に基き信頼領域を拡大・縮小する。モデル関数は、妥当な近似値を与える領域内でのみ「信頼」される。
信頼領域法は、ある意味で直線探索法と双対を成す。信頼領域法ではまずステップサイズ(信頼領域のサイズ)を選択し、次にステップ方向を選択するが、直線探索法ではまずステップ方向を選択し、次にステップサイズを選択する。
信頼領域法の背後にある考え方には、多くの名前がある。信頼領域という用語が使用されたのは、Sorensen 1982が最初とされる。人気のある教科書Fletcher 1980では、これらのアルゴリズムを制限ステップ法(restricted-step methods)と呼んでいる。さらに、この方法に関する初期の基礎研究、Goldfeld, Quandt & Trotter 1966では二次山登り法(quadratic hill-climbing)と呼ばれている。
レーベンバーグ・マルカート法は、目的関数を二次曲面で反復的に近似し、線形ソルバーにより推定値を更新する。初期推定が最適から乖離している場合、これだけではうまく収束しない可能性があるため、本法では代わりに各ステップを制限し、「行き過ぎ」ないようにする。具体的には、 A Δ x = b {\displaystyle A\,\Delta x=b} を Δ x {\displaystyle \Delta x} について解く代わりに、 ( A + λ diag  ( A ) ) Δ x = b {\displaystyle {\big (}A+\lambda \operatorname {diag} (A){\big )}\,\Delta x=b} を解く。 ここで diag  ( A ) {\displaystyle \operatorname {diag} (A)} はAと同じ対角をもつ対角行列、λは信頼領域のサイズを制御するパラメータである。幾何学的には、上記変更は Δ x = 0 {\displaystyle \Delta x=0} を中心とする放物面を加算したことに相当し、このためステップサイズが小さく抑えられる。
推定値の発散を防ぎ、かつ迅速に解に収束させるためには、いかに信頼領域のサイズ(λ)を変更するかが重要である。