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准则

收敛性

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

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

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

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

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

Proof. 只需注意到

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

现在考虑梯度法

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

Convergence of Gradient Method

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

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球的投影算子为

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

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

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

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

其中是的特征分解。

收敛性

对于目标函数是-强凸和-光滑的问题，投影梯度下降享有与无约束情况相似的收敛性质。

Convergence of Strongly Convex Problem

如果是-强凸和-光滑的，并且最优解在可行域内部，步长取，则投影梯度法的迭代序列满足

证明只需注意到

由于在可行域内部，因此无约束问题的分析可以直接搬到这里。

事实上，最优解在可行域内部的假设对于保证线性收敛速度而言是不必要的，即便失去这一假设，我们仍然可以证明投影梯度法的线性收敛速度。

Convergence of Strongly Convex Problem

如果是-强凸和-光滑的，步长取，则投影梯度法的迭代序列满足

我们定义，，则在无约束条件下等价于，因此称为广义梯度。上述定理的证明主要基于如下不等式

当上式成立时，我们就有

对于更一般的-光滑凸函数，可以证明投影梯度法的迭代序列满足

具有与无约束情况类似的收敛速度。

条件梯度法

基本思想是：在每一步迭代中，首先计算当前点的梯度，然后沿着梯度的反方向进行线搜索，得到一个新的点，最后将投影到可行域上得到下一个迭代点，即

回忆投影算子的定义为

其中为欧式范数。设是欧氏空间中的标准内积，于是投影梯度法的更新格式等价于

因此在每一步迭代中，投影梯度法需要求解一个带约束的二次优化问题，对于大规模问题来说，计算复杂度较高。当是凸函数，是-Lipschitz连续的时候，投影梯度法具有线性收敛速度：

为了克服投影梯度法每次迭代计算量较大的缺点，Frank-Wolfe算法（即条件梯度法）使用线性子问题替代了原本的二次优化问题，从而避免了开销较大的投影操作，在保持线性收敛速度的同时大幅降低了计算复杂度。下面我们介绍Frank-Wolfe算法及其几种常见变体的基本思想。

在投影梯度法中，每次迭代的更新格式为

实际上，上式等价于

条件梯度法舍弃了上式目标函数中的高次项，只保留线性部分，这样就用线性子问题替代了原本的二次优化问题，得到更新格式为

然而尽管上述格式的计算复杂度较低，直接线性化会引发以下问题：

1. 每一步迭代仅使用了当前点的梯度信息而丢弃了之前已经得到的迭代点处的已知信息，可能导致收敛速度较慢;
2. 直接使用线性子问题的求解结果可能会导致迭代点不在可行域内或在可行域边界来回剧烈震荡，这使得迭代难以收敛;
3. 使用固定极点迭代无法保证误差的线性下降速度，需要递减步长以保证收敛。

为了弥补上述缺陷，经典的Frank-Wolfe算法使用线性子问题的解与上一步迭代点的凸组合来更新迭代点，得到更新格式为

其中的消失步长通常设为以最大化收敛速度。经典Frank-Wolfe算法的计算流程如以下算法所示，从中可以观察到Frank-Wolfe算法给出的迭代点都是某些点的凸组合，这使得该算法给出的解天然具有稀疏和低秩的特性。

Frank-Wolfe算法

一些变体

下面我们介绍几种常见的Frank-Wolfe算法的变体。

近似线性子问题 在某些情况下，即使是求解线性化之后的子问题也同样过于昂贵，此时在每一步迭代时可尝试寻找一个近似极点而非精确求解原本的线性子问题。具体地，算法要求得到使得

该变体进一步降低了计算复杂度，在保证收敛速度仍为线性的情况下，允许每一步迭代中使用近似极点代替精确求解的线性子问题。与经典算法相比，近似变体在每步增加了一个误差参数，因此相应的理论收敛界需要增添一个 因子，但依然保持为线性收敛​。当时退化为经典算法。

步长线搜索 除了可以使用近似线性子问题替代原本的子问题，注意到在每一步迭代中，Frank-Wolfe算法使用固定的消失步长来更新迭代点，一种自然的替代方案是使用线搜索来确定步长，即令

