梯度下降法（Gradient Descent）也称为最速下降法（Steepest Descent），是法国数学家奥古斯丁·路易·柯西 (Augustin Louis Cauchy) 于1847年提出来，它是最优化方法中最经典和最简单的一阶方法之一。梯度下降法由于其较低的复杂度和简单的操作而在很多领域得到广泛研究和应用，如机器学习。由梯度下降法衍生了许多其他算法，如次梯度下降法，近端梯度下降法，随机梯度下降法，回溯梯度发，动量加速梯度法等等。本文只介绍最基础的梯度下降法原理和理论分析，与此同时，通过仿真来说明梯度下降法的优势和缺陷。其他重要的梯度下降衍生方法会持续更新，敬请关注。

在直角坐标系下，标量函数 f : R n ↦ R f:\mathbb{R}^{n}\mapsto \mathbb{R} f:Rn↦R 的梯度 ∇ f \nabla f ∇f 定义为：

∇ f = ∂ f ∂ x i + ∂ f ∂ y j + ∂ f ∂ z k \nabla f = \frac{{\partial f}}{{\partial x}}{\bf{i}} + \frac{{\partial f}}{{\partial y}}{\bf{j}} + \frac{{\partial f}}{{\partial z}}{\bf{k}} ∇f=∂x∂f​i+∂y∂f​j+∂z∂f​k

其中 i \bf{i} i， j \bf{j} j， k \bf{k} k 表示在三个维度的单位方向矢量。 ∂ f ∂ x \frac{{\partial f}}{{\partial x}} ∂x∂f​， ∂ f ∂ y \frac{{\partial f}}{{\partial y}} ∂y∂f​， ∂ f ∂ z \frac{{\partial f}}{{\partial z}} ∂z∂f​ 为对应的偏导数。

梯度下降法就是以梯度为搜索方向的迭代优化算法

对于无约束优化问题：

arg ⁡ min ⁡ x ∈ R n f ( x ) \mathop {\arg \min }\limits_{{\bf{x}} \in {\mathbb{R}^n}} f({\bf{x}}) x∈Rnargmin​f(x)

函数 f f f 可以是凸的，也可以是非凸的，在高维非凸的情况下，解这样一个优化问题可能很难计算解析解，而我们可以使用数值迭代法来求得一个局部最优解。这样的迭代方法有很多，比如本文讲的梯度下降法，牛顿迭代法，共轭梯度法等，其中梯度下降法利用了梯度信息，属于一阶方法，牛顿法利用了海森矩阵，属于二阶方法，而共轭梯度法是介于这二者之间的方法。

我们先来看看梯度下降法是什么样子的，梯度下降法的迭代公式为： x k + 1 = x k + α k d k {{\bf{x}}^{k + 1}} = {{\bf{x}}^k} + {\alpha _k}{{\bf{d}}^k} xk+1=xk+αk​dk 式 (2) 中 x k {{\bf{x}}^k} xk 表示第 k k k 次迭代时的位置， α k \alpha_k αk​ 表示第 k k k 次迭代的步长， d k \bf{d}_k dk​ 表示第 k k k 次迭代的寻优方向。梯度下降法就是在给定初始点 x 0 \bf{x}_0 x0​ 后，通过不断沿着寻优方向迭代找到局部最优值的过程。

那么梯度下降法中的步长和方向怎么确定呢？ 一般来说，步长的选择有多种方式，可以是固定的，也可以是随着迭代过程而变化的 寻优方向则是 f ( x ) f(\bf{x}) f(x) 在点 x k \bf{x}_k xk​ 处的梯度反方向，

