梯度下降方法

搜索方向的一个自然选择是负梯度方向 $\mathrm{\Delta }x=-\mathrm{\nabla }f(x)$，由此得到的算法称为梯度算法​（gradient algorithm）或梯度下降方法​（gradient descent method）。

算法 9.3（梯度下降方法） 给定初始点 $x\in \mathrm{dom}f$。

1. 令 $\mathrm{\Delta }x:=-\mathrm{\nabla }f(x)$。
2. 直线搜索​：通过精确或回溯直线搜索选取步长 $t$。
3. 更新：$x:=x+t\mathrm{\Delta }x$。

重复上述步骤直至满足终止准则。

终止准则通常为 $\parallel \mathrm{\nabla }f(x){\parallel }_2⩽\eta$（$\eta$ 为很小的正数）。在大多数实现中，该条件在第 1 步之后（而不是更新之后）检查。

收敛性分析

采用简化记号 $x^{+}=x+t\mathrm{\Delta }x$（其中 $\mathrm{\Delta }x=-\mathrm{\nabla }f(x)$）。假设 $f$ 在 $S$ 上强凸，即存在正的常数 $m$ 和 $M$ 使 $mI⪯{\mathrm{\nabla }}^{2}f(x)⪯MI$ 对所有 $x\in S$ 成立。定义 $\tilde{f}:\mathbf{R}\to \mathbf{R}$：

$$\tilde{f}(t)=f(x-t\mathrm{\nabla }f(x))$$

即 $f$ 在负梯度方向上关于步长 $t$ 的函数。由 Hessian 上界不等式（取 $y=x-t\mathrm{\nabla }f(x)$）可得 $\tilde{f}$ 的二次上界：

$$\tilde{f}(t)⩽f(x)-t\parallel \mathrm{\nabla }f(x){\parallel }_2^2+\frac{M{t}^2}{2}\parallel \mathrm{\nabla }f(x){\parallel }_2^2$$

精确直线搜索分析

假设使用精确直线搜索，对上述不等式两端关于 $t$ 取极小。右端是简单二次函数，在 $t=1/M$ 处取最小值 $f(x)-(1/(2M))\parallel \mathrm{\nabla }f(x){\parallel }_2^2$，因此

$$f(x^{+})-p^{\star }⩽f(x)-p^{\star }-\frac{1}{2M}\parallel \mathrm{\nabla }f(x){\parallel }_2^2$$

再结合 $\parallel \mathrm{\nabla }f(x){\parallel }_2^2⩾2m(f(x)-p^{\star })$（由强凸性得到），可得

$$f(x^{+})-p^{\star }⩽(1-m/M)(f(x)-p^{\star })$$

递归应用该不等式，有

$$f(x^{(k)})-p^{\star }⩽c^k(f(x^{(0)})-p^{\star })$$

其中 $c=1-m/M<1$。这说明 $f(x^{(k)})$ 收敛于 $p^{\star }$。特别地，采用精确直线搜索的梯度方法至多经过

$$\frac{\log ((f(x^{(0)})-p^{\star })/ϵ)}{\log (1/c)}$$

次迭代即可使 $f(x^{(k)})-p^{\star }⩽ϵ$。

这个界虽然粗糙，却能揭示梯度方法的一些性质。分子 $\log ((f(x^{(0)})-p^{\star })/ϵ)$ 可解释为初始次优量与最终次优量之比的对数，说明所需迭代次数取决于初始点的好坏和最终要求的精度。分母 $\log (1/c)$ 是 $M/m$ 的函数，而 $M/m$ 正是 ${\mathrm{\nabla }}^{2}f(x)$（或者说下水平集）条件数的上界。当条件数上界 $M/m$ 很大时，$\log (1/c)=-\log (1-m/M)\approx m/M$，即所需迭代次数的界随 $M/m$ 近似线性增长。事实上，当 Hessian（在 $x^{\star }$ 附近）的条件数很大时，梯度方法确实需要大量迭代；反之，当下水平集较为各向同性（条件数较小）时收敛很快。

