线搜索近似首先找到一个使目标函数 下降的方向，然后计算 应该沿着这个方向移动的步长。下降方向可以通过多种方法计算，比如梯度下降法，牛顿法和拟牛顿法。计算出的步长不一定是精确的。

在机器学习中，通常需要求某个函数的最值(比如最大似然中需要求的似然的最大值)。线搜索(line search)是求得一个函数f(x)的最值的两种常用迭代方法之一(另外一个是trust region)。其思想是首先求得一个下降方向,在这个方向上f(x)会下降，然后是求得f(x)在这个方向上下降的步长。求下降方向的方法有很多，比如梯度下降，牛顿方法和Quasi-Newton方法，而步长可以是固定值，也可以通过诸如回溯线搜索来求得。

1. 线搜索(line search)

线搜索是一种迭代的求得某个函数的最值的方法。对于每次迭代，线搜索会计算得到搜索的方向pk以及沿这个方向移动的步长α_k。大多数的线搜索方法都会要求 p_k 是下降方向(descent direction)，亦即需要满足以下条件：p_k^T ∇ f_k<0，这样就能够保证函数f(x)沿着这个方向是下降的。一般来说，搜索方向是

p_k=−B_k^(−1)\nabla f_k

其中B_k是一个对称非奇异矩阵。在最深下降(steepest descent)方法中，B_k是单位矩阵I，在牛顿方法(Newton)中B_k则是海森(Hessian)矩阵∇^2f(x_k))，在Quasi-Newton方法中通过迭代求得Hessian矩阵的近似矩阵。当p_k由上式定义，且Bk是正定矩阵时：

p$_k^T$p_k\nablaf=-\nablaf$_k^T$B$_k^-1$\nablaf_k<0

所以pk是下降方向(descent direction)。

2. 步长

步长α应该最小化下面的函数:

\phi(\alpha)=f(x_k+\alpha\p_k)

ϕ(α)=f(x_k+αp_k)

但是求得使上式最小的αα比较困难, 且计算量比较大, 实际常用的方法是在可接受的计算量的情况下尽可能的求得较大的步长, 以使得ϕ(α)尽可能的降低. 经典的线搜索方法通过迭代来求得α, 直至达到某个停止条件. 一般的线搜索方法都包含以下两个步骤:

    bracketing: 求得一个包含理想的步长的区间二分法或者插值法: 在这个区间内使用二分法或者插值法来求得步长

2.1 对于凸函数的二分搜索算法

如果f(x)是一个可微分的凸函数, 则我们的目标是求得α, 使得

\alpha =

α=argminf(x+λp)  （λ>0）

令ϕ(α)=f(xk+αp_k), 其中ϕ(α)是α的凸函数, 所以问题转化为求:

α¯=argminϕ(α)  （α>0）

因为ϕ(α)是凸函数, 所以ϕ′(α¯)=0ϕ′(α¯)=0. 可以得到ϕ′(α)=∇f(x+αp)Tpϕ′(α)=∇f(x+αp)Tp, 因为p是梯度下降方向, 所以ϕ′(0)<0.

假设我们知道一个α^使得ϕ′(α^)>0, 那么使得ϕ′(α¯)=0的α肯定位于(0,α^)区间内. 然后我们可以使用以下二分查找算法来求解ϕ′(α)≈0

    令k=0, α_l:=0, α_u:=α^

令α~=（αu+αl）/2, 然后计算ϕ′(α~):

    如果ϕ′(α~)>0, 则令α_u:=α~, 令k←k+1如果ϕ′(α~)<0, 则令α_l:=α~, 令k←k+1如果ϕ′(α~)=0, 停止迭代

2.2 回溯线搜索(backtracking line search)

使用二分查找法来求步长的计算复杂度很高, 因为在最小化f(x)的每次迭代中我们都需要执行一次线搜索, 而每次线搜索都要用上述的二分查找算法. 我们可以在牺牲一定的精度的条件下来加快计算速度, 回溯线搜索是一种近似线搜索算法.

首先, 我们要求每次的步长αk都使得f(x)充分的降低:

f(x_k+\alphap_k)<=f(x_k)+c_1\alpha\nablaf$_k^T$p_k

