| 翻訳と辞書 |
準ニュートン法[じゅんにゅーとんほう]
準ニュートン法 (英: quasi Newton method)とは、連続最適化問題の関数の極大・極小解を見つけるためのアルゴリズムである。準ニュートン法はニュートン法を元にしており、関数の勾配が0になるという意味での関数の不動点を見つけるための方法の一種である。
== 概要 ==
通常のニュートン法は最適解の近傍が二次関数で近似できると仮定し、一階および二階の導関数を不動点探索に用いる。高次元空間上で定義される関数に対しては、最小化(最大化)したい関数の勾配ベクトルおよびヘッセ行列を用いる。一方で、準ニュートン法ではヘッセ行列を陽に計算する必要がない。その代わりにヘッセ行列が最適化の繰り返し計算の過程で得られる勾配ベクトルにより近似される。準ニュートン法は多次元関数の根 (関数の値が0となる場所) を探すアルゴリズムの一種であるセカント法（割線法）の一般化であると見ることも出来る。多次元の問題においてはセカント方程式は未制約問題となるが、準ニュートン法は解にかかる制約が異なっており、具体的には現在の推定ヘッセ行列を低ランク行列成分を用いて更新する。
最初の準ニュートン法のアルゴリズムは物理学者のW.C. Davidonがアルゴンヌ国立研究所で研究中に提案したものである。彼が1959年に提案した最初の準ニュートン法はDFP法とよばれ、後にFletcherとPowellが1963年に世に広めたが、今日ではあまり実用的に用いられていない。現在最も用いられている準ニュートン法のアルゴリズムはSR1法、BHHH法、そしてBFGS法 (提案者であるBroyden, Fletcher, Goldfarb, Shannoの頭文字から) である。大規模問題に対応させる方法の一つとして記憶制限準ニュートン法が1980年に発表され、BFGS法を記憶制限準ニュートン法にした物としてL-BFGS法があり、良く用いられるアルゴリズムの1つである。
SR1法は行列の更新が行列の正定値性を保存しないため、不定値の行列のヘッセ行列に対しても用いることが出来る。またブロイデン法は行列が対称行列でなくとも良く、通常の連立方程式の解を求めるのにも使うことが出来る。
通常のニュートン法と比べたときの準ニュートン法の最大の利点はヘッセ行列の逆行列を計算する必要がない点にある。ニュートン法や、それを部分的に用いる内点法のアルゴリズムはこのヘッセ行列の逆行列を計算する部分が計算のボトルネックとなることが多い。これに対して準ニュートン法はヘッセ行列の逆行列自体を直接近似できる。
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「準ニュートン法」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|