準ニュートン法

数値解析において、準ニュートン法は、ニュートン法によく似た反復再帰式を介して関数の零点を見つけるか、関数の極大値と極小値を見つけるために使用される反復数値法であるが、関数の正確な導関数の代わりに近似導関数を使用する。ニュートン法では、零点の検索に使用する場合は多変量関数のすべての偏導関数のヤコビ行列が必要であり、極値の検索に使用する場合はヘッセ行列が必要である。一方、準ニュートン法は、ヤコビ行列またはヘッセ行列が利用できない、または反復ごとに計算するのが非現実的な場合に使用できる。

逐次二次計画法など、ニュートン法に帰着するいくつかの反復法も準ニュートン法とみなされることがあります。

多変数関数の零点を見つけるニュートン法はで与えられます。ここで はについて評価されたのヤコビ行列の左逆行列です。 ${\displaystyle g}$${\displaystyle x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})}$${\displaystyle [J_{g}(x_{n})]^{-1}}$ ${\displaystyle J_{g}(x_{n})}$${\displaystyle g}$${\displaystyle x_{n}}$

厳密に言えば、正確なヤコビアンを近似値に置き換える方法はいずれも準ニュートン法です。^[1]たとえば、コード法（すべての反復でが に置き換えられる）は簡単な例です。以下に示す最適化方法は、準ニュートン法の重要なサブクラスであるセカント法を参照しています。^[2]${\displaystyle J_{g}(x_{n})}$${\displaystyle J_{g}(x_{n})}$${\displaystyle J_{g}(x_{0})}$

極値を見つけるために開発された方法をゼロを見つけるために使用することは、必ずしも良い考えではありません。極値を見つけるために使用される方法の大半では、使用される行列が対称的であることが求められるためです。これは極値の検索のコンテキストでは当てはまりますが、ゼロの検索ではほとんど当てはまりません。Broydenの「良い」方法と「悪い」方法は、極値を見つけるために一般的に使用される 2 つの方法で、ゼロを見つけるためにも適用できます。使用できる他の方法は、列更新法、逆列更新法、準ニュートン最小二乗法、準ニュートン逆最小二乗法です。

最近では、準ニュートン法は、複数の連立方程式（流体構造相互作用問題や物理学における相互作用問題など）の解を求めるために適用されています。準ニュートン法では、各構成システム（全体システムよりも単純）を個別に解くことで、全体システムの解が見つかるまで、循環的に反復して解を求めることができます。^{[2] [3]}

スカラー値関数の最小値または最大値の探索は、その関数の勾配のゼロの探索と密接に関連しています。したがって、準ニュートン法は関数の極値を見つけるために簡単に適用できます。言い換えると、 が の勾配である場合、ベクトル値関数のゼロの探索は、スカラー値関数 の極値の探索に対応します。つまり、 のヤコビアンはのヘッセ行列になります。主な違いは、ヘッセ行列は、ゼロを探索するときのヤコビ行列とは異なり、対称行列 であることです。最適化で使用されるほとんどの準ニュートン法は、この対称性を活用します。 ${\displaystyle g}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f}$

最適化において、準ニュートン法（可変メトリック法の特殊なケース）は、関数の極大値と極小値を見つけるアルゴリズムです。最適化のための準ニュートン法は、ニュートン法に基づいて関数の停留点、つまり勾配が 0 である点を見つけます。ニュートン法では、関数は最適値の周りの領域で二次関数として局所的に近似できると仮定し、1 次導関数と 2 次導関数を使用して停留点を見つけます。より高次元では、ニュートン法は最小化する関数 の勾配と2 次導関数のヘッセ行列を使用します。

準ニュートン法では、ヘッセ行列を計算する必要はありません。代わりに、連続する勾配ベクトルを解析することでヘッセ行列を更新します。準ニュートン法は、多次元問題の最初の導関数の根を見つけるためのセカント法の一般化です。多次元ではセカント方程式は不完全決定であり、準ニュートン法は解を制約する方法が異なり、通常はヘッセ行列の現在の推定値に単純な低ランク更新を追加します。

