5.1 梯度下降法#

概念說明#

梯度下降法（gradient descent）用最直白的直覺找極小值：函數在負梯度方向下降最快，於是

\[ \mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k) \]

\(\alpha_k\) 是步長（學習率），它幾乎決定了一切。對二次函數 \(f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T H \mathbf{x}\) （ \(H\) 對稱正定、特徵值 \(\lambda_1 \le \cdots \le \lambda_n\) ），誤差遞推為 \(\mathbf{e}_{k+1} = (I - \alpha H)\mathbf{e}_k\) ，收斂條件與速度由迭代矩陣的譜半徑決定：

\[ \rho = \max_i |1 - \alpha \lambda_i| < 1 \iff 0 < \alpha < \frac{2}{\lambda_{\max}} \]

最佳固定步長 \(\alpha^* = \frac{2}{\lambda_1 + \lambda_n}\) ，收斂率 \(\rho^* = \frac{\kappa - 1}{\kappa + 1}\) （ \(\kappa\) 為條件數）。這揭示兩大困境：

條件數病態： \(\kappa = 100\) 時每步只縮約 2%，且最優步長下誤差軌跡呈「之字形」——梯度方向與通往谷底的方向偏差越大，折返越多。4.3 節共軛梯度正是為治此病而生。
步長敏感： \(\alpha\) 略大於 \(2/\lambda_{\max}\) 就發散；太小則龜速。實務解法：理論估計（Lipschitz 常數 \(L\) ，取 \(\alpha = 1/L\) ）、線搜尋（每步試探最佳 \(\alpha\) ）、或學習率衰減表。

對非凸函數，梯度下降只能保證收斂到駐點（梯度為零處），可能是局部極小、極大或鞍點；高維空間中鞍點遠多於局部極小，加噪聲（隨機梯度）反而有助逃離。收斂階為線性（ \(p = 1\) ），這解釋了為何後續的動量、Adam、牛頓法皆以此為改良對象。

生活類比#

濃霧中下山：看不見谷底，只能感覺腳下最陡的下坡方向，跨一小步，再感覺、再跨。步幅太大會直接跨過山谷撞上對面坡，太小則天黑也走不到——學習率的兩難。

演算法步驟#

初始化 \(\mathbf{x}_0\) 、步長 \(\alpha\) 、容許值 \(\varepsilon\) 、最大迭代數。
計算梯度 \(\mathbf{g}_k = \nabla f(\mathbf{x}_k)\) ；若 \(\|\mathbf{g}_k\| < \varepsilon\) 停止。
更新 \(\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha \mathbf{g}_k\) 。
（可選）回溯線搜尋：若 \(f(\mathbf{x}_{k+1}) > f(\mathbf{x}_k) - c\,\alpha \|\mathbf{g}_k\|^2\) ，則 \(\alpha \leftarrow \alpha/2\) 重試。
回到步驟 2。

Python 範例#

以病態二次函數 \(f(x, y) = 50x^2 + y^2\) （ \(\kappa = 50\) ）示範之字形與步長效應：

import numpy as np

def grad_descent(H, x0, alpha, n_iter=60):
    x = np.array(x0, dtype=float)
    path = [x.copy()]
    for _ in range(n_iter):
        x = x - alpha * (H @ x)
        path.append(x.copy())
    return np.array(path)

H = np.diag([100.0, 2.0])           # 特徵值 100 與 2
kappa = H[0, 0] / H[1, 1]
alpha_opt = 2 / (H[0, 0] + H[1, 1])

for a, name in [(alpha_opt, "最佳步長"), (0.019, "接近發散"), (0.005, "過小")]:
    p = grad_descent(H, [10.0, 10.0], a)
    err = np.linalg.norm(p[-1])
    print(f"{name} (α={a:.4f}): 終點誤差 {err:.2e}, "
          f"x 座標抖動次數約 {np.sum(np.abs(np.diff(np.sign(p[:,0])))>0)}")

# 回溯線搜尋版（非凸函數 f = (x-1)^4 + y^2）
def f(v):  return (v[0]-1)**4 + v[1]**2
def g(v):  return np.array([4*(v[0]-1)**3, 2*v[1]])

x = np.array([-1.5, 2.0]); alpha = 1.0
for k in range(200):
    grad = g(x)
    if np.linalg.norm(grad) < 1e-8:
        break
    while f(x - alpha*grad) > f(x) - 1e-4*alpha*grad@grad:
        alpha *= 0.5
    x = x - alpha * grad
print(f"線搜尋版解: {x}, f = {f(x):.2e}, 迭代 {k+1} 次")

複雜度與收斂性分析#

每步成本 = 一次梯度計算（通常 \(O(n)\) 或更貴，視 \(f\) 而定）。強凸且 \(L\) -平滑時，固定步長 \(1/L\) 保證 \(f(\mathbf{x}_k) - f^* = O(1/k)\) （函數值），線性收斂於二次函數。對 \(\kappa\) 的依賴 \(O(\kappa \log(1/\varepsilon))\) 次迭代是梯度法的宿命；動量法將其改良為 \(O(\sqrt{\kappa} \log(1/\varepsilon))\) ，牛頓法更進一步擺脫條件數。選法準則：小而平滑→牛頓/BFGS；大規模或隨機資料→梯度下降＋動量/Adam。

練習#

對 \(\kappa = 100\) 的對角二次函數，實測最佳固定步長的理論收斂率 \((\kappa-1)/(\kappa+1)\) 是否吻合。
實作「最速下降＋精確線搜尋」（每步解一維最佳化），觀察相鄰兩步方向是否恆正交，並與固定步長比較迭代次數。
用梯度下降（含回溯線搜尋）極小化 Rosenbrock 函數 \(f(x,y) = 100(y-x^2)^2 + (1-x)^2\) ，體會狹長山谷為何是梯度法的噩夢。