通过线搜索获得最优步长往往能够加快收敛速度，尤其在早期迭代时效果显著，减少迭代次数。但每次需要额外评估目标函数，计算开销较固定步长略大。

完全修正 另一种改进思路为在每次引入新原子后，重新优化目标函数在迄今得到的所有迭代点张成的凸包上的值。若设 为迭代过程中已经得到的所有原子，则选取新的迭代点为

通过使用完全校正，这种方法每次迭代可以大幅改进当前解，所以该方式通常会加快收敛速度，并且由于使用的原子集数量相对较小，该方式倾向于产生更加稀疏的解。

与经典算法每步只做线性插值不同，完全修正变体每步都要解决一个较大的凸优化问题，其复杂度可接近原问题本身。因此虽然能提升收敛效果（迭代数减少），但每次迭代计算成本显著增加，难以给出全局运行时保证。数学上，此方法与最小范数点算法或正交匹配追踪有关，尤其在线性目标或二次目标时有类似形式。

Away-Step变体（又称外步法）引入了对删除旧原子的机制。如果当前点已由一组原子表示为凸组合，当计算线性子问题得到新原子时，同时也计算“远离方向”。然后在添加新原子方向和远离方向中选择一个下降最快的方向，从而允许每步既可能“加一”也可能“减一”原子。通过允许向外步，此方法可以移除“不利”的原子，使解更加稀疏，且在某些情况下（如目标为强凸且约束为多面体，特别当最优点在可行域边界上时，原始Frank-Wolfe算法的迭代会出现锯齿现象，收敛速度大大下降，外步法可以很好地改善其收敛表现）能获得线性收敛速率。Away-Step变体在机器学习中常用于提升收敛性能，并且其轨迹上点数通常远少于经典算法。

与经典只添加原子不同，此方法每步都需维护当前原子集的表示形式，并判断是否应从中移除一个原子。这使得算法在稀疏性和速度上可能更优，但每步计算更为复杂，需要跟踪多点组合，同时需要解决如何选择添加或删除的决策问题。Away-Step变体常见于处理多面体等特殊约束的情形，已知在某些问题上可以显著快于原始Frank-Wolfe。

Frank-Wolfe算法的收敛性分析详见文档与演示文档。

邻近点梯度法

基础概念

闭函数 如果一个函数的上方图时闭集，则称它是一个闭函数。事实上，一个函数是闭函数当且仅当它的所有-下水平集都是闭集。另外，如果是闭函数且存在有界下水平集，则存在最小值点。

常见的保闭性操作包括：

1. 加法 当都是闭函数，且定义域交集非空时，在定义域交集上是闭函数；
2. 复合线性映射 如果是闭函数，则也是闭函数，其中是线性映射，是常数向量；
3. 取上确界 如果是闭函数，则也是闭函数。

共轭函数 给定函数，其共轭函数定义为

可以证明恒为闭凸函数，并且注意到

因此如下Fenchel不等式成立

另外，使用次梯度的定义可以证明闭凸函数的共轭函数与的次梯度满足如下定理。

Conjugate Function - Subgradient

如果是闭凸函数，则

事实上，根据次梯度与共轭函数之间满足的上述Fenchel对偶关系：

回忆共轭函数的定义，注意到若令

则有

于是Fenchel对偶关系的最后一个等式成立，因此

此即

我们可以根据这一关系来计算共轭函数的次梯度。

一般地，给定某一函数，其共轭函数可以通过如下三种方式计算：

1. 根据定义
   
   当可微时考虑稳定点
   
   反解出带入的定义中即可。
2. 将原函数分解为一些简单函数的组合，这包括
   1. 求和：如果，则
      
   2. 数乘：如果，则
      
   3. 添加线性函数：如果，则
      
   4. 卷积下确界：如果，则
      

近似点映射

现在我们定义邻近算子。给定函数，定义其近似点映射为

即寻找一个距离不太远的点使得函数值也相对较小。可以证明，如果是闭凸函数，则近似点映射存在且唯一。

