梯度下降：方向、步长与收敛

预备知识

本节使用梯度、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 曲率界给出有限步下降界，对称矩阵特征值给出正定二次函数的精确收敛判据；约束与停止证明需要分别检查。