以求解线性方程 y = A x {\bf{y}} = {\bf{Ax}} y=Ax 为例， 假设目标函数为 f ( x ) = 1 2 ∥ A x − y ∥ 2 2 f({\bf{x}}) = \frac{1}{2}\left\| {{\bf{Ax}} - {\bf{y}}} \right\|_2^2 f(x)=21​∥Ax−y∥22​ 我们知道目标函数的梯度就是梯度下降法的寻优方向，所以我们可以先求目标函数的导数： g = A T ( A x − y ) {\bf{g}} = {{\bf{A}}^T}({\bf{Ax}} - {\bf{y}}) g=AT(Ax−y) 在 x k {\bf{x}}_{k} xk​ 处，将 x k + 1 = x k + α k g k {{\bf{x}}_{k + 1}} = {{\bf{x}}_k} + {\alpha _k}{{\bf{g}}_k} xk+1​=xk​+αk​gk​ 代入上式中，得到： f ( x k + 1 ) = 1 2 ∥ A ( x k + α k g k ) − y ∥ 2 2 f({{\bf{x}}_{k + 1}}) = \frac{1}{2}\left\| {{\bf{A}}({{\bf{x}}_k} + {\alpha _k}{{\bf{g}}_k}) - {\bf{y}}} \right\|_2^2 f(xk+1​)=21​∥A(xk​+αk​gk​)−y∥22​ 接下来，为了求 x k {\bf{x}}_{k} xk​ 处的步长，我们介绍一种精确线搜索（Exact Line Search）方法， 精确线搜索方法的原理是沿着 x k + α k g k {{\bf{x}}_k} + {\alpha _k}{{\bf{g}}_k} xk​+αk​gk​ 方向最小化目标函数，从而得到此时的 α k {\alpha _k} αk​。也就是求解这样一个问题： α k = arg ⁡ min ⁡ α f ( x k + α k g k ) {\alpha _k} = \mathop {\arg \min }\limits_\alpha f\left( {{{\bf{x}}_k} + {\alpha _k}{{\bf{g}}_k}} \right) αk​=αargmin​f(xk​+αk​gk​) 求解这个优化问题，我们只需对 α k {\alpha _k} αk​ 求导，并且令结果等于0，也就是： ∂ f ( x k + 1 ) ∂ α k = 0 \frac{{\partial f({{\bf{x}}_{k + 1}})}}{{\partial {\alpha _k}}} = 0 ∂αk​∂f(xk+1​)​=0 ( A g k ) T ( A ( x k + α k g k ) − y ) = 0 {\left( {{\bf{A}}{{\bf{g}}_k}} \right)^T}\left( {{\bf{A}}({{\bf{x}}_k} + {\alpha _k}{{\bf{g}}_k}) - {\bf{y}}} \right) = 0 (Agk​)T(A(xk​+αk​gk​)−y)=0 α k ( A g k ) T A g k + g k T A T ( A x k − y ) = 0 {\alpha _k}{\left( {{\bf{A}}{{\bf{g}}_k}} \right)^T}{\bf{A}}{{\bf{g}}_k} + {\bf{g}}_k^T{{\bf{A}}^T}\left( {{\bf{A}}{{\bf{x}}_k} - {\bf{y}}} \right) = 0 αk​(Agk​)TAgk​+gkT​AT(Axk​−y)=0 α k ( A g k ) T A g k = g k T g k {\alpha _k}{\left( {{\bf{A}}{{\bf{g}}_k}} \right)^T}{\bf{A}}{{\bf{g}}_k} = {\bf{g}}_k^T{{\bf{g}}_k} αk​(Agk​)TAgk​=gkT​gk​ α k = g k T g k ( A g k ) T A g k {\alpha _k} = \frac{{{\bf{g}}_k^T{{\bf{g}}_k}}}{{{{\left( {{\bf{A}}{{\bf{g}}_k}} \right)}^T}{\bf{A}}{{\bf{g}}_k}}} αk​=(Agk​)TAgk​gkT​gk​​ 当然，还有其他的一些步长选择方法，比如回溯线搜索方法等，在这里就不再展开。 寻优方向和步长都得到了，那么矩阵形式的梯度下降法的迭代公式可以总结为： x k + 1 = x k + α k A T ( A x k − y ) {{\bf{x}}_{k + 1}} = {{\bf{x}}_k} + {\alpha _k}{{\bf{A}}^T}({\bf{A}}{{\bf{x}}_k} - {\bf{y}}) xk+1​=xk​+αk​AT(Axk​−y)