上述界表明误差 $f(x^{(k)})-p^{\star }$ 至少以几何级数的速度收敛到零。在迭代数值方法中，这称为线性收敛​（linear convergence），因为在对数-线性坐标下误差随迭代次数近似位于一条直线下方。

回溯直线搜索分析

对回溯直线搜索，可以证明回溯终止条件

$$\tilde{f}(t)⩽f(x)-\alpha t\parallel \mathrm{\nabla }f(x){\parallel }_2^2$$

在 $0⩽t⩽1/M$ 时总成立（利用 $-t+M{t}^2/2⩽-t/2$ 以及 $\alpha <1/2$）。因此回溯直线搜索要么终止于 $t=1$，要么终止于 $t⩾\beta /M$。综合两种情形可得

$$f(x^{+})⩽f(x)-min\{\alpha ,\beta \alpha /M\}\parallel \mathrm{\nabla }f(x){\parallel }_2^2$$

与精确直线搜索的情形一样处理，可以得到

$$f(x^{(k)})-p^{\star }⩽c^k(f(x^{(0)})-p^{\star }),c=1-min\{2m\alpha ,2\beta \alpha m/M\}<1$$

即 $f(x^{(k)})$ 至少以几何级数速度收敛于 $p^{\star }$，收敛率（至少部分地）依赖于条件数上界 $M/m$。在迭代方法的术语中，收敛至少是线性的。

例子

${\mathbf{R}}^2$ 中的二次问题

考虑 ${\mathbf{R}}^2$ 上的二次目标函数

$$f(x)=\frac{1}{2}(x_1^2+\gamma x_2^2),\gamma >0$$

显然最优点为 $x^{\star }=0$，最优值为 0。Hessian 为常矩阵，特征值为 1 和 $\gamma$，因此下水平集的条件数恰为 $max\{\gamma ,1/\gamma \}$，最紧的强凸常数取 $m=min\{1,\gamma \}$，$M=max\{1,\gamma \}$。

从 $x^{(0)}=(\gamma ,1)$ 出发采用精确直线搜索，可以导出迭代点的闭式表达式（见教材习题 9.6）：

$$x_1^{(k)}=\gamma {\left(\frac{\gamma -1}{\gamma +1}\right)}^k,x_2^{(k)}={(-\frac{\gamma -1}{\gamma +1})}^k$$

以及

$$f(x^{(k)})={\left(\frac{\gamma -1}{\gamma +1}\right)}^{2k}f(x^{(0)})$$

对这个简单例子，收敛恰好是线性的：误差每次迭代精确地按因子 $|(\gamma -1)/(\gamma +1){|}^2$ 缩减。$\gamma =1$ 时一次迭代即得精确解；$\gamma$ 接近 1（比如说在 1/3 到 3 之间）时收敛很快；而 $\gamma \gg 1$ 或 $\gamma \ll 1$ 时收敛非常慢。将实际收敛率 $((1-m/M)/(1+m/M){)}^2$ 与收敛分析给出的界 $1-m/M$ 比较，可以发现该界只保守约四倍，说明收敛率（及其上界）确实主要由下水平集的条件数决定。

待配图​：对应教材图 9.2 —— $f(x)=(1/2)(x_1^2+10x_2^2)$ 的若干条等高线，以及从 $x^{(0)}=(10,1)$ 出发的精确直线搜索梯度法迭代点；下水平集（椭圆）的条件数恰为 10。

${\mathbf{R}}^2$ 中的非二次问题

考虑 ${\mathbf{R}}^2$ 中的非二次例子：

$$f(x_1,x_2)=e^{x_1+3x_2-0.1}+e^{x_1-3x_2-0.1}+e^{-x_1-0.1}$$

