Optimization Algorithms - Gradient Methods

本文主要介绍梯度类算法，包括梯度下降法、投影梯度法、条件梯度法、邻近点梯度法、加速梯度法等的基本概念与内在思想。

在最优化理论中，梯度法 (Gradient method) 是一种求解优化问题

的迭代算法，其每一步的更新方向仅由当前点的一阶梯度(或次梯度)信息给出。这类方法的实现相对简单，更重要的是尽管它一般只具有线性收敛性，但由于每次迭代只需要计算一次梯度信息，计算复杂度相比使用二阶信息的牛顿法等方法要低得多，因此在实际应用中，特别是要处理大规模问题时，梯度法是最常用的优化算法之一。

无约束问题的梯度法

考虑如下问题

其中 是一个可微函数。

迭代算法的一般格式

其中，是处的下降方向，即

这也表明，方向导数满足

而是步长，以决定沿着下降方向走多远。

设计算法的目标是，使得迭代点xk越来越接近最优点。通常有如下几种最优条件度量：

1. （函数值下降）;
2. （梯度值下降） as ;
3. （最优点逼近），其中是最优点;
4. …

梯度下降法

注意到有Taylor展开

根据Cauchy不等式，如果足够小，则当会使得函数最小，因此梯度下降法 (GD) 选取下降方向为负梯度方向：

其迭代格式为

其中是步长，可以通过线搜索方法来选取，也可以直接选取固定的。

梯度下降法的另一种理解方式，是在局部使用二次函数逼近原函数，求解近似得到的二次函数的极小值点：

收敛性

为了理解梯度下降（GD）的收敛速率，让我们从二次目标函数开始

其中是正定矩阵，是最优点，不难发现。对于这一问题，我们有如下结论：

定理：对于上述二次问题，如果选取迭代步长为

其中和分别是的最小和最大特征值，则梯度下降法的迭代点满足

Remark. 这里的选取是为了保证

此时定理断言梯度下降法的收敛率由的条件数决定，也等价于

另外，上面使用的步长依赖于的谱范数，它需要通过估计的特征值得到。另一个更激进的策略是精确线搜索规则，即使用

定理：在使用精确线搜索求解二次问题时，梯度下降法的收敛率为

注意到该速率使用的是目标函数值的下降率，而不是迭代点的距离，且收敛率并不快于常数步长规则。另外，上述例子也表明，迭代步长的选择会影响算法的表现。

Proof. 实际上，若简记，则精确线搜索给出的步长为

因此有

其中最后一步的等式使用到了。由Kantorovich不等式可知

于是就可以得到

因此上述收敛性结论成立。

线搜索

下面我们继续讨论梯度下降法的步长选取问题，最常用的步长选取方法是线搜索 (Line Search)，即在每次迭代中，沿着当前的下降方向进行线搜索，找到一个合适的步长。

回忆梯度下降法的迭代格式为

为了确定下一个迭代点，需要先确定下降方向（如选取负梯度、Newton方向、拟Newton方向等），再按照某种准则来选取步长。选取的方式千差万别，但是选取的方式却相对固定：首先构造一元辅助函数

其中是给定的下降方向，是该辅助函数的自变量。线搜索的目标是选取合适的使得尽可能地小，这要求

1. 应当使得充分下降；
2. 不应在寻找上花费过多的计算量。

一个自然的想法是寻找在非负半轴上的最小值点，即令

称上述线搜索算法为精确线搜索法 (Exact Line Search)。由于以这种方式选取的是的精确最小值点，因此通常需要相当大的计算量，在实际应用中较少使用。

更常用的线搜索方法是不精确线搜索 (Inexact Line Search)，即选取使得足够小，但不需要是最小值点。常用的准则有：

1. Armijo准则：要求比小一个常数倍，即
   
   其中是一个小的正数（如）。
   • 引入Armijo准则的目的是保证每一步迭代充分下降；
   • Armijo准则有直观的几何含义, 它指的是点必须在直线
     
     的下方；
     Armijo准则
   • 参数通常选为一个很小的正数, 这使得Armijo准则非常容易得到满足；
   • Armijo准则需要配合其他准则以保证迭代的收敛性, 因为显然满足Armijo准则, 此时迭代序列中的点固定不变。
     一种常用的方式是结合回溯 (backtracking) 法：给定初值，回溯法通过不断以指数方式缩小试探步长, 找到第一个满足Armijo准则的点。回溯法选取
     
     其中
     
     这里的是一个给定的常数。
     Backtracking
     该算法被称为回溯法是因为的试验值是由大至小的, 它可以确保输出的能尽量地大。另外，上述算法不会无限进行下去, 因为是一个下降方向, 当充分小时, Armijo准则总是成立的。最后，在实际应用中我们通常也会给设置一个下界, 防止步长过小。
2. Goldstein准则：设是处的下降方向，若
   
   则称满足Goldstein准则，其中。
3. Wolfe准则：设是处的下降方向，若
   
   其中和是常数，通常取，则称满足Wolfe准则。
   • 注意到恰好就是的导数，因此Wolfe准则实际要求在点处切线的斜率不能小于的倍。
   • 的极小值点处有，因此永远满足上述第二条条件，而选取较小的可以使得同时满足第一条条件，因此Wolfe准则在绝大多数情况下都可以包含极小值点。
     Wolfe准则

光滑与强凸问题的收敛

给定可微函数，如果存在常数使得

对于任意都成立，则称是梯度Lipchitz连续的，通常也简称为梯度-Lipschitz连续或-光滑，称为梯度Lipschitz常数。

引理 (二次上界)：设可微函数的定义域，且为梯度-利普希茨连续的，则函数有二次上界：

其中。 另外，如果进一步是二次可微的，且

对于任意都成立，则是-强凸，且-光滑的。

Proof. 只需注意到

其中最后一行使用了梯度-Lipschitz连续的定义。

凸函数上的收敛

现在考虑梯度法

要求其中的函数为凸的梯度-Lipschitz连续函数，它的极小值存在并且可以被取到，并且如果要使用常数步长，则约定满足。在这种情况下，梯度法的收敛性可以通过以下定理来描述：

定理：对于满足上述条件的梯度法，迭代点列处的函数值收敛到最优值，且在函数值的意义下收敛速度为。如果函数进一步地是-强凸的，则梯度法的收敛速度会进一步提升到-线性收敛。

Proof. 因为函数是利普希茨可微函数，对任意的，根据二次上界引理

现在记并限制，则

其中第一个不等式成立是因为，第二个不等式成立是因为是凸函数。现在令上式中的，，并将不等式对求和得到

又由于非增，因此

于是结论成立。

当使用非常数步长时，我们可以对收敛率做进一步的分析。回忆给定初值，回溯法可以通过不断以指数方式缩小试探步长, 找到第一个满足Armijo准则的点，即选取

其中

这里的是一个给定的常数。根据这一机制，注意到Armijo准则在时不满足，即有

另一方面，由二次上界引理可得

结合上述两个估计可以得到

取可以得到

综合初始步长可得。这一事实表明回溯法可以有效估计函数的Lipschitz常数L。

关于使用回溯法的梯度下降法的收敛性，我们有以下结论：

定理：设是-强凸的，且梯度-Lipschitz连续的函数，使用回溯法的梯度下降法迭代点列处的函数值收敛到最优值，且在函数值的意义下收敛速度与固定步长方法类似为。

Proof. 由之前的分析可知

对上式两边求和得到

因此结论成立。

为了进一步给出步长选取的建议，我们需要先讨论凸函数和梯度-Lipschitz连续函数的有关性质。我们有如下两个基本的引理。

引理 (凸可微函数)：设函数是上的凸可微函数，则以下命题等价

1. 的梯度是-Lipschitz连续的，即
   
   对任意都成立；
2. 函数是凸函数；
3. 的梯度具有余强制性，即
   
   对任意都成立。

Proof. 我们按照的顺序证明上述等价关系。

：只需验证的单调性即可。注意到对于任意的，有

因此是单调的，是凸函数。
：构造辅助函数

不难验证和都是凸可微函数。由可知关于是凸函数，根据凸函数的性质有

对于任意的都成立。整理可得具有二次上界，并且系数为。又注意到，因此是的最小值点，根据下面容易证明的引理可得

同理对也有类似的结论，即

将上两式相加可得余强制性。
：由余强制性与Cauchy不等式可得

因此是梯度-Lipschitz连续的。

引理 (梯度-Lipschitz连续函数)：如果可微函数的定义域存在一个全局极小点，且为梯度-Lipschitz连续的，则对任意的都有

利用上述两个引理，我们可以将之前的关于函数值收敛的结论加强到迭代点收敛。

Convergence of Gradient Descent Method (Strong Convex)

设函数是-强凸的梯度-Lipschitz连续的函数，存在且可以被取到。如果迭代步长满足 则梯度下降法的迭代点列以-线性收敛速度收敛到最优点。

Proof. 根据是-强凸的梯度-Lipschitz连续函数的性质可得

是凸函数，且是凸函数。由之前的引理可知是梯度-Lipschitz连续的，再次使用引理可得的余强制性

代入的定义可得

下面估计固定步长下梯度法的收敛速度。设步长，对和应用上述估计并注意可得

于是有

因此迭代点列以-线性收敛速度收敛到最优点。

Remark. 注意到在上述强凸函数的假设下梯度下降法的迭代点列以

的速度收敛到最优点。如果取步长为，则有

如果函数的定义域内存在极小点，则

对任意都成立，因此

所以为了使函数值达到指定精度，即

所需的迭代次数为。

局部结构性条件

到目前为止，我们在强凸性和光滑性的条件下建立了梯度法的线性收敛。事实上，强凸性要求往往可以放宽，例如有如下几种条件可作为替代：

• 局部强凸性：
  设函数使局部-强凸且-光滑的，即
  
  对于任意都成立，其中是的极小点，则之前定理的结论仍然成立，即迭代点列以与之前相同的-线性收敛速度收敛到最优点。
• 规则性条件：
  如果函数对于任意的都满足以下规则性条件
  
  则使用固定步长时有
  
• Polyak-Łojasiewicz 条件：
  如果函数满足Polyak-Łojasiewicz 条件，即对于一阶稳定点下式成立
  
  (此时一阶稳定点是全局最优点)，则使用固定步长时有
  
  这一结果保证了迭代函数值向最优目标值的线性收敛，但是不意味着全局最小值的唯一性。

除此之外还有更多的条件，例如误差界、二次增长条件等。这些条件通常不需要假设问题是凸问题。

非凸问题

大量优化问题都是非凸的，对于非凸问题通常不能期望有效地全局收敛到全局最小值，但我们可以寻找方法来满足以下目标：

• 收敛到稳定点，即满足的点；
• 收敛到局部最小值；
• 在适当初始化时局部收敛到全局最小值；

一般地，对于非凸光滑函数使用梯度下降法时有以下收敛结果：若是-光滑函数且有最小值，则选取步长时有

且对于任意的正整数都有

因此梯度下降在次迭代中将能找到一个-近似稳定点，但这不意味梯度下降收敛到稳定点，这一结论只表明在梯度下降轨迹中存在近似稳定点。

一个进一步的问题是稳定点不一定是局部最小值，除了局部最小值点，鞍点同样具有消失梯度，它看起来像“不稳定”的临界点，然而梯度下降无法总是逃离鞍点。例如，如果算法的起始点恰好是一个鞍点，则梯度下降会陷入其中 (因为)。幸运的是，在相对不太严苛的条件下，随机初始化的梯度下降几乎总是可以收敛到局部 (有时甚至是全局) 最小值。

次梯度方法

许多优化问题的目标函数都是不可微的，例如常见的基追踪问题和矩阵补全问题，它们的目标函数分别是最小化范数和矩阵变量的核范数。为了研究不可微时问题的最优条件，我们可以定义一般非光滑凸函数的次梯度。

次梯度

回顾可微凸函数的一阶等价条件:

这表明，在点处的一阶近似是的一个全局下界。我们这里的想法是，将上述不等式拓展到一般不可微的情形。我们先考虑简单的绝对值函数，。注意到的左右导数分别为，因此在处不可导，可以验证，对于任意，下面的不等式成立

于是

函数在处的次梯度示意图。任意斜率在之间的过原点的直线，均为函数的一个下界。

设是适当 (存在使得) 凸函数，是定义域内一点。若满足

则称是在点处的次梯度 (subgradient)。进一步称该点处全体次梯度组成的集合

为在点处的次微分 (subdifferential)。

注意到当凸函数可微时有

即

上式表明诱导出的上方图在点处的支撑超平面，如下图所示。

对于凸函数，其上方图是一个凸集，是在处的支撑向量。

对于一般的不可微凸函数，次梯度的定义可以看作是上述几何意义的推广，即如果是的一个全局下界，则就可以诱导出上方图在点处的一个支撑超平面

这样的就是在点处的次梯度。如果可微，则自然满足上式，因此可微函数的梯度也是它的次梯度。

关于次梯度的存在性，我们有如下结论：

Existence of Subgradient

设是凸函数，是它的定义域。如果是的内点，即，则非空，即在点处存在次梯度。

Proof. 证明依赖于凸函数的上方图是一个凸集的性质。由于是一个凸集，因此它在点处的支撑超平面存在，即存在使得

令可知。现在令，其中，于是，故。根据之前的几何意义可知是在点处的次梯度，因此非空。

次梯度的性质

定理 (次微分是凸集)：对于任意，是一个闭凸集 (可能为空集)。

定理 (内点处次微分非空有界)：如果，则是非空有界。

