信頼領域法

OR事典

信頼領域法

読み方：しんらいりょういきほう
【英】：trust region method

制約なし最適化問題を解く勾配法の1つ. ヘッセ行列が正定値でなくてもニュートン法が大域的収束するように工夫された解法であるが, 準ニュートン法や制約付き最適化法の枠組みにも拡張されている. 回目の反復での近似解 が与えられたとき, 目的関数の2次近似が妥当であると思われる信頼領域でその2次近似を最小化するステップ を求める. そして関数の減少量に基づいて, 信頼領域の大きさを調節したり, と近似解を更新したりする.

「OR事典」の他の用語

非線形計画：

乗数法  二者択一定理  作用素分割法  信頼領域法  共役勾配法  共役関数  内点法

ウィキペディア

信頼領域

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/10 09:11 UTC 版)

この項目「信頼領域」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en: Trust region） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2022年9月）

信頼領域（しんらいりょういき、英: trust region）は、数理最適化において目的関数を近似するモデル関数（多くの場合二次関数）が有効とみなされる領域をいう。目的関数のモデル関数による近似が信頼領域内で十分であるならば、信頼領域を拡大して反復を継続し、逆に近似が不十分な場合、信頼領域を縮小して続行する。

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

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

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

例

レーベンバーグ・マーカート法は目的関数を二次曲面で反復的に近似し、線形ソルバーにより推定値を更新する。初期推定が最適から乖離している場合、これだけではうまく収束しない可能性があるため、本法では代わりに各ステップを制限し、「行き過ぎ」ないようにする。具体的には、${\displaystyle A\,\Delta x=b}$

Optimization computes maxima and minima.

非線形（制約付き）

一般	バリア関数 ペナルティ関数法
微分可能	ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法

凸最適化

凸最小化	切除平面法 簡約勾配法 劣勾配法 近接勾配法
線形 および 二次	内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法）
グラフ理論	最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法
ネットワークフロー (最大流問題)	ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア