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

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

1 梯度下降法

1.1 算法描述

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

[underset{w}{text{min}}f(w) = underset{w}{text{min}} left[ f(w^t) + nabla f(w^t)^T (w-w^t) right] ]

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

[w^{t+1} = w^t - eta nabla f(w^t) ]

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

梯度下降法描述如下：

1.2 收敛性分析

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

光滑凸函数收敛性 假设目标函数(f: mathbb{R}^d rightarrow mathbb{R})是凸函数，且(beta)-光滑，当步长(eta = frac{1}{beta})时，梯度下降法具有(mathcal{O}(frac{1}{t}))的次线性收敛速率：

[f(w^t) - f(w^*) leqslant frac{2beta lVert w^0 - w^*rVert^2}{t} ]

光滑强凸函数收敛性 假设目标函数(f: mathbb{R}^d rightarrow mathbb{R})是(alpha)-强凸函数，且(beta)-光滑，当步长(eta = frac{1}{beta})时，梯度下降法具有(mathcal{O}(e^{-frac{t}{Q}}))的线性收敛速率：

[f(w^t) - f(w^*) leqslant frac{beta}{2}e^{-frac{t}{Q}} lVert w^0 - w^*rVert^2 ]

其中(Q = frac{beta}{alpha})，一般被称为条件数。

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

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

2 投影次梯度下降法

2.1 算法描述

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

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

• 次梯度选择 选取当前迭代点(w^t)的次梯度集合(partial f(w^t))中随机选取一个次梯度(g^t)，按照梯度下降更新
  [v^{t+1} = v^t - eta g^t ]

  得到(v^{t+1})。

• 约束域投影 确定(v^{t+1})是否属于约束域(mathcal{W})，如果属于则直接将其做为(w^{t+1})；如果不属于，则需寻找(v^{t+1})到约束域(mathcal{W})的投影，也就是(mathcal{W})中离(v^{t+1})最近的点。如下图所示：
  
  寻找投影的过程可以经由投影映射(Pi_{mathcal{W}}(space cdot space))来完成：

[begin{aligned} w^{t+1} &= Pi_{mathcal{W}}(v^{t+1}) \ &= underset{vin mathcal{W}}{text{arg min}}lVert v - v^{t+1}rVert end{aligned} ]

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

2.2 收敛性分析

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

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

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

3 近端梯度下降法

3.1 算法描述

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

[underset{w in mathcal{W}}{text{min}} f(w) = l(w) + R(w) ]

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

[v^{t+1} = w^t - eta^t nabla mathcal{l}(w^t) ]

然后再经过近端映射(text{prox}_R(space cdot space))做为本轮最终的迭代更新：

[begin{aligned} w^{t+1} &= text{prox}_{R}(v^{t+1}) \ &= underset{vin mathcal{W}}{text{arg min}}left[ R(v) + frac{1}{2}lVert v - v^{t+1}rVert^2 right] end{aligned} ]

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

3.2 收敛性分析

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

近端梯度下降法收敛性 假设目标函数中的(l)函数是(mathbb{R}^d)上的(alpha)-强凸函数，且(beta)-光滑；(R)函数是(mathbb{R}^d)上的凸函数， 当步长(eta = frac{1}{beta})时，近端梯度下降法具有(mathcal{O}(e^{-frac{t}{Q}}))的线性收敛速率：

[f(w^t) - f(w^*) leqslant frac{beta}{2}e^{-frac{t}{Q}} lVert w^0 - w^*rVert^2 ]

其中(Q = frac{beta}{alpha})为(l)函数的条件数。

4 Frank-Wolfe算法

4.1 算法描述

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

[begin{aligned} v^t & = text{argmin}_{vinmathcal{W}}left[ f(w^t) + nabla f(w^t)^T(v - w^t) right]\ & = text{argmin}_{vin mathcal{W}} nabla f(w^t)^Tv end{aligned} ]

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

[w^{t+1} = (1-gamma^t)w^t + gamma^tv^t ]

如下图所示：

Frank-Wolfe算法描述如下：

4.2 收敛性分析

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

Frank-Wolfe法收敛性 假设目标函数中的(f)函数是(mathbb{R}^d)上的凸函数，且(beta)-光滑，当加权系数(gamma^t = frac{2}{t+1})时，Frank-Wolfe算法具有(mathcal{O}(frac{1}{t}))的次线性收敛速率：

[f(w^t) - f(w^*) leqslant frac{2beta D^2}{t} ]

其中(D = underset{w, v in mathcal{W}}{text{sup}}lVert w - v rVert)。
由于Frank-Wolfe算法的收敛速率和投影次梯度下降法相同，可以依据要解决问题中的投影计算是否困难，在两种算法中选择一种使用。

5 Nesterov加速法

5.1 算法描述

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

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

当任意时刻(t)，对当前状态(w^t)进行一步梯度迭代得到辅助变量(v^{t+1})：

[v^{t+1} = w^t - eta^t nabla f(w^t) w^{t+1} ]

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

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

[w^{t+1} = (1 + gamma^t)v^{t+1} - gamma^t v^t ]

其中(gamma^t = frac{1-sqrt{Q}}{1 + sqrt{Q}})，(Q)为条件数。

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

[w^{t+1} = (1 - gamma^t)v^{t+1} + gamma^t v^t ]

其中(gamma^t = frac{1 - lambda^t}{lambda^{t+1}})，(lambda^0 = 0), (lambda^t = frac{1 + sqrt{1 + 4{(lambda^{t-1})}^2}}{2})。

Nesterov加速算法描述如下：

5.2 收敛性分析

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

光滑凸函数收敛性 假设目标函数(f: mathbb{R}^d rightarrow mathbb{R})是凸函数，并且(beta)-光滑，当步长(eta = frac{1}{beta})时，Nesterov加速法能够将收敛速率提高到(mathcal{O}({frac{1}{t^2}}))（不过仍是次线性收敛速率）：

[f(w^t) - f(w^*) leqslant frac{2beta lVert w^0 - w^*rVert^2}{t^2} ]

光滑强凸函数收敛性 假设目标函数(f: mathbb{R}^d rightarrow mathbb{R})是(alpha)-强凸函数，并且(beta)-光滑，当步长(eta = frac{1}{beta})时，Nesterov加速法能够将收敛速率提高到(mathcal{e^{-frac{t}{sqrt{Q}}}})（不过仍是线性收敛速率）：

[f(w^t) - f(w^*) leqslant frac{alpha + beta}{2}e^{-frac{t}{sqrt{Q}}} lVert w^0 - w^*rVert^2 ]

其中(Q = frac{beta}{alpha})为条件数。

6 坐标下降法

6.1 算法描述

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

[w^{t+1}_j = underset{zin mathcal{W}_j}{text{arg min}}f(w^t_1,...,w^t_{j-1}, z, w^t_{j+1},...,w^t_d) ]

其中，(mathcal{W}_j)为第(j)个维度块的约束域。

对于维度的选择，坐标下降法一般遵循以下本征循环选择规则（Essential Cyclic Rule）：存在一个常数(rgeqslant 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.