采用参数 $\alpha =0.1$、$\beta =0.7$ 的回溯直线搜索，误差 $f(x^{(k)})-p^{\star }$ 近似按几何级数收敛，即近似线性收敛：误差从约 10 下降到约 ${10}^{-7}$ 用了 20 次迭代，每次迭代误差缩减因子约为 ${10}^{-8/20}\approx 0.4$。这与收敛分析的预测一致，因为该函数的下水平集条件数不太大。

改用精确直线搜索（同一问题、同一初始点）后收敛同样近似线性，但速度大约快一倍：15 次迭代中误差下降约 ${10}^{-11}$，每次迭代缩减因子约为 0.2。

待配图​：对应教材图 9.3、图 9.4、图 9.5 —— 该问题的等高线与回溯/精确直线搜索的迭代点，以及误差 $f(x^{(k)})-p^{\star }$ 随迭代次数 $k$ 的变化曲线。

${\mathbf{R}}^{100}$ 中的问题

考虑规模更大的例子：

$$f(x)=c^{\mathrm{\top }}x-\sum _{i=1}^m\log (b_i-a_i^{\mathrm{\top }}x)$$

其中 $m=500$，$n=100$。参数 $\alpha =0.1$、$\beta =0.5$ 的回溯直线搜索呈现两阶段收敛：前约 20 次迭代近似线性且较快（每次迭代缩减约 0.8），之后线性收敛变慢（每次迭代缩减约 0.94）；总体上误差在约 175 次迭代中下降约 ${10}^6$ 倍。精确直线搜索的收敛也近似线性，总体只稍快一些（约 140 次迭代下降 ${10}^6$ 倍）。

关于回溯参数的影响：固定 $\beta =0.5$ 而在 0.05 到 0.5 之间变化 $\alpha$，所需迭代次数在约 80（$\alpha$ 较大时）到约 170（$\alpha$ 较小时）之间变化；固定 $\alpha =0.1$ 而在 0.05 到 0.95 之间变化 $\beta$，所需迭代次数在约 80（$\beta \approx 0.5$）到约 200 之间变化。这些实验表明梯度方法在 $\alpha$ 较大（0.2–0.5）、$\beta \approx 0.5$ 时表现较好，但回溯参数对收敛的影响总体不大（不超过约两倍）。

待配图​：对应教材图 9.6 —— 该问题的误差随迭代次数变化曲线（回溯与精确直线搜索对比）。

梯度方法与条件数

将上述问题做变量替换 $x=T\overline{x}$，其中

$$T=\mathrm{diag}(1,{\gamma }^{1/n},{\gamma }^{2/n},\cdots ,{\gamma }^{(n-1)/n})$$

得到一族以 $\gamma$ 为参数、条件数不同的优化问题。实验表明：对角缩放仅为 10:1（$\gamma =10$）时，所需迭代次数就增长到一千次以上；缩放达到 20 倍以上时，梯度方法慢到基本不可用。最优点处 Hessian 的条件数随 $\gamma$ 大致按 $max\{{\gamma }^2,1/{\gamma }^2\}$ 变化，与所需迭代次数的变化方式非常相似。这说明条件数与收敛速度之间的关系是真实存在的现象，而不仅仅是收敛分析的产物。

待配图​：对应教材图 9.7、图 9.8 —— 所需迭代次数以及最优点处 Hessian 条件数随 $\gamma$ 的变化曲线。

结论

由这些数值实验可以得到如下结论：

• 梯度方法常常呈现近似线性收敛，即误差 $f(x^{(k)})-p^{\star }$ 近似按几何级数收敛到零。
• 回溯参数 $\alpha$、$\beta$ 的选择对收敛有明显但并不剧烈的影响。精确直线搜索有时能改善梯度方法的收敛，但效果不大（通常不值得为它增加实现代价）。
• 收敛速度强烈依赖于 Hessian（或下水平集）的条件数。即使条件数只是中等偏大（例如在几百的量级），收敛也可能非常慢；条件数更大时（例如 1000 或更多），梯度方法慢到在实际中毫无用处。

梯度方法的主要优点是简单；主要缺点是收敛速度对 Hessian 或下水平集的条件数过于敏感。