数值优化：经典一阶确定性算法及其收敛性分析 - orion-orion

我们在上一篇博客《数值优化：算法分类及收敛性分析基础》介绍了数值优化算法的历史发展、分类及其收敛性/复杂度分析基础。本篇博客我们重点关注一阶确定性优化算法及其收敛性分析。

1 梯度下降法

1.1 算法描述

梯度下降法[1]是最古老的一阶方法，由Cauchy在1847年提出。
梯度下降法的基本思想是：最小化目标函数在当前迭代点处的一阶泰勒展开，从而近似地优化目标函数本身。具体地，对函数f:Rn→R，将其在第t轮迭代点wt处求解下述问题：

上式右端关于自变量w是线性的，并且使得∇f(wt)Tw最小的方向与梯度∇f(wt)的方向相反。于是梯度下降法的更新规则如下：

其中η>0是步长，也常被称作学习率。

梯度下降法描述如下：

1.2 收敛性分析

针对不同性质的目标函数，梯度下降法具有不同的收敛速率。由于梯度下降法只适用于梯度存在的函数（没有梯度需要考虑使用次梯度的方法），这里考虑梯度下降法对于光滑凸函数和光滑强凸函数的收敛速率。

光滑凸函数收敛性 假设目标函数f:Rd→R是凸函数，且β-光滑，当步长η=1β时，梯度下降法具有O(1t)的次线性收敛速率：

光滑强凸函数收敛性 假设目标函数f:Rd→R是α-强凸函数，且β-光滑，当步长η=1β时，梯度下降法具有O(e−tQ)的线性收敛速率：

其中Q=βα，一般被称为条件数。

通过以上两个定理可知，强凸性质会大大提高梯度下降法的收敛速率。进一步地，强凸性质越好(即α越大)，条件数Q越小，收敛越快。

而光滑性质在凸和强凸两种情形下都会加快梯度下降法的收敛速率，即β越小（强凸情景下，条件数Q越小），收敛越快。可以说凸情形中的光滑系数和强凸情形中的条件数在一定程度上刻画了优化问题的难易程度。

2 投影次梯度下降法

2.1 算法描述

梯度下降法有两个局限，一是只适用于无约束优化问题，二是只适用于梯度存在的目标函数。投影次梯度法[2]可以解决梯度下降法的这两个局限性。

投影次梯度下降法相比梯度下降法，具有次梯度选择和约束域投影两个特性：

• 次梯度选择 选取当前迭代点wt的次梯度集合∂f(wt)中随机选取一个次梯度gt，按照梯度下降更新
  vt+1=vt−ηgt
  得到vt+1。
• 约束域投影 确定vt+1是否属于约束域W，如果属于则直接将其做为wt+1；如果不属于，则需寻找vt+1到约束域W的投影，也就是W中离vt+1最近的点。如下图所示：
  
  
  
  寻找投影的过程可以经由投影映射ΠW( ⋅ )来完成：

投影次梯度下降法描述如下：

2.2 收敛性分析

在一定步长的选取规则下，投影次梯度法是收敛的，并且收敛速度也依赖于目标函数的凸性和光滑性。

对于β-光滑的凸/强凸函数，当步长为1β时，投影次梯度下降法的收敛率和梯度下降法相同，对于凸函数是O(1t)，强凸函数是O（e−tQ）。

不过，由于投影次梯度算法适用于有次梯度存在的目标函数，因而不仅适用于光滑函数的优化，也适用于Lipschitz连续函数的优化。对于Lipschitz连续函数，投影次梯度下降法收敛。对于凸函数，步长η=O(1√t)时，收敛速率为O(1√t)；对于强凸函数，步长η=O(1t)时，收敛速率为O(1t)。可以看到其收敛速率在凸和强凸两种情形相比光滑函数显著降低，都是次线性。

3 近端梯度下降法

3.1 算法描述

近端梯度法[3]是投影次梯度法的一种推广，适用于如下形式的部分不可微的凸目标函数的优化问题：

其中l(w)是其中的可微凸函数部分，R(w)是不可微的凸函数（例如L1正则项）。算法的基本思想是先按照可微的l函数进行一步梯度下降更新：

然后再经过近端映射proxR( ⋅ )做为本轮最终的迭代更新：

近端梯度下降法描述如下：

3.2 收敛性分析

如下定理所示，近端梯度下降法可以达到线性收敛速率。

近端梯度下降法收敛性 假设目标函数中的l函数是Rd上的α-强凸函数，且β-光滑；R函数是Rd上的凸函数， 当步长η=1β时，近端梯度下降法具有O(e−tQ)的线性收敛速率：

其中Q=βα为l函数的条件数。

4 Frank-Wolfe算法

4.1 算法描述

Frank-Wolfe算法[4]是投影次梯度下降法的另一个替代算法。投影次梯度算法虽然适用于有约束优化问题，但是如果投影的计算很复杂，投影次梯度下降的效率将会称为瓶颈。为了解决此问题，不同于投影次梯度下降法中先进行梯度下降再对约束域进行投影的做法，Frank-Wolfe算法在最小化目标函数的泰勒展开时就将约束条件考虑进去，直接得到满足约束的近似最小点，即：