邻近算子的关键性质是它与函数的次梯度有关：

Proximal Operator - Subgradient

如果是适当的闭凸函数，则

与共轭函数的计算类似，给定函数，其近似点映射可以通过以下方式计算：

1. 根据定义
   
   当可微时考虑稳定点
   
   反解出带入近似点映射的定义中即可。
2. 使用近似点映射与次梯度之间的关系
   
   通过求解次梯度方程来得到近似点映射。
3. 将原函数分解为一些简单函数的组合，这包括
   1. 变量的常数倍放缩加平移：如果，则
      
   2. 函数的常数倍放缩：如果，则
      
   3. 添加线性函数：如果，则
      
   4. 添加二次项：如果，则
      
   5. 向量函数：如果
      
      则
      

另外，如果仅仅已知以及矩阵，令，一般而言无法直接使用的邻近算子得到的邻近算子，不过当时()时，我们有

例如对于，我们有

Moreau分解 根据之前的分析可知共轭函数与近似点映射都与函数的次梯度有关，借助次梯度这一桥梁，我们可以建立共轭函数和近似点映射之间的关系。注意到

而当且仅当，所以

再使用共轭函数的性质

这样就得到了

上式称为Moreau分解，它将一个点分解为两个部分：一个是近似点映射的结果，另一个是共轭函数的近似点映射的结果。

进一步地，有如下广义Moreau分解成立：

Generalized Moreau Decomposition

如果是闭凸函数，则对于任意都有

支撑函数 回忆支撑函数的定义为

其中是一个凸集。直接计算可知的共轭函数为的指示函数，即

使用Moreau分解就可以得到的近似点映射满足

其中是到凸集的投影算子，因此支撑函数的邻近算子可以通过计算投影得到。

范数 范数的共轭函数为其对偶范数球的指示函数

其邻近算子同样可由Moreau分解得到

其中是对偶范数球，是到对偶范数球的投影算子。当到上的投影容易计算时，可以直接使用上式高效计算范数的邻近算子。

单点距离 考虑一般的范数定义的单点距离函数

使用邻近算子的平移性质可知

其中是原点的单点距离函数。

欧式距离 考虑到闭凸集的欧式距离函数

其邻近算子为

对于平方距离，类似地有

最后，函数的凸性对于邻近算子与次梯度之间的关系并非必要，可以证明如果时适当闭函数(可能非凸)且有下界，则当时有

邻近点下降

考虑无约束复合优化问题 (对于凸约束问题，首先通过向目标函数中添加指示函数以转化为无约束问题)

其中是可微函数，为凸函数 (可以非光滑)，要求的邻近算子容易计算。当使用次梯度算法计算这一问题时的复杂度为，借助邻近点映射，我们可以将其复杂度降低到。

回忆函数的邻近算子定义为

邻近点梯度法的主要思想是对于光滑部分做梯度下降，对于非光滑部分做邻近点映射。具体地，邻近点梯度法的迭代格式为

其中是步长，它可以固定为一个常数或由线搜索得到。

根据邻近算子的定义，迭代格式等价于

根据邻近算子与次梯度的关系:

上式又可以写成

也即对光滑部分做显式的梯度下降，对非光滑部分做隐式的次梯度下降。

现在我们来讨论邻近点梯度法的步长选取。当是梯度-Lipschitz连续函数时，可以选取固定步长。当未知时，可以使用线搜索来确定步长，即

也可构造如下适用于邻近点梯度法的非单调线搜索准则

其中是正常数。注意此处定义时需要使用到整体函数值。

收敛性

现在我们假设在上是凸函数且是梯度-Lipschitz连续的，即

另外，是适当的闭凸函数，此时良定。最后要求函数的最小值有限，且在处可以取到 (可以不唯一)。在这些假设下，我们有下面的收敛性结论。

首先定义梯度映射

不难发现梯度映射具有以下性质。

1. 给出负搜索方向：
   
2. 根据邻近算子与次梯度的关系有
   
3. 最优性条件：是的最小值点当且仅当
   