最初の準ニュートン法は、アルゴンヌ国立研究所の物理学者ウィリアム・C・デイビッドンによって提案されました。彼は 1959 年に最初の準ニュートン法であるDFP 更新式を開発しました。これは後に 1963 年にフレッチャーとパウエルによって普及しましたが、今日ではほとんど使用されていません。現在最も一般的な準ニュートン法は、SR1 式(「対称ランク 1」)、BHHH法、広く普及しているBFGS 法(1970 年にブロイデン、フレッチャー、ゴールドファーブ、およびシャノによって独立に提案)、およびその低メモリ拡張であるL-BFGSです。ブロイデンのクラスは、DFP 法と BFGS 法の線形結合です。

SR1 式は、更新行列が正定値性を維持することを保証せず、不定問題に使用できます。ブロイデン法では、更新行列が対称である必要はなく、ヤコビ行列(ヘッセ行列ではなく) を更新することで、一般方程式 (勾配ではなく) の根を見つけるために使用されます。

ニュートン法に対する準ニュートン法の主な利点の 1 つは、ヘッセ行列(準ニュートン法の場合はその近似値)を逆行列化する必要がないことです。ニュートン法、および内点法などのその派生法では、ヘッセ行列を逆行列化する必要があり、これは通常、線形方程式系を解くことによって実装され、多くの場合、非常にコストがかかります。対照的に、準ニュートン法では通常、 の推定値を直接生成します。 ${\displaystyle B}$${\displaystyle B^{-1}}$

ニュートン法と同様に、関数の最小値を見つけるために2次近似を使用します。反復の周り のテイラー級数は${\displaystyle f(x)}$${\displaystyle f(x)}$

${\displaystyle f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{\mathrm {T} }\,\Delta x+{\frac {1}{2}}\Delta x^{\mathrm {T} }B\,\Delta x,}$

ここで ( ) は勾配、ヘッセ行列の近似である。^[4]この近似の勾配 ( に関して) は ${\displaystyle \nabla f}$${\displaystyle B}$${\displaystyle \Delta x}$

${\displaystyle \nabla f(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\,\Delta x,}$

この勾配をゼロに設定すると（最適化の目標）、ニュートンステップが実現されます。

${\displaystyle \Delta x=-B^{-1}\nabla f(x_{k}).}$

ヘッセ行列近似は、 ${\displaystyle B}$

${\displaystyle \nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\,\Delta x,}$

これはセカント方程式（勾配自体のテイラー級数）と呼ばれる。1次元以上では は不確定である。1次元では、 を解いて更新された値でニュートンステップを適用することは、セカント法と同等である。各種の準ニュートン法は、セカント方程式の解の選択において異なる（1次元では、すべての変種は同等である）。ほとんどの方法（ただし、ブロイデン法などの例外あり）は対称解（ ）を求める。さらに、以下に挙げる変種は、あるノルムで にできるだけ近い更新を見つけることによって動機付けられる可能性がある。つまり、 であり、 はノルムを定義する正定値行列である。を選択するための一般的な戦略はないが、おおよその初期値で迅速な収束を達成するのに十分な場合が多い。^{[5] は}正定値でなければならないことに注意。未知数は、現在のおおよそのヘッセ行列 を使用して計算されたニュートンステップを適用して更新される。 ${\displaystyle B}$${\displaystyle B}$${\displaystyle B^{T}=B}$${\displaystyle B_{k+1}}$${\displaystyle B_{k}}$${\displaystyle B_{k+1}=\operatorname {argmin} _{B}\|B-B_{k}\|_{V}}$${\displaystyle V}$${\displaystyle B_{0}=\beta I}$${\displaystyle \beta}$${\displaystyle B_{0}}$${\displaystyle x_{k}}$${\displaystyle B_{k}}$

• ${\displaystyle \Delta x_{k}=-\alpha _{k}B_{k}^{-1}\nabla f(x_{k})}$、ウルフ条件を満たすように選択された;${\displaystyle \alpha}$
• ${\displaystyle x_{k+1}=x_{k}+\Delta x_{k}}$;
• 新しい点における勾配は、${\displaystyle \nabla f(x_{k+1})}$

${\displaystyle y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})}$

