最適化におけるニュートン法

微積分学において、ニュートン法（ニュートン・ラフソン法とも呼ばれる）は、微分可能な関数の根を求めるための反復法である。${\displaystyle f}$方程式の解である${\displaystyle f(x)=0}$しかし、2回微分可能なものを最適化するには${\displaystyle f}$私たちの目標は、${\displaystyle f'}$したがって、その導関数にニュートン法を適用することができる。${\displaystyle f'}$解決策を見つける${\displaystyle f'(x)=0}$臨界点としても知られる${\displaystyle f}$これらの解は、最小値、最大値、または鞍点となる可能性があります。詳細については、「臨界点（数学） 」の「複数の変数」のセクション、およびこの記事の「幾何学的解釈」のセクションを参照してください。これは、関数の（グローバル）最小値を見つけることを目的とする最適化において重要です。${\displaystyle f}$。

最適化における中心的な問題は、関数の最小化です。まず、単変数関数、すなわち単一の実変数の関数について考えてみましょう。より一般的で実用的な多変数関数については、後ほど検討します。

2回微分可能な関数が与えられた場合${\displaystyle f:\mathbb {R} \to \mathbb {R} }$我々は最適化問題の解決を目指す

${\displaystyle \min _{x\in \mathbb {R} }f(x).}$

ニュートン法は、数列を構築することによってこの問題を解決しようと試みる。${\displaystyle \{x_{k}\}}$最初の推測（出発点）から${\displaystyle x_{0}\in \mathbb {R} }$最小値に収束する${\displaystyle x_{*}}$の${\displaystyle f}$2次テイラー近似のシーケンスを使用することにより${\displaystyle f}$反復の周り。f の2 次テイラー展開の周り${\displaystyle x_{k}}$は

${\displaystyle f(x_{k}+t)\approx f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}.}$

次の反復${\displaystyle x_{k+1}}$は、この二次近似を最小化するように定義される。 ${\displaystyle t}$、そして設定${\displaystyle x_{k+1}=x_{k}+t}$2階微分が正の場合、2次近似は凸関数となる。${\displaystyle t}$、そしてその最小値は導関数をゼロに設定することで求めることができる。

${\displaystyle \displaystyle 0={\frac {\rm {d}}{{\rm {d}}t}}\left(f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}\right)=f'(x_{k})+f''(x_{k})t,}$

最低限の条件は