在以上观察的基础上，在使用固定步长的情况下，邻近点梯度法的收敛性可以通过以下定理给出。

Convergence of Proximal Gradient Descent

取定步长为，设是邻近点梯度法的迭代序列，则

事实上，我们也可以使用线搜索来确定步长，每一步迭代都从某个开始进行回溯，直到满足不等式

上式等价于使用上一小节提到的

当使用这一方式确定步长时，我们有以下收敛性结论。

Convergence of Proximal Gradient Descent (Line Search)

使用线搜索确定步长 (从开始回溯，每次回溯令)，设是邻近点梯度法的迭代序列，则

对于非凸的适当闭函数，当具有有限下界，即

此时可以定义的邻近算子为

此时良定，是上的非空紧集 (可能不是单点集)，并且当，依然有。此时对于复合优化问题，依然可以使用以下迭代格式

即选取右端集合中的一个元素作为，此时算法同样具有收敛性。

加速梯度法

到目前为止，要获得一个精度为的解，当问题为强凸且光滑问题时，使用标准的梯度下降法具有-线性下降速度，因此需要使用次迭代，如果问题只是凸且光滑的，则需要使用次迭代。这一节我们希望进一步降低迭代次数，通过使用加速梯度法，对于强凸且光滑问题可以仅在次迭代内得到精度为的解，而对于凸且光滑问题可以仅在次迭代内得到精度为的解，因此加速梯度法的收敛远快于标准的梯度下降法。

我们先从无约束问题开始分析。回忆梯度下降法的迭代格式为

注意到GD的每次迭代都仅使用到当前点的梯度信息，没有利用上在之前已经计算得到的历史梯度信息；另外，直接梯度下降在一些情况下会出现锯齿现象，导致收敛速度变慢。因此我们可以尝试在迭代中利用上历史信息，以及添加缓冲量使得迭代轨迹更加平滑两种方式以加速收敛。

重球法

重球法是加速梯度法的一个重要变体。它通过在梯度下降的基础上引入一个缓冲量来加速收敛：考虑无约束光滑问题，重球法的迭代格式为

其中称为动量项，约定。通过为迭代点添加动量项，即在迭代过程中为迭代点引入惯性，使得迭代轨迹更加平滑，重球法可以有效地加速收敛。

通过利用差分

重球法的迭代格式可以看作是对以下二阶ODE使用上述差分格式进行离散之后得到的差分方程

其中可视为物体的质量，为物体加速度，为摩擦力，因此二次项可以理解为是物体的惯性。方程中的常数选取为

以保证差分方程与迭代格式的等价性。

梯度法和重球法在目标函数为时的迭代轨迹

上图展示了动量梯度法求解函数最小值的迭代轨迹。相比于梯度法，动量梯度法轨迹在更加缓和，因为动量随机梯度法在历史相同的梯度方向累积起来形成动量，而梯度变化快的方向相互抵消，缓解了振荡现象。总体上来说，动量梯度法只需添加一个参数, 其余参数设定方式可与GD相似。

现在我们来考虑使用重球法求解二次正定问题

时的收敛性，此处要求。首先不难发现重球法迭代格式可以写为如下矩阵形式

或者等价地

我们定义系统矩阵为

于是根据以上分析有

由此可见，重球法的收敛依赖于系统矩阵的谱范数，因此为了最大化收敛速度，应当选取合适的步长以及动量系数使得的谱范数尽可能地小。事实上，使用这一矩阵格式，我们对二次问题有以下收敛性结论：

定理 (使用重球法求解二次问题的收敛性) 设是-光滑且-强凸的二次函数，令步长取常数步长，且动量系数为，并令，则对于充分大的，存在使得

根据上述定理，在求解二次问题时重球法的迭代复杂度为，但是缺陷在于参数设置需要提前已知与。事实上，可以证明对于二次可微函数，如果是-光滑、-强凸的，则重球法在局部上同样具有的迭代复杂度；当函数仅仅一阶可微时，重球法的复杂度增加到与梯度下降法类似的水平 (此处“局部上”是指在局部上函数的Hessian矩阵近似不变，可以近似使用二次函数逼近，但是全局内函数的Hessian矩阵可能剧烈变化，因此难以获得全局一致的下界)。