为了使算法的解更稳定，Frank-Wolfe算法将求解上述子问题得到的vt与当前状态wt做线性加权：

如下图所示：

\

Frank-Wolfe算法描述如下：

4.2 收敛性分析

Frank-Wolfe算法收敛速率如下列定理所示：

Frank-Wolfe法收敛性 假设目标函数中的f函数是Rd上的凸函数，且β-光滑，当加权系数γt=2t+1时，Frank-Wolfe算法具有O(1t)的次线性收敛速率：

其中D=supw,v∈W‖w−v‖。
由于Frank-Wolfe算法的收敛速率和投影次梯度下降法相同，可以依据要解决问题中的投影计算是否困难，在两种算法中选择一种使用。

5 Nesterov加速法

5.1 算法描述

考虑以上所有的一阶算法。在Lipschitz连续的条件下，梯度下降法达到了一阶算法的收敛速率下界。然而对于光滑函数，一阶方法的收敛速率的下界小于梯度下降法的收敛速率。一阶方法在凸情形下的收敛率下界为O(1t2)，强凸情形下的下界为O(e−t√Q)；而梯度下降法在凸情形下的收敛率为O(1t)，强凸情形下的收敛率为O(e−tQ)。这说明我们可以针对光滑函数设计收敛速率更快的一阶方法。

Nesterov在1983年对光滑度目标函数提出了加快一阶优化算法收敛的方法[5]。我们这里以梯度下降法为例，介绍Nesterov加速法的具体实现。
Nesterov算法的基本原理如下图所示：

\

当任意时刻t，对当前状态wt进行一步梯度迭代得到辅助变量vt+1：

然后将新的辅助变量和上一轮迭代计算的辅助变量vt做线性加权，做为第t+1轮迭代的参数wt+1。对于凸和强凸的目标函数，线性加权系数有所不同。

具体地，对于强凸的目标函数，加权规则如下：

其中γt=1−√Q1+√Q，Q为条件数。

对于凸的目标函数，加权规则如下：

其中γt=1−λtλt+1，λ0=0, λt=1+√1+4(λt−1)22。

Nesterov加速算法描述如下：

5.2 收敛性分析

Nesterov证明了用以上方法加速之后的梯度下降法的收敛速率可以达到针对光滑目标函数的一阶方法的收敛速率下界:

光滑凸函数收敛性 假设目标函数f:Rd→R是凸函数，并且β-光滑，当步长η=1β时，Nesterov加速法能够将收敛速率提高到O(1t2)（不过仍是次线性收敛速率）：

光滑强凸函数收敛性 假设目标函数f:Rd→R是α-强凸函数，并且β-光滑，当步长η=1β时，Nesterov加速法能够将收敛速率提高到e−t√Q（不过仍是线性收敛速率）：

其中Q=βα为条件数。

6 坐标下降法

6.1 算法描述

坐标下降法[6]是另外一种常见的最小化实值函数的方法。其基本思想是，在迭代的每一步，算法选择一个维度，并更新这一维度，其它维度的参数保持不变；或者将维度分为多个块，每次只更新某块中的维度，其它维度保持不变。坐标下降法的更新公式如下：

其中，Wj为第j个维度块的约束域。

对于维度的选择，坐标下降法一般遵循以下本征循环选择规则（Essential Cyclic Rule）：存在一个常数r⩾d，使得对任意的s，对于每一个维度j，在第s轮和第s+r−1轮之间都至少选择一次。最常见的方法是循环选择规则，即对于任意j=1,...,d，分别在第j,d+j,2d+j,...次算法迭代中选择维度j（即每隔d轮选择一次）。

坐标下降法的算法描述如下所示：

6.2 收敛性分析

可以证明对于强凸并且光滑的目标函数，循环坐标下降法具有线性的收敛速率[6]。

• [1] Cauchy A. Méthode générale pour la résolution des systemes d’équations simultanées[J]. Comp. Rend. Sci. Paris, 1847, 25(1847): 536-538.
• [2]
  Levitin E S, Polyak B T. Constrained minimization methods[J]. USSR Computational mathematics and mathematical physics, 1966, 6(5): 1-50.
• [3] Parikh N, Boyd S. Proximal algorithms[J]. Foundations and Trends in optimization, 2014, 1(3): 127-239.
• [4] Frank M, Wolfe P. An algorithm for quadratic programming[J]. Naval research logistics quarterly, 1956, 3(1‐2): 95-110.
• [5] Nesterov Y E. A method for solving the convex programming problem with convergence rate O (1/k^ 2)[C]//Dokl. akad. nauk Sssr. 1983, 269: 543-547.
• [6]
  Wright S J. Coordinate descent algorithms[J]. Mathematical Programming, 2015, 151(1): 3-34.

__EOF__