5.3 牛頓法與擬牛頓法#

概念說明#

一階方法只看坡度，二階方法還看坡度的彎曲率。對 \(f\) 做二階泰勒展開：

\[ f(\mathbf{x}_k + \mathbf{d}) \approx f(\mathbf{x}_k) + \nabla f_k^T \mathbf{d} + \frac{1}{2}\mathbf{d}^T H_k \mathbf{d}, \qquad H_k = \nabla^2 f(\mathbf{x}_k) \]

對 \(\mathbf{d}\) 求極小得 \(\nabla f_k + H_k \mathbf{d} = 0\) ，即牛頓法的更新：

\[ \mathbf{x}_{k+1} = \mathbf{x}_k - H_k^{-1} \nabla f_k \]

這正是 3.2 節牛頓求根法作用在 \(\nabla f\) 上（求 \(\nabla f = 0\) 的根），因此同樣享有平方收斂：接近解時位數每步翻倍，且不依賴條件數。代價有三：(1) 每步要算 Hessian（ \(n \times n\) ， \(O(n^2)\) 儲存）；(2) 解線性系統 \(H_k \mathbf{d} = -\nabla f_k\) （稠密時 \(O(n^3)\) ）；(3) \(H_k\) 不保證正定——在非凸區牛頓方向可能「上坡」，需加修正（改用 \(H + \lambda I\) 、信賴域等）。

擬牛頓法的聰明之處：不真算 Hessian，而是利用每步的位移 \(\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k\) 與梯度差 \(\mathbf{y}_k = \nabla f_{k+1} - \nabla f_k\) 逐步學習曲率，維護一個近似 \(B_k \approx H_k\) 。曲率資訊藏在割線方程 \(B_{k+1} \mathbf{s}_k = \mathbf{y}_k\) 裡。BFGS 公式直接更新 \(B\) （或等價地更新逆近似 \(H^{-1}\) ，免解線性系統）：

\[ H_{k+1} = \left(I - \rho_k \mathbf{s}_k \mathbf{y}_k^T\right) H_k \left(I - \rho_k \mathbf{y}_k \mathbf{s}_k^T\right) + \rho_k \mathbf{s}_k \mathbf{s}_k^T, \qquad \rho_k = \frac{1}{\mathbf{y}_k^T \mathbf{s}_k} \]

配伍洛夫條件（Wolfe conditions）的線搜尋保證 \(B_k\) 保持正定。BFGS 達超線性收斂（ \(p \approx 1.7\) 量級），每步 \(O(n^2)\) 更新、 \(O(n)\) 矩陣-向量乘；L-BFGS 只保留最近 \(m\) 組 \((\mathbf{s}, \mathbf{y})\) （ \(m \approx 10\) ），記憶體降至 \(O(mn)\) ，是大型無約束最佳化的主力（scipy.optimize.minimize(method='L-BFGS-B')）。三者定位：牛頓法＝小維度、要極致收斂；BFGS＝中規模、通用首選；L-BFGS＝大規模、無約束。

生活類比#

下山的牛頓法像配備地形雷達：不只看腳下坡度，還量出坡度變化率，直接算出「彎谷底多遠」一次跨到位。BFGS 則像憑記憶學習的登山者：每次跨步後比較「預期坡度變化」與「實際感受」，逐漸在腦中建出地形模型——不需雷達，卻越走越準。

演算法步驟#

BFGS 流程：

初始化 \(\mathbf{x}_0\) 、逆 Hessian 近似 \(B_0^{-1} = I\) 。
方向 \(\mathbf{d}_k = -B_k^{-1}\nabla f_k\) （此處 \(B_k\) 表逆近似）。
線搜尋求 \(\alpha_k\) 滿足 Wolfe 條件。
\(\mathbf{s}_k = \alpha_k \mathbf{d}_k\) ， \(\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k\) ； \(\mathbf{y}_k = \nabla f_{k+1} - \nabla f_k\) 。
若 \(\mathbf{y}_k^T \mathbf{s}_k > 0\) ，用 BFGS 公式更新 \(B_k^{-1}\) 。
收斂（ \(\|\nabla f\|\) 小）則停。

Python 範例#

import numpy as np

def bfgs(f, g, x0, tol=1e-8, max_iter=100):
    x = np.array(x0, float)
    I = np.eye(len(x)); Binv = I.copy()      # 逆 Hessian 近似
    grad = g(x)
    for k in range(max_iter):
        if np.linalg.norm(grad) < tol:
            return x, k
        d = -Binv @ grad                     # 搜尋方向
        alpha, c1, decay = 1.0, 1e-4, 0.5    # 回溯線搜尋（簡化版）
        while f(x + alpha*d) > f(x) + c1*alpha*grad @ d:
            alpha *= decay
        s = alpha * d
        x_new = x + s
        y = g(x_new) - grad
        sy = y @ s
        if sy > 1e-12:
            rho = 1.0 / sy
            V = I - rho * np.outer(s, y)
            Binv = V @ Binv @ V.T + rho * np.outer(s, s)
        x, grad = x_new, g(x_new)
    return x, max_iter

# Rosenbrock 函數（經典難題）
f = lambda v: 100*(v[1]-v[0]**2)**2 + (1-v[0])**2
g = lambda v: np.array([-400*v[0]*(v[1]-v[0]**2) - 2*(1-v[0]),
                        200*(v[1]-v[0]**2)])
x, k = bfgs(f, g, [-1.2, 1.0])
print(f"BFGS 解: {x.round(6)}, f = {f(x):.2e}, 迭代 {k} 次")

from scipy.optimize import minimize
res = minimize(f, [-1.2, 1.0], jac=g, method="BFGS")
print("scipy BFGS:", res.x.round(6), "nit =", res.nit)

複雜度與收斂性分析#

牛頓法每步 \(O(n^3)\) （稠密解系統），平方收斂，迭代次數極少；適合 \(n\) 在數百以內、Hessian 可得且正定的情形。BFGS 每步 \(O(n^2)\) 、超線性收斂；L-BFGS 每步 \(O(mn)\) 、線性偏超的收斂率，適合百萬維。梯度法 \(O(n)\) 每步但迭代次數多且依賴 \(\kappa\) 。實務組合：深度學習因 Hessian 不可行且資料隨機，用 Adam；平滑確定性問題用 L-BFGS；小問題要高精度用牛頓。

練習#

對二次函數 \(f = \frac{1}{2}\mathbf{x}^T H \mathbf{x}\) （ \(H\) 對角），驗證 BFGS 至多 \(n\) 步收斂（精確線搜尋下），並解釋原因。
實作牛頓法（含 \(H + \lambda I\) 修正）解 Rosenbrock，比較與 BFGS 的迭代次數與單步成本。
用 scipy.optimize.minimize 的 L-BFGS-B 解 \(n = 1000\) 的對角二次函數，記錄 nit 與執行時間，與 GD、Adam 比較。