準ニュートン法
(ただし 
)を解くための
を
としたとき, 
の解 
を
(
は
を
準ニュートン法
準ニュートン法（じゅんニュートンほう、英: quasi-Newton method）とは、非線形連立方程式の解、あるいは連続最適化問題の関数の極大・極小解を見つけるためのアルゴリズムである。準ニュートン法はニュートン法を元にしており、非線形連立方程式の解を求めることが基本になるが、最適化問題においては、関数の停留点を見つけるために、関数の勾配=0の連立方程式を解くという立場から考えることができる。以下は、主に最適化問題の立場からの説明である。
概要
通常のニュートン法は最適解の近傍が二次関数で近似できると仮定し、一階および二階の導関数を解の探索に用いる。高次元空間上で定義される関数に対しては、最小化（最大化）したい関数の勾配ベクトルおよびヘッセ行列を用いる。一方で、準ニュートン法ではヘッセ行列を陽に計算する必要がない。その代わりにヘッセ行列が最適化の繰り返し計算の過程で得られる勾配ベクトルにより近似される。準ニュートン法は多次元関数の零点 (関数の値が0となる場所) を探すアルゴリズムの一種であるセカント法（割線法）の一般化であると見ることも出来る。多次元の問題においてはセカント方程式は1次元の場合と違い一意に定まらず、劣決定問題となるが、準ニュートン法は近似の制約が異なっており、具体的には現在の推定ヘッセ行列を低ランク行列成分を用いて更新する。
最初の準ニュートン法のアルゴリズムは物理学者のW.C. Davidonがアルゴンヌ国立研究所で研究中に提案したものである。彼が1959年に提案した最初の準ニュートン法は、1963年にFletcherとPowellが世に広め、後にDFP法（Davidon-Fletcher-Powell法）とよばれるようになったが、1970年後半、より効率的なBFGS法の登場により、今日ではあまり用いられていない。現在最も用いられている準ニュートン法のアルゴリズムはSR1法（対称ランクワン法、symmetric rank-one）、BHHH法、そしてBFGS法（提案者であるBroyden, Fletcher, Goldfarb, Shannoの頭文字から）である。大規模問題に対応させる方法の一つとして記憶制限準ニュートン法が1980年に発表され[1]、BFGS法を記憶制限準ニュートン法にした物としてL-BFGS法があり[2]、良く用いられるアルゴリズムの1つである。
SR1法は行列の更新が行列の正定値性を保存しないため、不定値の行列のヘッセ行列に対しても用いることが出来る。またブロイデン法は行列が対称行列でなくとも良く、通常の連立方程式の解を求めるのにも使うことが出来る。
通常のニュートン法と比べたときの準ニュートン法の最大の利点はヘッセ行列の逆行列を計算する必要がない更新法があるという点である。ニュートン法や、それを部分的に用いる内点法のアルゴリズムはこのヘッセ行列の逆行列を計算する部分が計算のボトルネックとなることが多い。これに対して準ニュートン法はヘッセ行列の逆行列自体を直接近似できる。
手法の説明
ニュートン法と同様、関数 
| 一般 | |
|---|---|
| 微分可能 |
|
| 凸縮小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) | |||||
|---|---|---|---|---|---|
| グラフ理論 |
| ||||
| ネットワークフロー (最大流問題) |
|
