ブロイデン法

数値解析において、ブロイデン法（ブロイデンほう英: Broyden's method）とは準ニュートン法の1種であり、多変数関数の求根に用いられるアルゴリズムである。1965年にチャールズ・ジョージ・ブロイデンが発表した。

ニュートン法によりf(x) = 0を解く場合、各イテレーションごとにヤコビアンJを用いることになる。しかし、ヤコビアンを計算するには困難で複雑な演算を要する。ブロイデン法では、ヤコビアン全体を最初のイテレーションで1回だけ計算し、以降のイテレーションではランク1更新を用いる。

1979年、Gayによりブロイデン法はサイズn × nの線形システムに適用したとき2 nステップで終了することが証明された。しかし、他の準ニュートン法と同様、非線形システムに対しては収束する保証はない。

手法の詳細

1変数方程式の求根

割線法では、f′のx_nにおける1階微分を有限差分近似する。

$f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}$

その上で、ニュートン法と同様の操作を繰り返す

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f^{\prime }(x_{n})}}$

ここでnはイテレーション指数である。

非線形方程式系の求根

k本の非線形方程式の系

${\boldsymbol {f}}({\boldsymbol {x}})=\mathbf {0}$

を考える。ここでfはベクトルxのベクトル値関数である。

${\boldsymbol {x}}=(x_{1},x_{2},x_{3},\dotsc ,x_{k})$

${\boldsymbol {f}}({\boldsymbol {x}})={\big (}f_{1}(x_{1},x_{2},\dotsc ,x_{k}),f_{2}(x_{1},x_{2},\dotsc ,x_{k}),\dotsc ,f_{k}(x_{1},x_{2},\dotsc ,x_{k}){\big )}$

このような問題に対して、ブロイデンは1次元ニュートン法の微分をヤコビアンJで置き換えて一般化した手法を考案した。ヤコビアンは、次のように割線法における有限差分近似にもとづいて反復的に決定される。

${\boldsymbol {J}}_{n}({\boldsymbol {x}}_{n}-{\boldsymbol {x}}_{n-1})\simeq {\boldsymbol {f}}({\boldsymbol {x}}_{n})-{\boldsymbol {f}}({\boldsymbol {x}}_{n-1})$

ここでnはイテレーション指数である。

${\boldsymbol {f}}_{n}={\boldsymbol {f}}({\boldsymbol {x}}_{n})$

$\Delta {\boldsymbol {x}}_{n}={\boldsymbol {x}}_{n}-{\boldsymbol {x}}_{n-1}$

$\Delta {\boldsymbol {f}}_{n}={\boldsymbol {f}}_{n}-{\boldsymbol {f}}_{n-1}$

のように定義すると、上式は以下のように簡潔に書ける。

${\boldsymbol {J}}_{n}\Delta {\boldsymbol {x}}_{n}\simeq \Delta {\boldsymbol {f}}_{n}$

上式はkが1より大きい場合は劣決定系となる。ブロイデンは、以下のようにヤコビアンの現状の推定値J_n−1を最低限の変更により割線方程式を満たすよう改善することを提案した。

${\boldsymbol {J}}_{n}={\boldsymbol {J}}_{n-1}+{\frac {\Delta {\boldsymbol {f}}_{n}-{\boldsymbol {J}}_{n-1}\Delta {\boldsymbol {x}}_{n}}{\|\Delta {\boldsymbol {x}}_{n}\|^{2}}}\Delta {\boldsymbol {x}}_{n}^{\top }$

これにより以下のフロベニウスノルムが最小化される。

$\|{\boldsymbol {J}}_{n}-{\boldsymbol {J}}_{n-1}\|_{\rm {F}}$

これでNewton directionへ進むことができる。

${\boldsymbol {x}}_{n+1}={\boldsymbol {x}}_{n}-{\boldsymbol {J}}_{n}^{-1}{\boldsymbol {f}}(\mathbf {x} _{n})$

ブロイデンはSherman-Morrisonの公式を用いてヤコビアンの逆行列を直接更新することも提案している。

