信頼地域

数学的最適化において、信頼領域とは、モデル関数 (多くの場合、2 次関数) を使用して近似される目的関数の領域のサブセットです。信頼領域内で目的関数の適切なモデルが見つかった場合、領域は拡大されます。逆に、近似が不十分な場合は、領域は縮小されます。

適合性は、モデル近似からの予想される改善率と目的関数で観察された実際の改善率を比較することによって評価されます。比率の単純なしきい値設定が拡大と縮小の基準として使用されます。モデル関数は、妥当な近似値を提供する領域でのみ「信頼」されます。

信頼領域法は、ある意味では直線探索法の二重性を持っています。信頼領域法では、最初にステップ サイズ (信頼領域のサイズ) を選択し、次にステップ方向を選択しますが、直線探索法では、最初にステップ方向を選択し、次にステップ サイズを選択します。

信頼領域法の基本的な考え方は多くの名前で知られていますが、この用語を最初に使ったのはソレンセン（1982）のようです。^[1]フレッチャー（1980）の有名な教科書では、これらのアルゴリズムを制限ステップ法と呼んでいます。^[2]さらに、この方法の初期の基礎研究で、ゴールドフェルド、クワント、トロッター（1966）はこれを二次山登り法と呼んでいます。^[3]

概念的には、Levenberg–Marquardt アルゴリズムでは、目的関数は2 次曲面で反復的に近似され、線形ソルバーを使用して推定値が更新されます。初期推定が最適値から離れすぎている場合、これだけではうまく収束しない可能性があります。このため、アルゴリズムでは各ステップを制限し、「離れすぎた」ステップを回避します。「離れすぎた」ステップは次のように操作化されます。を解くのではなく、 を解きます。ここで、 はAと同じ対角を持つ対角行列であり、 λ は信頼領域のサイズを制御するパラメーターです。幾何学的には、これにより を中心とする放物面が2 次形式に追加され、ステップが小さくなります。 ${\displaystyle A\,\Delta x=b}$${\displaystyle \Delta x}$${\displaystyle {\big (}A+\lambda \operatorname {diag} (A){\big )}\,\Delta x=b}$${\displaystyle \operatorname {diag} (A)}$${\displaystyle \Delta x=0}$

コツは信頼領域のサイズ（λ）を変えることです。各反復で、減衰二次関数近似はコスト関数の一定の減少を予測しますが、これは実際の減少よりも小さい減少になると予想されます。 が与えられている場合、次のように評価できます 。${\displaystyle \Delta f_{\text{pred}}}$${\displaystyle \Delta x}$

${\displaystyle \Delta f_{\text{actual}}=f(x)-f(x+\Delta x).}$

比率 を調べることで、信頼領域のサイズを調整できます。一般に、 はよりも少し小さくなることが予想されるため、比率は、たとえば 0.25 から 0.5 の間になります。比率が 0.5 より大きい場合は、ステップを減衰させすぎているため、信頼領域を拡大 (λ を小さく) して反復します。比率が 0.25 より小さい場合は、真の関数が信頼領域近似から「大きく」逸脱しているため、信頼領域を縮小 (λ を大きく) して再試行します。 ${\displaystyle \Delta f_{\text{pred}}/\Delta f_{\text{actual}}}$${\displaystyle \Delta f_{\text{pred}}}$${\displaystyle \Delta f_{\text{actual}}}$

• Dennis, JE Jr.; Schnabel, Robert B. (1983)。「ニュートン法の全体的収束修正」。制約のない最適化と非線形方程式の数値的手法。Englewood Cliffs: Prentice-Hall。pp. 111–154。ISBN 0-13-627216-9。
• Andrew R. Conn、Nicholas IM Gould、Philippe L. Toint「信頼領域法 (最適化に関する MPS-SIAM シリーズ)」。
• Byrd, R. H, RB Schnabel、GA Schultz. 「非線形制約最適化のための信頼領域アルゴリズム」、SIAM J. Numer. Anal.、24 (1987)、pp. 1152–1170。
• Yuan, Y. 「最適化のための信頼領域アルゴリズムのレビュー」、ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics、エジンバラ、2000 Oxford University Press、米国。
• Yuan, Y.「信頼領域アルゴリズムの最近の進歩」、数学プログラム、2015

• Kranf サイト: 信頼領域アルゴリズム
• 信頼領域法