凸优化： 梯度下降、回溯线搜索（Backtracking line search）

机器学习或强化学习的很多算法直接或间接地使用了最优化（Optimization）算法（如回溯线搜索、信赖域等）。例如，强化学习中引入信赖域方法产生了TPRO（Trust Region Policy Optimization）算法、在训练机器学习模型的过程中，求最小化损失函数时应用了线搜索的方法。为了更好的理解这些知识，本文主要对梯度下降和线搜索进行总结。

在最优化问题中，找函数f(x)的一个局部最小值 x ∗ x^{*} x∗ 有两种基本迭代方法：线搜索和信赖域。本质上它们的作用都是在优化迭代过程中从当前点找寻下一点。它们的最大区别是先确定步长还是先确定方向。线搜索（Line search）方法先确定方向再确定步长，而信赖域(Trust region)方法则先把搜索范围缩小到一个小的范围，小到能够用另一个函数（Model function）去近似目标函数（Objective function），然后通过优化这个model function来得到参数更新的方向及步长。

本文从凸优化问题中的无约束最小化问题引出线搜索。在凸优化问题中，无约束最小化问题（unconstrained minimization problem），数学描述为

m i n i m i z e    f ( x ) minimize \;f(x) minimizef(x)

其中函数f(x)是凸的，且二阶连续可微。

如果是只想了解线搜索、回溯线搜索，可以跳过下面的下降方法部分。

所有的无约束最小化算法都会生成一个最小化序列 x 1 , x 2 , . . . , x n x^{1},x^{2},...,x^{n} x1,x2,...,xn,其中，

x ( k + 1 ) = x ( k ) + t ( k ) Δ x ( k ) x^{(k+1)} = x^{(k)} +t^{(k)} \Delta x^{(k)} x(k+1)=x(k)+t(k)Δx(k)

且 t ( k ) > 0 t^{(k)} > 0 t(k)>0 （除了当 x ( k ) x^{(k)} x(k) 是最优时）。其中， Δ x ( k ) \Delta x^{(k)} Δx(k) 称为搜索方向或下降方向；k=0，1，2，…表示迭代次数。标量 t ( k ) > 0 t^{(k)} > 0 t(k)>0 称为第k次迭代的步长（step size），上式称为下降更新。

注： 上述所谓最小化序列 x 1 , x 2 , . . . , x n x^{1},x^{2},...,x^{n} x1,x2,...,xn 是指使f(x) 最小化的x的离散点。

所有的下降方法都有，

f ( x ( k + 1 ) ) < f ( x ( k ) ) f(x^{(k+1)}) < f(x^{(k)} ) f(x(k+1))0 Δx(k)>0 ），反之亦然。如下图所示，

Δ x ( k ) \Delta x^(k) Δx(k) 的方向和 ∇ f ( x ( k ) ) \nabla f(x^{(k)}) ∇f(x(k)) 的方向相反如下图所示， Δ x ( k ) \Delta x^(k) Δx(k) 和 − ∇ f ( x ( k ) ) -\nabla f(x^(k)) −∇f(x(k)) (梯度反方向) 构成锐角。我们把这个方向称为下降方向（descent direction）

一般下降方法算法如下：

上述算法很简单，第一步，找到下降方向，根据 ∇ f ( x ( k ) Δ x ( k ) < 0 \nabla f(x^{(k)} \Delta x^{(k)} < 0 ∇f(x(k)Δx(k) 0 a_{k} >0 ak​>0, 使得 f ( x k + a k p k ) < f ( x k ) f(x_{k}+a_{k}p_{k})0 ak​>0 } 找步长 a k a_{k} ak​ 使f(x)最小化，即 f ( x k + a k p k ) < f ( x k ) f(x_{k}+a_{k}p_{k})0} {argmin} f(x_{k}+a_{k}p_{k}) \tag{2.1} ak​=ak​>0argmin​f(xk​+ak​pk​)(2.1)

在梯度下降算法中，上式中的下降方向就是梯度的反方向（具体见第一部分），即 p k = − ∇ f ( x ) p_{k} = -\nabla f(x) pk​=−∇f(x) ,为了与第一部分保持符号统一，上式中的步长 a k a_{k} ak​ ，用t替换，得到梯度下降算法中的精确线搜索在每次迭代中沿梯度方向的步长t，

t = a r g m i n t > 0 f ( x − t ∇ f ( x ) ) (2.2) t = \underset {t >0} {argmin} f(x-t \nabla f(x)) \tag{2.2} t=t>0argmin​f(x−t∇f(x))(2.2)

梯度下降算法中的精确线搜索如下图所示，

精确线搜索实际用得比较少

设 g ( t ) = f ( x − t ∇ f ( x ) ) g(t)=f(x-t \nabla f(x)) g(t)=f(x−t∇f(x)) （即当方向确定时，变成了关于步长t的函数）,上式就是求g(t)的关于t的最小值。在梯度下降算法求f(x)的最小值过程中用到了精确线搜索来计算步长，而精确线搜索需要求g(t)的最小值。所以只有当单变量的最小化问题的计算成本比计算搜索方向的成本低时，才使用精确线搜索。因此，在实际应用中，用得比较多的是回溯线搜索。

2.2 回溯线搜索（Backtracking line search，BLS）

在介绍回溯线搜索之前，先介绍Wolfe conditions和 Goldstein conditions。

2.2.1 步长约束条件 在计算步长 a k a_{k} ak​ 时,我们面临一个权衡：我们既想选择一个 a k a_{k} ak​ 使得目标函数f大幅减小，但同时我们又不想花太多时间来选择 a k a_{k} ak​ 。通俗的说就是存在一个矛盾：既想通过选择更多的 a k a_{k} ak​ 来找到一个 a k a_{k} ak​使得目标函数f大幅减小，但是选择的次数太多又会影响效率。一个理想的选择是全局最小化单变量函数 ϕ ( . ) \phi(.) ϕ(.) ,其定义如下：

ϕ ( a ) = f ( x k + a p k ) , a > 0 , (2.3) \phi(a) = f(x_{k}+a p_{k}), \quad a>0, \tag{2.3} ϕ(a)=f(xk​+apk​),a>0,(2.3)

但是，求式2.3的全局最小耗费的计算成本太高。更实际的做法是使用不精确线搜索来确定一个步长使得目标函数以最小的代价取得足够的减小。

我们可以对 a k a_{k} ak​ 加一个简单的条件，即要求f减小： f ( x k + a k p k ) < f ( x k ) f(x_{k}+a_{k} p_{k}) < f(x_{k}) f(xk​+ak​pk​)