凸优化: 回溯直线搜索 Backtracking line search

深度学习优化方法层出不穷，总结起来基本不外乎在方向和步长(或者说学习率)这两方面下功夫。深度学习是非凸优化问题，本文简单介绍下凸优化中关于步长选择的一种方法：回溯直线搜索（Backtracking line search）。

凸优化问题特点是局部最优即是全局最优，可采用梯度下降方法取得最优解。搜索方向为目标函数的负梯度方向(沿负梯度方向下降最快)，步长由我们将要讨论的方法确定。方向决定了我们能否到达最优点，而步长决定了我们能否快速到达。太小的步长导致收敛太慢，而太大的步长又可能跳过最优点，引起震荡。

首先，对于凸优化问题来说，选择极小的步长肯定是没问题的，只是比较慢而已。所以我们这里要讨论的问题就是如何步子尽可能大一些同时又能保bu证che收zhe敛dan。既然小的没问题，那我们就从大往小来搜索合适的步长，算法如下：

这里说明下上面符号意义：
目标函数：f
参变量：x
超参数：\alpha, \beta
方向: \Delta x
步长: t

那么，为什么上面的不等式可以帮助我们判断步长是否合适呢？以 t 为自变量，我们得到下图：

初始步长设为1， t=\beta t 从大到小搜索合适的步长。注意这里是寻找当前点x对应的合适步长，x是已知的， t 作为未知变量。如果上面的不等式成立，就不断迭代，直到等式不成立，此时的t作为当前x的步长,

即： f(x+t\Delta x) < f(x)+\alpha t \nabla f(x)\Delta x

即 （\frac{f(x+t\Delta x) - f(x)}{t\Delta x}) / \nabla f(x) > \alpha

令 k = \frac{f(x+t\Delta x) - f(x)}{t\Delta x}

注意 \Delta x 是下降方向(负梯度方向)，因此上面不等号反向。当t->0时，k极限为 \nabla f(x)。此时左侧 \nabla f(x) / \nabla f(x) = 1 ，不等式显然成立，这和我们前面的结论一致: t足够小是没问题的。

而我们的搜索是从大到小进行的，因此看下t比较大时的情形。 t 较大时，k可看作凸函数一条弦的斜率，上述不等式可能不成立，可能越过最优点太多，需缩小 t 进一步考察。不过，合适的t并不保证一定不会越过最优点。