Nesterov加速梯度法

对于无约束问题，其中是-光滑函数，Yurri Nesterov于1983年提出如下交替地进行梯度更新与适当外推的迭代格式：

其中为迭代步长，通常选取，且约定起始项。该格式每次迭代仅需计算一次梯度，因此成本与GD几乎相同。需要注意的是该格式并不是下降格式，即可能对于某些有。另外，每次迭代的第二步类似于重球法添加了一个动量项，但是这里的动量系数相当神秘，在早期没有比较直观的理解方式，目前比较合适的理解是该参数选取使得与迭代格式对应的ODE具有下降速度，这在一定程度上解释Nesterov算法的快速收敛。

Nesterov算法的强大之处在于如果目标函数是凸且-光滑的，令迭代步长为，则

因此Nesterov算法的迭代复杂度仅为，远快于GD的。

事实上，若定义一阶方法为任何在集合

内选取的迭代算法，则有如下定理成立：
Nesterov定理 对于任意整数与任意，存在-光滑的凸函数，对于任意一阶方法都有

这说明一阶方法对于-光滑的凸函数不可能具有比更快的收敛速度，因此Nesterov算法的收敛速度是一阶方法族中最优的。

现在我们从ODE的角度简要说明动量系数的选取合理性。首先对Nesterov算法的迭代格式进行变形可知其等价于

假设存在某一由参数化的光滑曲线满足，我们使用Taylor展开近似中的各项。令

于是我们有

在处对使用Taylor展开可得

以及

另外根据与之间的关系有

最后注意到动量系数的选取满足

现在将以上四部分的近似对迭代格式中的对应部分进行替换可得

令并注意到，于是上式的极限形式为

相应的初值条件为与，其中是因为时有

根据ODE理论，方程的解满足

这一定程度上解释了Nesterov算法的收敛速度。事实上，是保证ODE

的解具有收敛速度的最小常数，对于任意都有类似的收敛速度，因此动量系数对应的最小化了收敛界中的常数系数。

ODE曲线和Nesterov算法迭代轨迹 (From Su, Boyd, Candes ’2016)

FISTA

现在我们考虑典型的复合优化问题

其中是连续可微的梯度-Lipschtiz连续凸函数，是适当闭凸函数，且其邻近算子容易计算。根据之前的分析，当使用邻近点梯度法(ISTA)

时，若取常数步长时，则收敛速度为。

求解这一问题的FISTA (Fast Iterative Shrinkage-Thresholding Algorithm) 借鉴了上一节介绍的Nesterov加速梯度方法，每步迭代都对前两次迭代结果做线性外推来构造新的搜索点，从而在保持与邻近点梯度法相同计算成本的前提下实现了更快的收敛，其迭代格式分为两步：

1. 沿着前两步的计算方向计算一个新点；
2. 在得到的新点处做一步邻近点梯度迭代。

完整的迭代格式为

因此相比于Nesterov算法，FISTA仅需将梯度下降替换为邻近点下降。

FISTA

类似于Nesterov算法，FISTA迭代格式中的也称为动量系数，可以更一般地将这一系数替换为，其中满足

当取时即有。除此之外，我们可以使用如下常用的手段选取:

为了方便分析，我们将FISTA迭代格式写为如下等价形式

可以证明，当如下条件成立时，FISTA将以的速度收敛：

注意若要求步长满足，则根据的Lipschitz连续性可知条件自动得到满足，然而对于绝大多数问题，的Lipschitz常数未知，此时需要使用线搜索确定满足条件的步长。最直接的改进方式是直接在迭代格式的第2行中加入线搜索，并取

以回溯的方式找到满足条件的。当足够小时，条件总会满足，因此不会出现线搜索无法终止的情况。

另外，也可以重复以下过程直到条件得到满足来代替上述线搜索过程：

1. 取为的正根；
2. 令；
3. 令；
4. 令 (为回溯因子)；

