ニュートン法・準ニュートン法

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：無制約最適化　|　関連：ペナルティ法・障壁法

要点（BLUF）

ニュートン法は 2次のテイラー近似（放物面）を最小化して進む。曲率（ヘッセ行列）を使う。
ヘッセ行列が 非特異なら、最小点近傍で 2次収束（誤差が毎反復で2乗的に縮む）。
ヘッセの計算・逆行列が重いので、準ニュートン法（BFGS） が勾配差から近似ヘッセを更新する。

概念 ── 曲率まで使う

最急降下（無制約最適化）は1次情報（勾配）だけで、谷の歪みに弱い。ニュートン法は 2次情報（ヘッセ行列 $\nabla^2 f$ ） を使い、関数を放物面で近似してその底へ一気に進む。

$x_k$ まわりの2次テイラー近似：

f(x_k + d) \approx f(x_k) + \nabla f(x_k)^\top d + \tfrac12 d^\top \nabla^2 f(x_k)\, d

これを $d$ で最小化（ $d$ 微分＝0）すると ニュートンステップ：

d = -\bigl(\nabla^2 f(x_k)\bigr)^{-1} \nabla f(x_k), \qquad x_{k+1} = x_k + d

要するに：勾配を「曲率の逆数」でスケーリングする。きつい方向は小さく、緩い方向は大きく進むので、最急降下のジグザグ（条件数問題）が解消される。2次関数なら 1反復で厳密に最小に着く。

2次収束の威力

ヘッセ行列が最小点で非特異（正定値）かつリプシッツ連続なら、十分近い初期点から

\|x_{k+1} - x^\star\| \le C\,\|x_k - x^\star\|^2

が成り立つ。誤差が毎回2乗＝正しい桁数が反復ごとに倍増する、爆発的に速い収束。

Pythonで2次収束を確認

$f(x)=e^x - x$ 、最小は $f'(x)=e^x-1=0$ より $x=0$ 。 $f''(0)=1$ で非特異なので、ニュートン法は2次収束する。最急降下と並べる。

import numpy as np

def fp(x):  return np.exp(x) - 1     # 一階微分
def fpp(x): return np.exp(x)         # 二階微分(ヘッセ)

xn = 1.0   # ニュートン
xg = 1.0   # 最急降下
print(f"{'反復':>4} | {'ニュートン x':>14} | {'誤差|x|':>12} | {'最急降下 x':>12}")
for k in range(1, 7):
    xn = xn - fp(xn)/fpp(xn)     # ニュートンステップ
    xg = xg - 0.3*fp(xg)         # 最急降下(固定ステップ0.3)
    print(f"{k:>4} | {xn:>14.3e} | {abs(xn):>12.3e} | {xg:>12.6f}")

実行結果：

反復 | ニュートン x |     誤差|x| |  最急降下 x
   1 |    3.679e-01 |   3.679e-01 |    0.484515
   2 |    6.008e-02 |   6.008e-02 |    0.297499
   3 |    1.769e-03 |   1.769e-03 |    0.193553
   4 |    1.564e-06 |   1.564e-06 |    0.129487
   5 |    1.223e-12 |   1.223e-12 |    0.088014
   6 |    7.784e-17 |   7.784e-17 |    0.060413

ニュートン法の誤差は $0.37 \to 0.060 \to 0.0018 \to 1.6\text{e-}6 \to 1.2\text{e-}12$ と 毎回ほぼ2乗で縮み、6反復で機械精度に到達。最急降下は同じ反復数でまだ $0.060$ ── 1次収束（誤差が一定割合でしか減らない）。曲率情報の有無がこれほど効く。

準ニュートン法（BFGS）

ニュートン法の難点は、毎反復で ヘッセ行列 $\nabla^2 f$ の計算と逆行列が必要なこと（ $n$ 変数で $O(n^2)$ 要素・ $O(n^3)$ 逆行列）。準ニュートン法は、勾配の変化からヘッセ（の逆）を 近似的に更新する：

s_k = x_{k+1}-x_k,\quad y_k = \nabla f(x_{k+1}) - \nabla f(x_k)

を使い、セカント条件 $B_{k+1} s_k = y_k$ （割線がヘッセを近似）を満たすように $B$ を低ランク更新する。BFGS がその代表で、勾配だけから超1次収束を得る。大規模では記憶を抑えた L-BFGS が定番（scipy の minimize(method="BFGS"/"L-BFGS-B")）。

数式の直観的意味

ニュートン法は「勾配を曲率で割る」操作。最急降下が等高線の歪みに翻弄される（無制約最適化）のに対し、ヘッセの逆 $H^{-1}$ を掛けることで座標を実効的に「真円」に変換し、どの方向も等速で最小へ向かわせる ── 局所的にニュートン法は条件数を1にする前処理に等しい。2次収束は、放物面近似が最小点近傍で真の関数に急速に一致する（テイラー剰余が2次）ことの帰結。ただしヘッセが正定値でないと「下らない方向」へ進み得るので、実務は信頼領域や直線探索で安全化する。準ニュートンは「曲率を測り直す代わりに、歩いた履歴から推定する」── 計算と収束のトレードオフをうまく取った折衷案。

⚠️ よくある誤解・落とし穴

ニュートンは大域収束しない：遠い初期点では発散・鞍点へ進むことも。直線探索や信頼領域で減衰させる（damped Newton）。
ヘッセが非正定値だとニュートン方向が降下方向にならない。修正（正定値化）が要る。
2次収束は「最小点の近く」でのみ。序盤は最急降下的、終盤でニュートンが効く。
ヘッセの計算が高コスト／不可能なときは準ニュートン（BFGS）か、ヘッセ自由法（共役勾配）を使う。