${\displaystyle t=-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

すべてをまとめると、ニュートン法は反復を実行します。

${\displaystyle x_{k+1}=x_{k}+t=x_{k}-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

ニュートン法の幾何学的解釈は、各反復において、放物線をグラフに当てはめることに相当する。${\displaystyle f(x)}$試算値において${\displaystyle x_{k}}$その点におけるグラフと同じ傾きと曲率を持ち、その後その放物線の最大値または最小値（高次元では鞍点となる場合もある）まで進む。以下を参照。注意：${\displaystyle f}$二次関数である場合、正確な極値は1ステップで求められます。

上記の反復スキームは、以下のように一般化できます。${\displaystyle d>1}$導関数を勾配に置き換えることで次元を変換します（著者によって勾配の表記法が異なります。${\displaystyle f'(x)=\nabla f(x)=g_{f}(x)\in \mathbb {R} ^{d}}$）、およびヘッセ行列の逆行列との2階微分の逆数（著者によってヘッセ行列の表記法は異なる）${\displaystyle f''(x)=\nabla ^{2}f(x)=H_{f}(x)\in \mathbb {R} ^{d\times d}}$）このようにして反復スキームが得られる。

${\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k}),\qquad k\geq 0.}$

ニュートン法は、しばしば小さなステップサイズを含むように修正される。${\displaystyle 0<\gamma \leq 1}$の代わりに${\displaystyle \gamma =1}$:

${\displaystyle x_{k+1}=x_{k}-\gamma [f''(x_{k})]^{-1}f'(x_{k}).}$

これは、メソッドの各ステップでウルフ条件、あるいはより単純で効率的なアルミホ条件が満たされるようにするためによく行われます。ステップサイズが1以外の場合、このメソッドは緩和ニュートン法または減衰ニュートン法と呼ばれることがよくあります。

fがリプシッツヘッセ行列を持つ強凸関数である場合、${\displaystyle x_{0}}$に十分近い${\displaystyle x_{*}=\arg \min f(x)}$シーケンス${\displaystyle x_{0},x_{1},x_{2},\dots }$ニュートン法によって生成された値は、（必然的に一意な）最小値に収束する。 ${\displaystyle x_{*}}$の${\displaystyle f}$2乗的に速い。^{[ 1 ]} つまり、

${\displaystyle \|x_{k+1}-x_{*}\|\leq {\frac {1}{2}}\|x_{k}-x_{*}\|^{2},\qquad \forall k\geq 0.}$

高次元におけるヘッセ行列の逆行列を求めてニュートン方向を計算する${\displaystyle h=-(f''(x_{k}))^{-1}f'(x_{k})}$これはコストのかかる操作になる可能性があります。このような場合、ヘッセ行列を直接逆行列化するのではなく、ベクトルを計算する方が良いでしょう。${\displaystyle h}$連立一次方程式の解として

${\displaystyle [f''(x_{k})]h=-f'(x_{k})}$

これは、さまざまな因数分解によって解くか、反復法を用いて近似的に（ただし非常に高い精度で）解くことができます。これらの方法の多くは、特定のタイプの方程式にのみ適用可能です。たとえば、コレスキー分解と共役勾配法は、次の場合にのみ機能します。${\displaystyle f''(x_{k})}$は正定値行列です。これは制約のように思えるかもしれませんが、多くの場合、何かがうまくいっていないことを示す有用な指標となります。たとえば、最小化問題に取り組んでいて、${\displaystyle f''(x_{k})}$が正定値でない場合、反復計算は最小値ではなく鞍点に収束します。

一方、制約付き最適化（例えば、ラグランジュ乗数を用いる場合）を行うと、問題は鞍点探索問題になる可能性があり、その場合、ヘッセ行列は対称不定となり、解は${\displaystyle x_{k+1}}$次のような方法で行う必要があります。${\displaystyle LDL^{\top }}$コレスキー分解法または共役残差法の変種。

また、勾配の変化からヘッセ行列（またはその逆行列）の近似値を構築する、さまざまな準ニュートン法も存在する。

ヘッセ行列が非可逆行列に近い場合、逆ヘッセ行列は数値的に不安定になり、解が発散する可能性があります。この場合、過去にはいくつかの回避策が試みられてきましたが、問題によって成功の度合いは様々でした。例えば、補正行列を追加することでヘッセ行列を修正することができます。${\displaystyle B_{k}}$作るために${\displaystyle f''(x_{k})+B_{k}}$正定値。一つのアプローチはヘッセ行列を対角化し、${\displaystyle B_{k}}$ となることによって${\displaystyle f''(x_{k})+B_{k}}$はヘッセ行列と同​​じ固有ベクトルを持つが、各負の固有値は に置き換えられている。${\displaystyle \epsilon >0}$。

レーベンバーグ・マルカート法（近似ヘッセ行列を使用する）で利用されるアプローチは、ヘッセ行列にスケーリングされた単位行列を追加することである。${\displaystyle \mu I}$必要に応じて、各反復でスケールを調整します。${\displaystyle \mu }$ヘッセ行列が小さい場合、反復処理はステップサイズを指定した勾配降下法のように動作します。${\displaystyle 1/\mu }$その結果、ヘッセ行列が有用な情報を提供しない場合、収束速度は遅くなるものの、より信頼性の高い収束が得られる。

ニュートン法は、その原典版にはいくつかの注意点がある。

1. ヘッセ行列が逆行列を持たない場合、この方法は機能しません。これは、ヘッセ行列の逆行列を取ることを必要とするニュートン法の定義からも明らかです。
2. 全く収束しない場合もあり、複数の点を持つサイクルに入る可能性があります。§ニュートン方向の計算を参照してください。
3. § 幾何学的解釈に従って、局所最小値ではなく鞍点に収束する可能性があります。

前述の準ニュートン法やレーベンバーグ・マルカート法など、ニュートン法の一般的な改良版にも注意点がある。

例えば、コスト関数が（強く）凸であり、ヘッセ行列が大域的に有界またはリプシッツ連続であることが通常要求されます。これは、この記事の「収束」のセクションで言及されています。レーベンバーグ・マルカートアルゴリズムの参考文献にあるレーベンバーグとマルカートの論文を見ると、この方法の元のソースであるレーベンバーグの論文には基本的に理論的な分析がなく、マルカートの論文は局所的な状況のみを分析し、大域的な収束結果を証明していないことがわかります。勾配降下法のバックトラッキング線探索と比較することができます。これは、より一般的な仮定の下で優れた理論的保証があり、ディープニューラルネットワークなどの実際の大規模な問題で実装してうまく機能します。

• 準ニュートン法
• 勾配降下法
• ガウス・ニュートン法
• レーベンバーグ・マルカートアルゴリズム
• トラスト地域
• 最適化
• ネルダー・ミード法
• 自己一致関数- ニュートン法による大域的収束率が非常に高い関数。^{[ 2 ]：第6.2節}

• アヴリエル、モルデカイ（2003）。非線形計画法：分析と手法。ドーバー出版。ISBN 0-486-43227-0。
• Bonnans, J.  Frédéric; Gilbert, J.  Charles; Lemaréchal, Claude ; Sagastizábal, Claudia  A. (2006). Numerical optimization: Theoretical and practical aspects . Universitext (1997年フランス語版の翻訳版、第2版改訂版 ). Berlin: Springer-Verlag. doi : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-XMR 2265882 .​ 
• フレッチャー、ロジャー（1987）。最適化の実践的方法（第2 版）。ニューヨーク：ジョン・ワイリー・アンド・サンズ。ISBN 978-0-471-91547-8。
• Givens, Geof H.; Hoeting, Jennifer A. (2013).計算統計学. ホーボーケン、ニュージャージー州: John Wiley & Sons. pp. 24–58 . ISBN  978-0-470-53331-4。
• ノセダル、ホルヘ；ライト、スティーブン J. (1999).数値最適化. Springer-Verlag. ISBN 0-387-98793-2。
• Kovalev, Dmitry; Mishchenko, Konstantin; Richtárik, Peter (2019). "単純な局所線形二次レートを持つ確率的ニュートン法と三次ニュートン法". arXiv : 1912.01597 [ cs.LG ].

• コレンブルム、ダニエル (2015 年 8 月 29 日)。「ニュートン・ラフソン可視化 (1D)」。ブロック。 ffe9653768cb80dfc0da。