定理 (可微函数的次微分等价于微分)：设凸函数在处可微，则。

定理 (次梯度的单调性)：设是凸函数，，则

定理 (次梯度的连续性)：设是闭凸函数，在点附近存在且非空。若序列，为在点处的次梯度且满足，则。

凸函数的方向导数

对于一般的适当函数，给定点以及方向，当极限

存在时，称其为在点沿方向的方向导数 (directional derivative)，记作。

特别地，当是凸函数时，注意到在上是单调不减的，上式中的极限可以替换为下确界，并且此时下确界总是存在，故凸函数总是可以定义方向导数：对于任意的凸函数，给定点以及方向，定义其方向导数为

定理 (方向导数有限)：设是凸函数，，则对任意的，方向导数是有限的。

定理 (方向导数与次梯度的关系)：设是凸函数，，为中任意方向，则

更一般地，可以证明当是适当凸函数，且在处次微分不为空集时，对于任意的都有

并且当并非无穷时，上式中的上确界可以取到。

次梯度的计算

次梯度的计算通常比较困难，一般可以进一步分为两大类问题：

1. 弱次梯度计算：得到一个次梯度。
   • 这足以满足大多数不可微凸优化问题的需求；
   • 如果可以获得任意一点处函数的值，则总可以计算出一个次梯度。
2. 强次梯度计算：得到所有次梯度。
   • 部分算法与最优性条件需要函数完整的次微分；
   • 此类计算可能相当复杂。

次梯度计算的基本规则是首先将给定函数视作若干简单函数在一些变换下的组合，然后利用简单函数的次梯度计算规则来计算的次梯度。下面我们介绍一些典型函数的次梯度计算方法。

凸可微函数 根据之前的分析，如果凸函数在点处可微，则，因此梯度就是次梯度。

凸函数的非负线性组合 设是凸函数，满足

现在对于任意，令

则在点处的次微分满足

线性变量替换 设是适当凸函数，满足。如果存在使得，则

函数族的上确界 设都是上的凸函数，令

对于任意，定义，则

即所有在点处的次梯度的并的凸包。进一步地，如果所有地都在点处可微，则

逐点上确界函数 设是一组凸函数，令

对于任意的，定义，则

如果是紧集且关于指标连续，则

固定分量的函数极小值 考虑函数

其中函数关于联合凸。为了计算在点处的次梯度，首先可以找到一个点使得

之后就可以断言存在使得

这样的。

复合函数 设都是凸函数，为关于各分量单调递增的凸函数，令

为了计算在某一点处的次梯度，首先可以计算出在点处的次梯度

以及相应的在点处的次梯度

那么就可以证明

是在点处的次梯度。

期望函数 设是一个随机变量，是关于的凸函数，令

现在我们希望计算在点处的次梯度。为此，我们需要首先选择一个函数使得

然后就可以断言

对偶与最优性条件

对于无约束问题而言，最直接的最优性条件是：

Optimal Condition for Unconstrained Problem

设是凸函数，则是的极小点当且仅当

而对于带约束的凸问题，有以下相应的最优性定理：

Optimal Condition for Constrained Convex Problem

考虑带不等式约束的如下凸问题 如果强对偶原理成立，则和是最优原始、对偶变量当且仅当以下条件成立

1. 是可行点；
2. ；
3. 对于所有成立；
4. 是的一个极小值点，其中

非光滑优化

典型的非光滑优化问题包括：

1. 极大极小问题：
   
2. 求解非线性方程组：，其中；
3. LASSO问题:
   
   其中，，；
4. …

对于非光滑问题，直接使用梯度法可能会收敛到一个非稳定点，例如考虑函数

其中。现在我们假设梯度法的迭代点形如

其中。可以计算迭代点处的梯度为

其中。如果直接使用梯度法进行迭代，在负梯度方向进行精确线搜索，可得

其中，因此。当给定初始点为时，我们有，然而处梯度非零，并非稳定点。为了解决这一问题，我们需要使用下面介绍的次梯度方法。

次梯度算法

现在我们假设是凸函数，但不一定可微，考虑以下无约束优化问题

回忆该问题的最优条件为是的极小点当且仅当

因此可以通过寻找次梯度集合中包含的点来求解其对应的全局极小点。更严格地讲，为了极小化一个不可微的凸函数，可类似梯度法构造如下次梯度算法的迭代格式

其中是步长，通常有以下四种选取方式

1. 固定步长：；
2. 固定：为常数；
3. 消失步长：且；
4. 线搜索：通过精确或非精确线搜索来选取步长。

我们将这类基于次梯度的算法称为次梯度算法 (subgradient method)。总地来说，次梯度算法具有以下特征：