可以证明，采用精确线性搜索的最速下降法的收敛速度是线性的。对于极小化正定二次函数，梯度下降法产生的序列满足 f ( x k + 1 ) − f ( x ∗ ) f ( x k ) − f ( x ∗ ) ≤ ( λ 1 − λ n λ 1 + λ n ) 2 = ( κ − 1 κ + 1 ) 2 \frac{{f({x_{k + 1}}) - f({x^*})}}{{f({x_k}) - f({x^*})}} \le {\left( {\frac{{{\lambda _1} - {\lambda _n}}}{{{\lambda _1} + {\lambda _n}}}} \right)^2} = {\left( {\frac{{\kappa - 1}}{{\kappa + 1}}} \right)^2} f(xk​)−f(x∗)f(xk+1​)−f(x∗)​≤(λ1​+λn​λ1​−λn​​)2=(κ+1κ−1​)2 这里 λ 1 {{\lambda _1}} λ1​ 和 λ 1 {{\lambda _1}} λ1​ 分别表示矩阵 A T A {{\bf{A}}^T}{\bf{A}} ATA 的最大和最小特征值， κ = λ 1 λ n \kappa = \frac{{{\lambda _1}}}{{{\lambda _n}}} κ=λn​λ1​​ 表示矩阵 A T A {{\bf{A}}^T}{\bf{A}} ATA 的条件数。可以看出梯度下降法的收敛速度是与对称矩阵 A T A {{\bf{A}}^T}{\bf{A}} ATA 的条件数有关的，条件数越小收敛速度越快。如果矩阵的条件数远大于1，则说明矩阵是ill-conditioned，反之，如果矩阵的条件数等于1，则说明矩阵是well-conditioned。

如果函数 f f f 在定义域内是利普希兹连续（Lipschitz continuous）的，则有： ∥ f ( x ) − f ( y ) ∥ ≤ L ∥ x − y ∥ \left\| {f(x) - f(y)} \right\| \le L\left\| {x - y} \right\| ∥f(x)−f(y)∥≤L∥x−y∥ 如果函数 f f f 的导数符合Lipschitz continuous，那么有： ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ≤ L ∥ x − y ∥ \left\| {\nabla f(x) - \nabla f(y)} \right\| \le L\left\| {x - y} \right\| ∥∇f(x)−∇f(y)∥≤L∥x−y∥ 其中 L > 0 L>0 L>0 称为利普希兹常数。

在梯度满足利普希兹连续条件下，梯度下降法的收敛性如下：

步长为 α ≤ 1 L \alpha \le \frac{1}{L} α≤L1​ 的梯度下降法满足： f ( x k ) − f ( x ∗ ) ≤ ∥ x 0 − x ∗ ∥ 2 2 α k f({x_k}) - f({x^*}) \le \frac{{{{\left\| {{x_0} - {x^*}} \right\|}^2}}}{{2\alpha k}} f(xk​)−f(x∗)≤2αk∥x0​−x∗∥2​ 也就是说梯度下降法的收敛速度为 O ( 1 k ) O\left( {\frac{1}{k}} \right) O(k1​)，只需要 O ( 1 ε ) O\left( {\frac{1}{\varepsilon }} \right) O(ε1​) 次迭代即可达到 $f({x_k}) - f({x^*}) \le \varepsilon $。

