準ニュートン法準ニュートン法
準ニュートン法ニュートン法に基づく最適化手法で、主に非線形方程式や連続関数のゼロ点、最大値、最小値の問題を解くために使用されます。
ニュートン法におけるヤコビアン行列または ヘッセ行列 行列の計算が難しい、または不可能な場合には、準ニュートン法が役に立ちます。これは、非線形最適化問題を解決するための最も効果的な方法の 1 つであり、米国によって開発されました。 アルゴンヌ 国立研究所の物理学者 WCDアビドン で 20 世紀 50 1990年代に提案されました。
準ニュートン法の考え方
ニュートン法は毎回解決します ヘッセ行列 行列を使用する場合、最初に逆行列を計算する必要があり、効率が低下しますが、準ニュートン法では正定行列を使用して近似します。 ヘッセ行列 行列の逆行列。これにより、アルゴリズムの複雑さが軽減され、効率が向上します。
一般的な準ニュートンアルゴリズム
- DFP (デイビドン・フレッチャー・パウエル) アルゴリズム
DFP アルゴリズムでは、各反復の行列が 2 つの追加項で構成されていると仮定して、 の近似値として選択されます。
で、
そして
は未決定の行列です。しかし
作るには
準ニュートン条件を満たすと、そして満足する
望ましい
利用可能なマトリックスの反復公式
初期行列が
が正定値の場合、反復プロセスの各行列
それらはすべて正しいです。
- BFGS (Broyden-Fletcher-Goldfard-Shano) アルゴリズム
DFP が使用するヘッセ行列の逆行列の近似
、BFGS アルゴリズムは
ヘッセ行列の近似
、対応する準ニュートン条件
各反復ステップの行列は次のように仮定します。
でできていますこれは 2 つの追加項目で構成されます。
で、そしては未決定の行列です。しかし
作るには準ニュートン条件を満たすと、そして満足する
望ましい
利用可能なマトリックスの反復公式
初期行列が
が正定値の場合、反復プロセスの各行列それらはすべて正しいです。
- Broyden (Broyden のアルゴリズム) クラス アルゴリズム
BFGS アルゴリズム行列は次から取得できます。BFGS アルゴリズムの反復公式は次のとおりです。反復式。
覚えて
シャーマン・モリソンの公式を 2 回適用すると、次のようになります。
BFGS アルゴリズムと呼ばれる説明反復式。
ここで、シャーマン・モリソンの公式: 仮定
はn次の可逆行列であり、
は n 次元ベクトルであり、
これは可逆行列でもあるため、次のようになります。
DFP アルゴリズムの反復式で求めます。として記録される
、BFGS アルゴリズムの反復公式による得られたと が両方とも準ニュートン条件を満たすため、2 つの線形結合は次のように記述されます。
また、準ニュートン条件も満たし、正定値です。で、
。このタイプのアルゴリズムは、Broyden 型アルゴリズムと呼ばれます。