は近似ヘッセ行列を更新するために使用されるか、またはシャーマン・モリソンの公式を使用してその逆行列を直接更新するために使用されます。 ${\displaystyle B_{k+1}}$${\displaystyle H_{k+1}=B_{k+1}^{-1}}$

• BFGS および DFP 更新の重要な特性は、が正定値であり、Wolfe 条件を満たすように選択される場合、も正定値であるということです。${\displaystyle B_{k}}$${\displaystyle \alpha_{k}}$${\displaystyle B_{k+1}}$

最も一般的な更新式は次のとおりです。

他の方法としては、ピアソン法、マコーミック法、パウエル対称ブロイデン（PSB）法、グリーンシュタット法などがあります。^[2]これらの再帰的な低ランク行列更新は、初期行列と低ランク補正として表すこともできます。これは、制約付き問題や大規模問題に特に効果的な コンパクト準ニュートン表現です。

が正定値ヘッセ行列を持つ凸二次関数である場合、準ニュートン法によって生成された行列は逆ヘッセ行列に収束すると予想されます。これは、最小変化更新に基づく準ニュートン法のクラスの場合に当てはまります。^[6]${\displaystyle f}$${\displaystyle B}$${\displaystyle H_{k}}$${\displaystyle H=B^{-1}}$

準ニュートン法の実装は、多くのプログラミング言語で利用可能です。

注目すべきオープンソース実装には以下のものがあります。

• GNU Octave は、信頼領域拡張を備えたBFGS の形式をそのfsolve機能で使用します。
• GNU 科学ライブラリは、Broyden-Fletcher-Goldfarb-Shanno ( BFGS ) アルゴリズムを実装しています。
• ALGLIB はC++ と C# で (L)BFGS を実装します。
• Rのoptim汎用最適化ルーチンは、を使用してBFGSmethod="BFGS"法を使用します。^[7]
• Scipy .optimizeにはfmin_bfgsがあります。PythonのSciPy拡張では、この関数には他のメソッドとともにBFGS実装が含まれています。^[8]scipy.optimize.minimize

注目すべき独自の実装には次のものがあります。

• Mathematicaには準ニュートンソルバーが含まれています。^[9]
• NAGライブラリには、準ニュートンアルゴリズムを使用して関数^[11]を最小化または最大化するためのいくつかのルーチン^{[10]が含まれています。}
• MATLABの最適化ツールボックスでは、fminunc関数は（他の方法の中でも）BFGS準ニュートン法を使用します。^[12]最適化ツールボックスの制約付き手法の多くは、 BFGSとその変形L-BFGSを使用します。^[13]

• Bonnans, JF; Gilbert, J. Ch.; Lemaréchal, C.; Sagastizábal , CA (2006).数値最適化: 理論と数値の側面(第 2 版). Springer. ISBN 3-540-35445-X。
• フレッチャー、ロジャー（1987）、最適化の実践的方法（第2版）、ニューヨーク：ジョン・ワイリー＆サンズ、ISBN 978-0-471-91547-8。
• Nocedal, Jorge; Wright, Stephen J. (1999)。「準ニュートン法」。数値最適化。ニューヨーク: Springer。pp. 192–221。ISBN 0-387-98793-2。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)。「セクション 10.9. 多次元における準ニュートン法または可変メトリック法」。数値レシピ: 科学計算の技法(第 3 版)。ニューヨーク: Cambridge University Press。ISBN 978-0-521-88068-8。
• スケールズ、LE（1985）。非線形最適化入門。ニューヨーク：マクミラン。pp.84-106。ISBN 0-333-32552-4。