上述条件称作充分下降条件, 其中c_1∈(0,1), 一般来说c_1=10−4. 亦即f(x)的下降应该至少和α_k以及∇(f_k)^T*p_k成正比. 如下图所示, 上式的右边

f(x_k)+c_1α∇fTkpk 是一个线性函数, 可以表示为l(α).

f(x_k)+c_1*\alpha\nablaf$_k^T$p_k

充分下降条件规定只有使得ϕ(α)≤l(α))的α才满足条件. 其区间如上图所示.

单独只有充分下降条件是不够的, 因为如上图, 所有充分小的α都满足上述条件, 但是α太小会导致下降不充分, 为了排除这些小的α, 我们引入了第二个要求, 亦即曲率条件(curvature condition):

\nablaf{(x_k+\alphap_k)^T}p_k>=c_2*\alpha*\nablaf$_k^T$p_k

其中c_2∈(c_1,1). 上式的左边就是ϕ′(α_k), 右边则是ϕ′(0), 亦即上式要求ϕ′(α_k)大于等于c_2倍的ϕ′(0), 这是因为如果ϕ′(α)是很小的负数, 则我们可以在这个方向上继续使得f(x)下降更多. 如下图所示

上述两个条件合起来称作Wolfe条件:

f(x_k+\alphap_k)<=c_1\alpha\nablaf$_k^T$p_k
\nablaf{(x_k+\alphap_k)^T}p_k>=c_2\nablaf$_k^T$p_k

其中0

我们可以使用以下算法来求得满足Wolfe条件的步长αα, 其主要思想是从一个初始的步长之后逐步减少αα, 直至其满足充分下降条件, 同时可以防止αα变得太小:

    选择一个(¯α)>0,ρ,c∈(0,1);令α←α¯重复以下步骤直到:
f(x_k+\alphap_k)<=f(x_k)+c_1\alpha\nablaf$_k^T$p_k
\longleftarrow\\alpharho

3. 返回α_k=α

发展历史

1966年，Armijo, L.提出Armijo规则。该算法给出了梯度法的一般收敛定理。结果表明，通常的最陡下降和修正的最陡下降算法在某些假设下会收敛。改进的最陡下降算法允许可变步长。

1966年，回溯线搜索 (backtracking line search) 是基于Armijo–Goldstein condition设计的线搜索方法。，从一个相对较大的步长估计，沿着搜索方向移动，并迭代地缩小步长(也就是“回溯”)，基于目标函数的局部梯度，直到目标函数减小。

1969年，Wolfe, P. 提出了 曲率条件(curvature condition):，来避免曲线下降不充分的问题。

1986年，Grippo, L., Lampariello, F., & Lucidi, S.提出了牛顿法的非单调步进选择规则，可以看作是Armijo规则的推广。数值结果表明，所提出的技术可以大大节省线搜索的次数和函数计算。

2006年，Wächter, A., & Biegler, L. T.提出关于大型非线性规划的内点滤波线搜索算法。它提出了一种基于滤波器线搜索方法的非线性规划的原对偶内点算法。并在IPOPT中实现，数据集是CUTEr的954个问题进行了演示。

主要事件

年份事件相关论文1966Armijo, L.提出Armijo规则Armijo, L. (1966). Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1), 1-3.1969Grippo, L., Lampariello, F., & Lucidi, S.提出了牛顿法的非单调步进选择规则Wolfe, P. (1969). Convergence conditions for ascent methods. SIAM review, 11(2), 226-235.1986Wolfe, P. 提出了 曲率条件(curvature condition):Grippo, L., Lampariello, F., & Lucidi, S. (1986). A nonmonotone line search technique for Newton’s method. SIAM Journal on Numerical Analysis, 23(4), 707-716.2006Wächter, A., & Biegler, L. T.提出关于大型非线性规划的内点滤波线搜索算法。Wächter, A., & Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical programming, 106(1), 25-57.

发展分析

瓶颈

在line search中有一个Steepest Descent：最速下降法

    范围是变的收敛通常很缓慢数值，通常不收敛

未来发展方向

线搜索是指一类通过选择一个合理的方向向量来寻找一个已定义的非线性函数的最小值的算法。具体对于步长的选择都需要根据具体的问题和需求进行选择。

Contributor: Ruiying Cai