这种方法不仅改变了步长，同时也不断调整，并且因此迭代点和参照点在线搜索的过程中都发生了变化，点处的梯度也需要重新计算，但此算法给我们带来的好处就是步长不再随着单调递减，在迭代后期也可以取较大值，这会进一步加快收敛。

最后，如果是-光滑且-强凸的函数，设其条件数为，FISTA的迭代格式可以选为

则当步长取时有

这说明在强凸情况下，FISTA具有最优复杂度。不过仍然有需要事先已知和的缺点 (可以借助线搜索估计，但难以估计)，并且当使用的与真实值相差较大时可能会导致迭代出现震荡 (可以通过尝试重启方法修正)。

总的来说，固定步长的FISTA算法对于步长的选取是较为保守的，为了保证收敛，有时不得不选取一个很小的步长，这使得固定步长的FISTA算法收敛较慢。如果采用线搜索，则在算法执行过程中会有很大机会选择符合条件的较大步长，因此线搜索可能加快算法的收敛，但代价就是每一步迭代的复杂度变高。在实际的FISTA算法中，需要权衡固定步长和线搜索算法的利弊，从而选择针对特定问题的高效算法。

最后我们不加证明地给出FISTA的收敛性定理：

Convergence of FISTA

在本节开头的收敛性假设下，当用FISTA求解凸复合优化问题时，若取固定步长，则 更一般地，若迭代点、步长和系数满足之前给出的条件，则 其中仅与和初始点的选取有关。特别地，使用了前面介绍的线搜索方法确定步长的FISTA具有的收敛速度。

事实上，是FISTA所能达到的最快的收敛速度，无法再找到其他的, 选取方式来进一步改善FISTA算法的收敛速度。

随机梯度下降法

随机梯度下降法(Stochastic Gradient Descent, SGD)是处理大规模数据集时常用的优化方法。它通过在每次迭代中仅使用一个样本或一小批样本来近似计算梯度，从而显著降低每次迭代的计算成本。

考虑大规模优化问题

其中是第个样本的损失函数，是样本总数。这类问题常见于各种机器学习中。经典的梯度下降法需要计算所有样本的平均梯度，由于数据规模巨大，计算目标函数的梯度非常困难。为了绕开这一困难，SGD通过随机采样的方式只计算部分样本的梯度来进行梯度下降，在一些场景下同样能达到非常好的数值表现，而每步的运算量却得到了极大的减小。下面为了讨论方便，我们先假设中的每一个都是可微的凸函数。

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

考虑到采集到的样本量是巨大的，因此计算需要非常大的计算量。使用传统的梯度法求解这样的问题并不是一个很好的做法，而牛顿算法这样的二阶算法的计算量更加庞大以至于完全无法使用。与上述方法不同，SGD的核心思想是每次迭代仅使用一个样本的梯度来近似计算目标函数的梯度，因此每次迭代的计算量大大降低。具体地，SGD的迭代格式为

其中是等可能地随机抽取的样本索引，为步长，通常在机器学习领域又被称作学习率。特别需要注意的是，的全梯度中包含系数，而SGD的更新格式中将这一系数去除了，这是为了保证随机梯度的条件期望与全梯度相同，即

在实际计算中，每次仅抽取一个样本的做法比较极端，常用的变体是小批量随机梯度下降法(Mini-batch SGD)，该方法在每次迭代中随机选择一个元素个数为的集合，然后执行迭代格式

注意上述抽取方式为有放回采样。

后续大量实验表明，通常采用无放回采样方式选取小批量元素的效果更好，这种采样方式又称为随机洗牌(random shuffling, RS)，命名的原因在于进行无放回采样时可以先将所有的数据集随机排序，即为下标分配一个新的排序, 每批次训练数据按照新的排序，依次选择长度为的子集。这样分批次抽完所有的数据的过程叫做一个epoch，于是训练中1个epoch可以使得模型遍历所有样本。事实上，可以从理论上证明RS收敛速度更快。

另外，当凸函数不可微时，我们可以使用次梯度下降法来代替梯度下降法，SGD的迭代格式变为

其中是随机选到的在点处的次梯度，其期望为的真实的次梯度。