1. 能够处理一般的不可微凸函数；
2. 常能推导出非常简单的算法；
3. 收敛速度可能非常缓慢 (相比于具有线性收敛速度的梯度法，次梯度法通常仅具有阶数的收敛速度)；
4. 没有很好的停机准则；
5. 理论复杂度：迭代步可以得到-精度的点；
6. 一种“最优”的一阶方法：复杂度无法再改进。

下面我们讨论在不同步长取法下次梯度算法的收敛性质。

收敛性

现在约定本小节中出现的函数满足如下假设：

1. 是凸函数；
2. 至少存在一个有限的极小值点，且；
3. 为Lipshitz连续的，即
   

上述三个条件等价于要求的次梯度有界，即

对于次梯度算法，一个重要的观察就是它并不是一个下降方法，即无法保证，这给收敛性的证明带来了困难．不过我们可以分析历史迭代的最优点所满足的性质，以此给出一些关于次梯度算法的收敛性的分析。

Convergence of Subgradient Method

设满足本小节开头的假设，是任意迭代步长序列，是对应的次梯度算法的迭代序列，则对于任意的都有 其中是的极小点，是的极小值，是前次迭代点上的最小值。

上述定理揭示了次梯度算法的一些关键性质：次梯度算法的收敛性非常依赖于步长的选取；次梯度算法是非单调算法，可以配套常用的非单调线搜索准则一起使用。另外，根据上述定理可以直接得到不同步长取法下次梯度算法的收敛性：

1. 取是固定步长时，直接计算可得
   
   由于只是前次迭代点上的最小值，因此上述结果无法保证收敛性。当足够大时，近似为精度的近似解。
2. 取以使得固定，即令是常数，则
   
   同样地，这一结果无法保证收敛性，但可以保证当足够大时，近似为精度的近似解。
3. 取且为消失步长时，我们有
   
   进一步可得收敛到。

由此可见，与梯度法不同，次梯度算法的收敛性依赖于步长的选取，只有当步长满足消失条件时，次梯度算法给出的前次最优值才能收敛到的极小点。一个常用的步长取法为。

下面我们考察固定迭代步数下的最优步长。假设，并且总迭代步数给定，则在固定步长下有

由平均值不等式可知当满足

时，该估计的右端最小，因此步迭代之后的上界是

这表明在步迭代之后可以得到的精度。类似地，可以证明在第二类步长选取策略下，取也可以得到与上面一致的收敛性结果，即

特别地，如果最优值已知，由于根据次梯度算法的迭代格式可知

其中最后一行右端在

时取到最小，此时迭代等价于

递归地使用上式并结合和，最终就得到了

实际上，存在例子可以说明上面估计的右端上界无法进一步改进，是次梯度算法的最优收敛速度。

投影梯度法

从现在起，我们开始讨论带约束的凸优化问题。在优化和应用数学中，约束优化的梯度方法对于解决广泛的问题至关重要，这些方法的主要思想是将梯度下降 — 一种用于无约束优化的基本技术 — 有效地改进到处理约束的情况。

我们将约束问题写为如下一般形式：

其中约束集是一个闭凸集。首先关于这种问题我们有以下最优性条件：

Optimal Condition for Constrained Problem

对于上述约束问题而言，是最优点当且仅当

投影梯度下降方法是梯度下降在约束问题上的直接扩展。给定一个约束集合，点到的投影，表示为，定义为：

投影梯度下降方法的迭代格式为

其中是第次迭代的步长。

这种投影方法的一个关键性质是非扩张性 (non-expansiveness)，即对于任意的，都有

这意味着投影操作不会增加点之间的距离，这对于迭代过程的稳定性和收敛性是非常重要的。

到简单集合的投影

对于一些简单的凸集合，投影操作可以显式地计算出来。以下是一些常见集合的投影方法：

仿射集 对于超平面，其中，相应的投影算子为

而对于仿射集，其中，，投影算子为

当或时，上述投影算子可以高效地计算。

多面体集 对于半平面，其中，相应的投影算子为

对于矩形区域，其中，投影算子为

对于非负象限，投影算子为

对于概率单纯形，投影算子为

其中是以下方程的解

对于更一般的概率单纯形，其投影算子类似地为

其中是以下方程的解

范数球 到Euclidean球的投影算子为

到范数球的投影算子以如下方式被定义

当时，否则是以下方程的解

简单锥 二阶锥的投影算子为

对于半正定锥，相应的投影算子为

其中是的特征分解。

收敛性

条件梯度法

邻近点梯度法

近似点映射

加速梯度法