梯度下降：方向、步長與收斂

預備知識

本節使用梯度、Hessian 矩陣、多元鏈式法則、對稱矩陣的特徵值和一元 Taylor 定理。在分析有限步之前，請複習多元 Taylor 多項式。

5.3 為甚麼負梯度在局部向下

設 $f$ 在 $x$ 可微。對單位方向 $u$，$D_uf(x)=\nabla f(x)^Tu$。由 Cauchy–Schwarz 不等式，它至少為 $-\|\nabla f(x)\|$；當梯度非零且 $u=-\nabla f/\|\nabla f\|$ 時取等號。因此，在所選歐氏坐標下，負梯度是一階意義下降最快的方向。

坐標度量很重要：改變輸入的尺度會改變哪些方向具有單位長度。以貨幣和利率比例為坐標時，未選擇尺度之前，梯度方向沒有不變的物理意義。

梯度下降使用

$$x_{k+1}=x_k-\eta_k\nabla f(x_k),\qquad\eta_k>0.$$

在非駐點沿該方向的方向導數為負，但任意有限步可能越過低點並使目標增大。要確定步長條件，需要曲率信息。

5.4 推導有限步下降界

設 $f$ 在包含整個相關線段的開集上為 $C^1$，梯度在該線段上的 Lipschitz 常數為 $L>0$，即 $\|\nabla f(x+ts)-\nabla f(x)\|\le Lt\|s\|$ 對 $0\le t\le1$ 成立。若原 Lipschitz 常數為零，可任取正常數作為上界。由一元微積分基本定理的線積分形式，

$$f(x+s)-f(x)=\int_0^1\nabla f(x+ts)^Ts\,dt.$$

減去 $\nabla f(x)^Ts$，使用 Cauchy–Schwarz 不等式並對 $Lt\|s\|^2$ 積分，得到下降引理

$$f(x+s)\le f(x)+\nabla f(x)^Ts+\frac L2\|s\|^2.$$

取 $s=-\eta\nabla f(x)$，

$$f(x-\eta\nabla f(x))\le f(x)-\eta\left(1-\frac{L\eta}{2}\right)\|\nabla f(x)\|^2.$$

因此，在整一步均滿足假設時，$0<\eta<2/L$ 保證非駐點處嚴格下降。若一步離開局部曲率界成立的區域，就不能用該局部界為此步提供保證。

例 2：安全步與過大步。 對 $f(x,y)=(x^2+9y^2)/2$，梯度為 $(x,9y)^T$，且全局有 $L=9$。取常數步長 $\eta=0.1$，

$$x_{k+1}=0.9x_k,\qquad y_{k+1}=0.1y_k.$$

從 $(1,1)$ 出發，第一次迭代為 $(0.9,0.1)$，目標值為 $0.45$，而初值為五。第二次為 $(0.81,0.01)$，目標值為 $0.3285$。若 $\eta=0.3$，第二坐標的乘數是 $-1.7$；儘管初始方向向下，該分量的絕對值仍會增長。

5.5 正定二次函數的精確收斂

設 $f(x)=\frac12x^THx-b^Tx+c$，其中 $H$ 對稱正定，且使用固定常步長 $\eta$。其唯一最小點為 $x_*=H^{-1}b$。記誤差 $e_k=x_k-x_*$，則

$$e_{k+1}=(I-\eta H)e_k.$$

取 $H$ 的一組標準正交特徵向量基。每個誤差坐標乘以 $1-\eta\lambda_i$。因此，每個初始點都收斂到 $x_*$，當且僅當所有特徵值滿足 $|1-\eta\lambda_i|<1$，也就是

$$0<\eta<2/\lambda_{\max}.$$

在上端點，最大特徵值對應的分量可能振盪而不衰減。低於該範圍時，零步或負步不一定使目標下降；高於該範圍時，某些分量增長。當某個坐標方向比其他方向平坦得多時，條件數 $\lambda_{max}/\lambda_{min}$ 也解釋了收斂緩慢的原因。

對該二次函數，$\|\nabla f(x)\|=\|H(x-x_*)\|\ge\lambda_{min}\|x-x_*\|$。因此，梯度範數停止規則只有在已知正的特徵值下界時才能給出到最小點的距離界。因選擇極小 $\eta$ 而得到的小步長，本身不能證明接近最小點。

5.6 約束與停止條件

無約束步可能離開可行集。例如，減去梯度並不能自動保持權重非負。等式約束可能需要投影方向、代入法或單獨的約束算法。第 2 章的乘數條件與無約束梯度下降公式回答不同的問題。

數值報告應寫明目標、起點、坐標尺度、步長規則、停止準則，以及確有依據的誤差或下降界。“程序停止”不是數學上的收斂證明；非凸問題的駐點也可能是鞍點而非所求最小點。

5.7 練習

P02. 求 $f(x,y)=x^2+2y^2$ 的梯度下降更新式。

P03. 對 $f(x,y)=x^2+y^2$，證明從 $(1,0)$ 以 $\eta=2$ 走一步會使目標增大。

P05. 對 $f=(x^2+4y^2)/2$，求從所有起點都收斂的全部常數步長。

P06. 對同一目標，從 $(2,1)$ 取 $\eta=1/4$，計算前兩次迭代及目標值。

P08. 對 $f(x)=\frac12x^THx-b^Tx+c$，其中 $H=\operatorname{diag}(2,5)$，若 $\|\nabla f(x)\|\le0.001$，求到該二次函數最小點的距離界。

P09. 對對稱正定二次函數直接推導有限步下降引理，並將曲率界與最大特徵值比較。

P10. 解釋為甚麼負梯度方向的一步不一定保持約束 $x+y=1$。在 $(x,y)$、梯度為 $(g_1,g_2)$ 時，推導這一特定步保持總和的條件。

5.8 完整解答

P02. 梯度為 $(2x,4y)^T$，故常數步長下 $(x_{k+1},y_{k+1})=((1-2\eta)x_k,(1-4\eta)y_k)$。

P03. 在 $(1,0)$ 的梯度是 $(2,0)$，一步到 $(-3,0)$，目標由一增至九。一階向下的方向不能保證過大的有限步仍下降。

P05. 特徵值為一和四，所有初始點收斂當且僅當 $0<\eta<1/2$。

P06. 更新乘數分別為 $3/4$ 和零。兩次迭代為 $(3/2,0)$、$(9/8,0)$，目標值分別為 $9/8$、$81/128$，均低於初值四。

P08. 最小特徵值為二，故距離至多為 $0.001/2=0.0005$。

P09. 精確增量是 $f(x+s)-f(x)=\nabla f(x)^Ts+s^THs/2$。由 $s^THs\le\lambda_{max}\|s\|^2$，下降引理在 $L=\lambda_{max}$ 時成立。代入 $s=-\eta\nabla f$ 得到同一充分下降界；特徵坐標遞推給出所有起點收斂的精確範圍。

P10. 新的總和為 $x+y-\eta(g_1+g_2)=1-\eta(g_1+g_2)$。步長為正時，它保持為一當且僅當 $g_1+g_2=0$；一般梯度未必滿足此切向條件。

總結

負梯度只有在所選度量和一階意義下才是最陡下降方向。Lipschitz 曲率界給出有限步下降界，對稱矩陣特徵值給出正定二次函數的精確收斂判據；約束與停止證明需要分別檢查。