上述结论的证明见参考文献[1]，这里给一个简单的描述。 如果 ∇ f ( x ) \nabla f(x) ∇f(x) 满足利普希兹连续条件，那么下式成立 f ( y ) ≤ f ( x ) + ∇ f ( x ) T ( y − x ) + L 2 ∥ y − x ∥ 2 f(y) \le f(x) + \nabla f{(x)^T}(y - x) + \frac{L}{2}{\left\| {y - x} \right\|^2} f(y)≤f(x)+∇f(x)T(y−x)+2L​∥y−x∥2 将 y = x − α ∇ f ( x ) y = x - \alpha \nabla f(x) y=x−α∇f(x) 代入可得 f ( y ) ≤ f ( x ) − ( 1 − L α 2 ) α ∥ ∇ f ( x ) ∥ 2 f(y) \le f(x) - (1 - \frac{{L\alpha }}{2})\alpha {\left\| {\nabla f(x)} \right\|^2} f(y)≤f(x)−(1−2Lα​)α∥∇f(x)∥2 令 x ~ = x − α ∇ f ( x ) \tilde x = x - \alpha \nabla f(x) x~=x−α∇f(x)，且 0 < α ≤ 1 L 0 < \alpha \le \frac{1}{L} 0{2\alpha }}\left( {{{\left\| {{x_0} - {x^*}} \right\|}^2} - {{\left\| {{x_k} - {x^*}} \right\|}^2}} \right) \\ \le \frac{1}{{2\alpha }}{\left\| {{x_0} - {x^*}} \right\|^2} \\ \end{array} i=1∑k​(f(xi​)−f(x∗))≤2α1​(∥x0​−x∗∥2−∥xk​−x∗∥2)≤2α1​∥x0​−x∗∥2​ 因为 f ( x k ) f({x_k}) f(xk​) 是非增的，所以有 f ( x i ) − f ( x ∗ ) ≤ 1 k ∑ i = 1 k ( f ( x i ) − f ( x ∗ ) ) ≤ ∥ x 0 − x ∗ ∥ 2 2 α k f({x_i}) - f({x^*}) \le \frac{1}{k}\sum\limits_{i = 1}^k {\left( {f({x_i}) - f({x^*})} \right)} \le \frac{{{{\left\| {{x_0} - {x^*}} \right\|}^2}}}{{2\alpha k}} f(xi​)−f(x∗)≤k1​i=1∑k​(f(xi​)−f(x∗))≤2αk∥x0​−x∗∥2​

通过梯度下降法求解二次方程来说明梯度下降法的性能。设求解的问题为 y = A x {\bf{y}} = {\bf{Ax}} y=Ax，那么用梯度下降法求解 x ∗ {\bf{x}}^{*} x∗ 可以写成优化问题： x ∗ = arg ⁡ min ⁡ x ∈ R n 1 2 ∥ A x − y ∥ 2 2 {\bf{x}}^{*}=\mathop {\arg \min }\limits_{{\bf{x}} \in {\mathbb{R}^n}} \frac{1}{2}\left\| {{\bf{Ax}} - {\bf{y}}} \right\|_2^2 x∗=x∈Rnargmin​21​∥Ax−y∥22​。

[1]]袁亚湘, 孙文瑜. 最优化理论与方法[M]. 科学出版社, 1997. [2]https://www.cs.ubc.ca/~schmidtm/Courses/540-W18/L4.pdf [3]https://www.cs.cmu.edu/~ggordon/10725-F12/slides/05-gd-revisited.pdf [4]]http://users.ece.utexas.edu/~cmcaram/EE381V_2012F/Lecture_4_Scribe_Notes.final.pdf

更多精彩内容请关注订阅号优化与算法和加入QQ讨论群1032493483获取更多资料

往期精选：

经典正交多项式介绍及其应用

SISO/MIMO信道估计（channel estimation）原理详细图解

毫米波大规模MIMO的AOA估计

线性降维：主成分分析PCA原理分析与仿真验证

5G+AI：有哪些新的研究方向和新范式？

简述3D点云配准算法

5G为人工智能与工业互联网赋能|79页高清PPT

智能算法|以动物命名的算法

一份超全面的机器学习公共数据集

矩阵填充|奇异值阈值算法

可重构/大规模智能反射表面reconfigurable/large intelligent surface综述

迭代硬阈值类算法总结||IHT/NIHT/CGIHT/HTP

软阈值迭代算法（ISTA）和快速软阈值迭代算法（FISTA）

伍德伯里矩阵恒等式（Woodbury matrix identity）

压缩感知：一种新型亚采样技术