${\boldsymbol {J}}_{n}^{-1}={\boldsymbol {J}}_{n-1}^{-1}+{\frac {\Delta {\boldsymbol {x}}_{n}-{\boldsymbol {J}}_{n-1}^{-1}\Delta {\boldsymbol {f}}_{n}}{\Delta {\boldsymbol {x}}_{n}^{\mathrm {T} }{\boldsymbol {J}}_{n-1}^{-1}\Delta {\boldsymbol {f}}_{n}}}\Delta {\boldsymbol {x}}_{n}^{\top }{\boldsymbol {J}}_{n-1}^{-1}$

この1つめの手法は「良いブロイデン法」とも呼ばれる。

類似手法として、J_n−1に若干異なる変更を加える手法も導出できる。この2つめの手法は「悪いブロイデン法」とも呼ばれる(ただし、を参照)。

${\boldsymbol {J}}_{n}^{-1}={\boldsymbol {J}}_{n-1}^{-1}+{\frac {\Delta {\boldsymbol {x}}_{n}-{\boldsymbol {J}}_{n-1}^{-1}\Delta {\boldsymbol {f}}_{n}}{\|\Delta {\boldsymbol {f}}_{n}\|^{2}}}\Delta {\boldsymbol {f}}_{n}^{\top }$

これは上とはことなる以下のフロベニウスノルムを最小化する。

$\|{\boldsymbol {J}}_{n}^{-1}-{\boldsymbol {J}}_{n-1}^{-1}\|_{\rm {F}}$

他にも多くの準ニュートン法が提案されており、これを用いてある関数の勾配の求根を行うことによりその関数の最大値または最小値をみつける、すなわち最適化を行うために活用されている。勾配のヤコビアンはヘッシアンと呼ばれ、対称行列であるため更新式にさらなる制約が追加される。

Broyden Classの手法

上述の2つの手法に加え、ブロイデンは関連する手法の1群を定義した。一般に、Broyden Classの手法は以下の形式で与えられる。$${\boldsymbol {J}}_{k+1}={\boldsymbol {J}}_{k}-{\frac {{\boldsymbol {J}}_{k}s_{k}s_{k}^{\top }{\boldsymbol {J}}_{k}}{s_{k}^{\top }{\boldsymbol {J}}_{k}s_{k}}}+{\frac {y_{k}y_{k}^{\top }}{y_{k}^{T}s_{k}}}+\phi _{k}\left(s_{k}^{\top }{\boldsymbol {J}}_{k}s_{k}\right)v_{k}v_{k}^{\top }$$ここで、$y_{k}:={\boldsymbol {f}}({\boldsymbol {x}}_{k+1})-{\boldsymbol {f}}({\boldsymbol {x}}_{k})$および$s_{k}:={\boldsymbol {x}}_{k+1}-{\boldsymbol {x}}_{k}$、$$v_{k}=\left[{\frac {y_{k}}{y_{k}^{T}s_{k}}}-{\frac {\mathbf {J} _{k}s_{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}\right]$$であり、$k=1,2,...$に対して各$\phi _{k}\in \mathbb {R}$を定めることによりその手法が決定される。

Broyden classに分類できる手法のいくつかは他の著者により提案されている。

• DFP法はBroyden classに分類できる手法のうち、先述の2手法がブロイデンにより提案されるようりも前に発表されていた唯一の手法である。DFP法は$\phi _{k}=1$を用いる。
• Schubert's algorithmまたは疎ブロイデン法は疎なヤコビアン向けの修正版である。
• Klement (2014) は多方程式系の求根を少ないイテレーションで解く。

関連項目

• 割線法
• ニュートン法
• 準ニュートン法
• ニュートン法による最適化
• DFP法
• BFGS法

関連文献

• Dennis, J. E.; Schnabel, Robert B. (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice Hall. pp. 168–193. ISBN 0-13-627216-9 
• Fletcher, R. (1987). Practical Methods of Optimization (Second ed.). New York: John Wiley & Sons. pp. 44–79. ISBN 0-471-91547-5. https://archive.org/details/practicalmethods0000flet 

外部リンク

• Simple basic explanation: The story of the blind archer