準ニュートン法 （じゅんニュートンほう、英 : 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] L-BFGS法 があり[ 2]
SR1法は行列の更新が行列の正定値性 を保存しないため、不定値の行列のヘッセ行列に対しても用いることが出来る。またブロイデン法 は行列が対称行列でなくとも良く、通常の連立方程式の解を求めるのにも使うことが出来る。
通常のニュートン法と比べたときの準ニュートン法の最大の利点はヘッセ行列の逆行列を計算する必要がない更新法があるという点である。ニュートン法や、それを部分的に用いる内点法 のアルゴリズムはこのヘッセ行列の逆行列を計算する部分が計算のボトルネックとなることが多い。これに対して準ニュートン法はヘッセ行列の逆行列自体を直接近似できる。
ニュートン法と同様、関数
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}
∇
f
(
x
k
+
Δ
x
)
≈
∇
f
(
x
k
)
+
B
Δ
x
{\displaystyle \nabla f({\boldsymbol {x}}_{k}+\Delta {\boldsymbol {x}})\approx \nabla f({\boldsymbol {x}}_{k})+{\boldsymbol {B}}\Delta {\boldsymbol {x}}}
この勾配が0になると仮定するとニュートン・ステップが次の式で計算される。
Δ
x
=
−
B
−
1
∇
f
(
x
k
)
{\displaystyle \Delta {\boldsymbol {x}}=-{\boldsymbol {B}}^{-1}\nabla f({\boldsymbol {x}}_{k})}
そこでヘッセ行列の近似
B
{\displaystyle {\boldsymbol {B}}}
∇
f
(
x
k
+
Δ
x
)
=
∇
f
(
x
k
)
+
B
Δ
x
{\displaystyle \nabla f({\boldsymbol {x}}_{k}+\Delta {\boldsymbol {x}})=\nabla f({\boldsymbol {x}}_{k})+{\boldsymbol {B}}\Delta {\boldsymbol {x}}}
この方程式はセカント方程式と呼ばれる。
f
{\displaystyle f}
B
{\displaystyle {\boldsymbol {B}}}
B
{\displaystyle {\boldsymbol {B}}}
B
=
B
⊺
{\displaystyle {\boldsymbol {B}}={\boldsymbol {B}}^{\intercal }}
B
k
+
1
{\displaystyle {\boldsymbol {B}}_{k+1}}
B
k
{\displaystyle {\boldsymbol {B}}_{k}}
ノルム の意味において近い解を選ぼうとする。すなわち何らかの正定値行列
V
{\displaystyle {\boldsymbol {V}}}
B
k
+
1
=
arg
min
B
‖
B
−
B
k
‖
V
{\displaystyle {\boldsymbol {B}}_{k+1}=\arg \min _{\boldsymbol {B}}\|{\boldsymbol {B}}-{\boldsymbol {B}}_{k}\|_{\boldsymbol {V}}}
B
{\displaystyle {\boldsymbol {B}}}
[ 3]
x
k
{\displaystyle {\boldsymbol {x}}_{k}}
B
k
{\displaystyle {\boldsymbol {B}}_{k}}
アルゴリズムをまとめると以下のようになる。
Δ
x
k
=
−
α
B
k
−
1
∇
f
(
x
k
)
{\displaystyle \Delta {\boldsymbol {x}}_{k}=-\alpha {\boldsymbol {B}}_{k}^{-1}\nabla f({\boldsymbol {x}}_{k})}
x
k
+
1
=
x
k
+
Δ
x
k
{\displaystyle {\boldsymbol {x}}_{k+1}={\boldsymbol {x}}_{k}+\Delta {\boldsymbol {x}}_{k}}
新しい点での勾配
∇
f
(
x
k
+
1
)
{\displaystyle \nabla f({\boldsymbol {x}}_{k+1})}
y
k
=
∇
f
(
x
k
+
1
)
−
∇
f
(
x
k
)
{\displaystyle {\boldsymbol {y}}_{k}=\nabla f({\boldsymbol {x}}_{k+1})-\nabla f({\boldsymbol {x}}_{k})}
y
k
{\displaystyle {\boldsymbol {y}}_{k}}
B
k
+
1
−
1
{\displaystyle {\boldsymbol {B}}_{k+1}^{-1}}
Method
B
k
+
1
=
{\displaystyle {\boldsymbol {B}}_{k+1}=}
H
k
+
1
=
B
k
+
1
−
1
=
{\displaystyle {\boldsymbol {H}}_{k+1}={\boldsymbol {B}}_{k+1}^{-1}=}
DFP法
(
I
−
y
k
Δ
x
k
⊺
y
k
⊺
Δ
x
k
)
B
k
(
I
−
Δ
x
k
y
k
⊺
y
k
⊺
Δ
x
k
)
+
y
k
y
k
⊺
y
k
⊺
Δ
x
k
{\displaystyle \left({\boldsymbol {I}}-{\frac {{\boldsymbol {y}}_{k}\,\Delta {\boldsymbol {x}}_{k}^{\intercal }}{{\boldsymbol {y}}_{k}^{\intercal }\,\Delta {\boldsymbol {x}}_{k}}}\right){\boldsymbol {B}}_{k}\left({\boldsymbol {I}}-{\frac {\Delta {\boldsymbol {x}}_{k}{\boldsymbol {y}}_{k}^{\intercal }}{{\boldsymbol {y}}_{k}^{\intercal }\,\Delta {\boldsymbol {x}}_{k}}}\right)+{\frac {{\boldsymbol {y}}_{k}{\boldsymbol {y}}_{k}^{\intercal }}{{\boldsymbol {y}}_{k}^{\intercal }\,\Delta {\boldsymbol {x}}_{k}}}}
H
k
+
Δ
x
k
Δ
x
k
⊺
y
k
T
Δ
x
k
−
H
k
y
k
y
k
⊺
H
k
⊺
y
k
⊺
H
k
y
k
{\displaystyle {\boldsymbol {H}}_{k}+{\frac {\Delta {\boldsymbol {x}}_{k}\Delta {\boldsymbol {x}}_{k}^{\intercal }}{{\boldsymbol {y}}_{k}^{T}\,\Delta {\boldsymbol {x}}_{k}}}-{\frac {{\boldsymbol {H}}_{k}{\boldsymbol {y}}_{k}{\boldsymbol {y}}_{k}^{\intercal }{\boldsymbol {H}}_{k}^{\intercal }}{{\boldsymbol {y}}_{k}^{\intercal }{\boldsymbol {H}}_{k}{\boldsymbol {y}}_{k}}}}
BFGS法
B
k
+
y
k
y
k
⊺
y
k
⊺
Δ
x
k
−
B
k
Δ
x
k
(
B
k
Δ
x
k
)
⊺
Δ
x
k
T
B
k
Δ
x
k
{\displaystyle {\boldsymbol {B}}_{k}+{\frac {{\boldsymbol {y}}_{k}{\boldsymbol {y}}_{k}^{\intercal }}{{\boldsymbol {y}}_{k}^{\intercal }\Delta {\boldsymbol {x}}_{k}}}-{\frac {{\boldsymbol {B}}_{k}\Delta {\boldsymbol {x}}_{k}({\boldsymbol {B}}_{k}\Delta {\boldsymbol {x}}_{k})^{\intercal }}{\Delta {\boldsymbol {x}}_{k}^{T}{\boldsymbol {B}}_{k}\,\Delta {\boldsymbol {x}}_{k}}}}
(
I
−
y
k
Δ
x
k
⊺
y
k
⊺
Δ
x
k
)
⊺
H
k
(
I
−
y
k
Δ
x
k
⊺
y
k
⊺
Δ
x
k
)
+
Δ
x
k
Δ
x
k
⊺
y
k
⊺
Δ
x
k
{\displaystyle \left({\boldsymbol {I}}-{\frac {{\boldsymbol {y}}_{k}\Delta {\boldsymbol {x}}_{k}^{\intercal }}{{\boldsymbol {y}}_{k}^{\intercal }\Delta {\boldsymbol {x}}_{k}}}\right)^{\intercal }{\boldsymbol {H}}_{k}\left({\boldsymbol {I}}-{\frac {{\boldsymbol {y}}_{k}\Delta {\boldsymbol {x}}_{k}^{\intercal }}{{\boldsymbol {y}}_{k}^{\intercal }\Delta {\boldsymbol {x}}_{k}}}\right)+{\frac {\Delta {\boldsymbol {x}}_{k}\Delta {\boldsymbol {x}}_{k}^{\intercal }}{{\boldsymbol {y}}_{k}^{\intercal }\,\Delta {\boldsymbol {x}}_{k}}}}
ブロイデン法
B
k
+
y
k
−
B
k
Δ
x
k
Δ
x
k
⊺
Δ
x
k
Δ
x
k
⊺
{\displaystyle {\boldsymbol {B}}_{k}+{\frac {{\boldsymbol {y}}_{k}-{\boldsymbol {B}}_{k}\Delta {\boldsymbol {x}}_{k}}{\Delta {\boldsymbol {x}}_{k}^{\intercal }\,\Delta {\boldsymbol {x}}_{k}}}\,\Delta {\boldsymbol {x}}_{k}^{\intercal }}
H
k
+
(
Δ
x
k
−
H
k
y
k
)
Δ
x
k
⊺
H
k
Δ
x
k
⊺
H
k
y
k
{\displaystyle {\boldsymbol {H}}_{k}+{\frac {(\Delta {\boldsymbol {x}}_{k}-{\boldsymbol {H}}_{k}{\boldsymbol {y}}_{k})\Delta {\boldsymbol {x}}_{k}^{\intercal }{\boldsymbol {H}}_{k}}{\Delta {\boldsymbol {x}}_{k}^{\intercal }{\boldsymbol {H}}_{k}{\boldsymbol {y}}_{k}}}}
Broyden family
(
1
−
φ
k
)
B
k
+
1
BFGS
+
φ
k
B
k
+
1
DFP
,
φ
∈
[
0
,
1
]
{\displaystyle (1-\varphi _{k}){\boldsymbol {B}}_{k+1}^{\text{BFGS}}+\varphi _{k}{\boldsymbol {B}}_{k+1}^{\text{DFP}},\qquad \varphi \in [0,1]}
SR1法 （英語版 ）
B
k
+
(
y
k
−
B
k
Δ
x
k
)
(
y
k
−
B
k
Δ
x
k
)
⊺
(
y
k
−
B
k
Δ
x
k
)
⊺
Δ
x
k
{\displaystyle {\boldsymbol {B}}_{k}+{\frac {({\boldsymbol {y}}_{k}-{\boldsymbol {B}}_{k}\,\Delta {\boldsymbol {x}}_{k})({\boldsymbol {y}}_{k}-{\boldsymbol {B}}_{k}\,\Delta {\boldsymbol {x}}_{k})^{\intercal }}{({\boldsymbol {y}}_{k}-{\boldsymbol {B}}_{k}\,\Delta {\boldsymbol {x}}_{k})^{\intercal }\,\Delta {\boldsymbol {x}}_{k}}}}
H
k
+
(
Δ
x
k
−
H
k
y
k
)
(
Δ
x
k
−
H
k
y
k
)
⊺
(
Δ
x
k
−
H
k
y
k
)
⊺
y
k
{\displaystyle {\boldsymbol {H}}_{k}+{\frac {(\Delta {\boldsymbol {x}}_{k}-{\boldsymbol {H}}_{k}{\boldsymbol {y}}_{k})(\Delta {\boldsymbol {x}}_{k}-{\boldsymbol {H}}_{k}{\boldsymbol {y}}_{k})^{\intercal }}{(\Delta {\boldsymbol {x}}_{k}-{\boldsymbol {H}}_{k}{\boldsymbol {y}}_{k})^{\intercal }{\boldsymbol {y}}_{k}}}}
準ニュートン法は現在、汎用的に用いられている最適化アルゴリズムの1つであり、多くのプログラミング言語 による実装が存在する。
![{\displaystyle (1-\varphi _{k}){\boldsymbol {B}}_{k+1}^{\text{BFGS}}+\varphi _{k}{\boldsymbol {B}}_{k+1}^{\text{DFP}},\qquad \varphi \in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2373b9608044742c60d4782383891bd116f7450)
