10.2 凸優化與梯度法#

概念說明#

非線性優化的世界分兩半：凸的與非凸的。凸函數滿足「任取兩點連線，函數值不高於連線上的值」（f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y)）。這個定義帶來一個決定性的禮物：凸函數的任何局部最小值就是全域最小值。因此凸優化只需「找到一個谷底」，不必擔心卡在別的山谷；而非凸問題（如神經網路訓練）則充滿局部極小與鞍點，只能反覆嘗試或靠高維的幸運。

最通用的凸優化方法是梯度下降法：站在山坡上，往負梯度方向走一小步。迭代式

x_{k+1} = x_k − η·∇f(x_k)

其中學習率 η 的選擇是成敗關鍵：太大會震盪甚至發散，太小收斂龜速。理論告訴我們：對 Lipschitz 梯度常數為 L 的凸函數，η = 1/L 可保證收斂；收斂速率分兩檔——一般凸函數 O(1/k)，強凸函數（像碗一樣彎）幾何收斂 O(q^k)，q 取決於條件數 κ（聯繫到 5.2 節）。條件數越大（碗越扁長），梯度下降走得越痛苦——等高線是細長橢圓時，梯度幾乎垂直於通往谷底的方向，路徑呈之字形。

升級路線因此清晰：動量法（累積歷史梯度，衝過平坦區）、牛頓法（用 Hessian 把二次曲線直接解掉，二次收斂但每步要解線性系統）、擬牛頓法（BFGS，用梯度歷史近似 Hessian，免二階導）。驗證是否收斂到真的谷底，最簡單的武器是梯度檢查：用 6.1 節的中央差分對比解析梯度——這是深度學習框架單元測試的標準作法。

演算法步驟#

選初始點 x₀、學習率 η、容許誤差 ε。
反覆：
計算梯度 g = ∇f(x_k)。
若 ‖g‖ < ε，停止（一階必要條件滿足）。
更新 x_{k+1} = x_k − η·g。
若 f 上升，把 η 減半（簡單回溯線搜尋）。
回傳 x 與 f(x)。

牛頓法版本：改更新 x_{k+1} = x_k − H⁻¹g，其中 H 是 Hessian（用 5.1 節解線性系統）。

Python 程式碼範例#

import numpy as np

rng = np.random.default_rng(0)

def gradient_descent(f, grad, x0, eta=0.1, tol=1e-10, max_iter=10000):
    x = np.array(x0, dtype=float)
    path = [x.copy()]
    for i in range(max_iter):
        g = grad(x)
        if np.linalg.norm(g) < tol:
            break
        fx_old = f(x)
        x_new = x - eta * g
        while f(x_new) > fx_old:          # 簡單回溯：步太大就減半
            eta /= 2
            x_new = x - eta * g
        x = x_new
        path.append(x.copy())
    return x, np.array(path), i + 1

def newton_min(f, grad, hess, x0, tol=1e-10, max_iter=50):
    x = np.array(x0, dtype=float)
    for i in range(max_iter):
        g, H = grad(x), hess(x)
        if np.linalg.norm(g) < tol:
            break
        step = np.linalg.solve(H, g)      # 第 5 章的 LU 在此上場
        x = x - step
    return x, i + 1

# --- 測試 1：病態二次函數（條件數 = 100） ---
Q = np.diag([1.0, 100.0])
f  = lambda x: 0.5 * x @ Q @ x
g_ = lambda x: Q @ x
h  = lambda x: Q

x, path, n = gradient_descent(f, g_, [9.0, 9.0])
print(f"梯度下降: x* ≈ {x}, 迭代 {n} 次")
xn, nn = newton_min(f, g_, h, [9.0, 9.0])
print(f"牛頓法  : x* ≈ {xn}, 迭代 {nn} 次")

# --- 梯度檢查：數值梯度 vs 解析梯度 ---
def num_grad(f, x, h=1e-6):
    x = np.asarray(x, dtype=float)
    g = np.zeros_like(x)
    for i in range(len(x)):
        e = np.zeros_like(x); e[i] = h
        g[i] = (f(x + e) - f(x - e)) / (2 * h)
    return g

xtest = rng.normal(size=2)
rosen_grad = lambda x: np.array([
    -400*x[0]*x[1] + 2*x[0] - 2,
    200*x[1] - 200*x[0]**2])   # Rosenbrock 梯度示範
print("梯度檢查最大誤差:",
      np.abs(num_grad(lambda v: v@Q@v/2, xtest) - Q@xtest).max())

# --- Rosenbrock（非凸經典）與 scipy 對照 ---
def rosen(x):
    return sum(100*(x[1:]-x[:-1]**2)**2 + (1-x[:-1])**2)
from scipy.optimize import minimize
r = minimize(rosen, [-1.2, 1.0], method="BFGS")
print(f"scipy BFGS: x* = {r.x}, f* = {r.fun:.2e}，呼叫 {r.nit} 次迭代")

誤差分析#

梯度下降的收斂理論（凸、L-smooth）：f(x_k) − f* ≤ 2‖x₀−x*‖²L/(k+2)，即 O(1/k)；強凸（參數 μ）時誤差 ≤ (1−μ/L)^k·初始誤差，κ = L/μ 直接決定幾何速率——病態問題（κ 大）是梯度法慢的根因，也是特徵縮放（preprocessing）重要的原因。牛頓法二次收斂（4.2 節結論直接搬來用），但每步成本 O(n³)（解 Hessian 系統）且 Hessian 非正定時失效；擬牛頓（BFGS）是折衷，每步 O(n²)。實務檢查清單：(1) 一開始永遠先做梯度檢查（容差 1e-7 量級）；(2) 學習率從 0.1 起試，回溯線搜尋當保險；(3) 收斂判據看梯度範數而非函數值變化（後者在平坦區會誤判收斂）；(4) 非凸問題多起點重啟（scipy.optimize.minimize 配多個 x0），並接受「好解」而非「最優解」。這些診斷習慣在 10.3 節的實戰中會全部派上用場。

練習#

對條件數 κ = 1, 10, 100 的二次函數（Q = diag(1, κ)）各跑梯度下降，記錄迭代次數，驗證次數 ≈ O(κ log(1/ε))。
實作動量法：v ← βv + ∇f，x ← x − ηv（β = 0.9），與純梯度下降在病態二次函數上比較迭代次數。
對 logistic 損失（10.3 節會用到）L(w) = Σ log(1+e^{−yᵢwᵀxᵢ}) 推導梯度，實作梯度下降 + 梯度檢查，並驗證凸性（Hessian 半正定）。