準ニュートン法
ニュートン法と同様、関数 f ( x ) {\displaystyle f({\boldsymbol {x}})} の解を見つけるために二次の近似を用いる。 f ( x ) {\displaystyle f({\boldsymbol {x}})} の二階のテイラー展開は
f ( x k + Δ x ) ≈ f ( x k ) + ∇ f ( x k ) ⊺ Δ x + 1 2 Δ x ⊺ B Δ x {\displaystyle f({\boldsymbol {x}}_{k}+\Delta {\boldsymbol {x}})\approx f({\boldsymbol {x}}_{k})+\nabla f({\boldsymbol {x}}_{k})^{\intercal }\Delta {\boldsymbol {x}}+{\frac {1}{2}}\Delta {\boldsymbol {x}}^{\intercal }{\boldsymbol {B}}\Delta {\boldsymbol {x}}}
となる。この式で ∇ f {\displaystyle \nabla f} は勾配を表し、 B {\displaystyle {\boldsymbol {B}}} はヘッセ行列の近似を表す。勾配 ∇ f {\displaystyle \nabla f} はさらに次のように近似される。
現在最も用いられている準ニュートン法のアルゴリズムはSR1(対称ランクワン、symmetric rank-one)法、BHHH法、そしてBFGS法 (提案者であるBroyden, Fletcher, Goldfarb, Shannoの頭文字から) である。大規模問題に対応させる方法の一つとして記憶制限準ニュートン法が1980年に発表され、BFGS法を記憶制限準ニュートン法にした物としてL-BFGS法があり、良く用いられるアルゴリズムの1つである。
SR1法は行列の更新が行列の正定値性を保存しないため、不定値の行列のヘッセ行列に対しても用いることが出来る。またブロイデン法は行列が対称行列でなくとも良く、通常の連立方程式の解を求めるのにも使うことが出来る。
通常のニュートン法と比べたときの準ニュートン法の最大の利点はヘッセ行列の逆行列を計算する必要がない更新法があるという点である。ニュートン法や、それを部分的に用いる内点法のアルゴリズムはこのヘッセ行列の逆行列を計算する部分が計算のボトルネックとなることが多い。これに対して準ニュートン法はヘッセ行列の逆行列自体を直接近似できる。