除此之外，我们在之前已经看到传统的梯度法在问题比较病态时收敛速度非常慢，随机梯度下降法也有类似的问题。为了克服这一缺陷，可以将重球法拓展到随机梯度法中，主要的想法是在算法迭代时一定程度上保留之前更新的方向，同时利用当前计算的梯度调整最终的更新方向。具体的迭代格式为

这种方法在计算当前点的随机梯度之后添加了一步动量更新来得到新的更新方向，上式中的是动量更新系数，当时该方法退化成随机梯度下降法。在动量方法中，参数的范围是，通常取, 神经网络训练中通常，其含义为迭代点带有较大惯性，每次迭代会在原始迭代方向的基础上做一个小的修正。在普通的梯度法中，每一步迭代只用到了当前点的梯度估计，动量方法的更新方向还使用了之前的梯度信息，因此可以更好地适应目标函数的形状，尤其是在目标函数具有较强的非光滑性时。另外，当许多连续的梯度指向相同的方向时，更新步长就会相对较大，这一特性也符合我们的直觉。

最后我们介绍如何使用Nesterov加速的思想来改进随机梯度下降法。回忆Nesterov加速梯度法的迭代格式为

当都是光滑函数时，我们可以直接将Nesterov加速梯度法的迭代格式应用到随机梯度下降法中，得到

其中，步长可取常数或通过线搜索得到。可以看出，Nesterov-SGD的迭代格式与Nesterov加速梯度法的迭代格式非常相似，唯一的区别在于第二步迭代中使用了随机梯度来代替全梯度。

若在第步迭代引入速度变量，合并原始Nesterov加速算法的迭代格式可以得到

再定义

于是就有

从中可以看出，Nesterov加速与动量法的主要差别在梯度的计算上：Nesterov加速算法先对点施加速度的作用，再求梯度。从这种视角来看，Nesterov加速可以理解为标准动量方法的校正版本。

收敛性

下面我们简单介绍SGD的收敛性。为了方便讨论，首先重新将问题写成下列标准形式

其中是-强凸且-光滑的函数，是随机变量，是给定的的无偏估计，并且要求对于所有的，随机梯度的方差有界，即

在上述假设下，使用固定步长的SGD给出的迭代序列满足

从上述估计中可见对于强凸且光滑问题，SGD在一开始有快速(线性)收敛速度，但在接近最优解时，梯度的噪声阻碍了进一步收敛，最后期望误差通常只能下降到与随机梯度的方差和步长的大小有关的量级附近但无法精确收敛到。特别地，当梯度计算无噪声，即时，SGD可以线性收敛到最优点。另外，较小的步长会导致收敛速度变慢，但可以使得期望误差更小。基于这一特性，通常我们先使用较大的步长进行初始迭代以快速收敛到最优点附近，然后当收敛停滞时再使用较小的步长进行精细调整。

进一步地，当使用消失步长，其中，并且时，我们有

这一结果说明当使用步长以的速度递减时，SGD的收敛速度为。

当问题失去强凸性时，SGD的收敛速度会变慢。我们现在假设仅是凸函数，，定义如下加权平均

在这种情况下，我们有

特别地，当时，上式的直接推论是

因此SGD在非强凸的问题中也具有一定的收敛性，但收敛速度相对于在强凸问题中较慢。

最后下表总结了随机算法与普通算法的收敛速度对比，这里分别列出了随机算法与普通算法在不同类型的凸函数下的收敛速度，其中是样本数量，是所需精度。当样本数巨大时，随机算法通常具有更快的收敛速度。

随机算法 v.s. 普通算法

	凸(使用次梯度算法)	可微强凸	可微强凸且-光滑
随机算法
普通算法

References

1. 最优化讲义，陈士祥
   1. 无约束问题的梯度法
   2. 次梯度方法
   3. 投影梯度法和条件梯度法
   4. 近似点映射
   5. 邻近点梯度法
   6. 加速梯度算法
   7. 随机梯度法
   8. 随机梯度法-续，Adam优化器
2. 最优化与建模，文再文