数值计算之 线搜索法，Armijo，Wolfe，Goldstein条件，回溯法

前言

本篇是基于梯度的优化方法的补充篇

梯度法的步长

梯度下降法、牛顿法、拟牛顿法的主要目的都是求出增量方向。求出增量方向后，如果使用固定步长进行更新，当步长太大导致优化函数与其泰勒展开偏差太大时，可能出现优化函数不降反增的情况，导致迭代不收敛。

因此在获得增量方向后，还需要确定迭代的步长。常用的方法是线搜索法。

线搜索法

线搜索法在求出优化函数 f ( x ) f(\bf x) f(x)在 x k \bf x_k xk​的增量方向后，构建以下问题： min ⁡ α ϕ ( α ) = f ( x k + α p k ) \min_{\alpha} \quad \phi(\alpha)=f({\bf x_k}+\alpha {\bf p_k}) αmin​ϕ(α)=f(xk​+αpk​)

构造的函数是一元函数，其极值点处的导数为零： ϕ ′ ( α ) = ∇ f T ( x k + α p k ) p k = 0 \phi'(\alpha)=\nabla f^T({\bf x_k}+\alpha{\bf p_k}){\bf p_k}=0 ϕ′(α)=∇fT(xk​+αpk​)pk​=0 这样就能获得步长的精确解，也就是所谓的精确线搜索方法。但是实际操作中，如果梯度没有解析式，那么上面这个方程的解的计算是很困难的。

非精确线搜索法

非精确线搜索法不需要找到精确的步长，而是希望找到一个能够使优化函数 f f f稳定收敛并且下降速度较快的步长。此时的步长 α \alpha α通常存在于一个或数个区间内。

Armijo条件

Armijo条件又被称为充分下降条件，是使得 f f f稳定收敛的充分条件，也是最简单的条件。

如下图所示，实线是函数 ϕ ( α ) = f ( x k + α p k ) \phi(\alpha)=f({\bf x_k}+\alpha {\bf p_k}) ϕ(α)=f(xk​+αpk​)的图像，虚线 l ( α ) l(\alpha) l(α)表达式为： ϕ ′ ( α ) = ∇ f T ( x k + α p k ) p k l ( α ) = ϕ ( 0 ) + c 1 ϕ ′ ( 0 ) ( x − x k ) , 0 < c 1 < 1 \phi'(\alpha)=\nabla f^T({\bf x_k}+\alpha{\bf p_k}){\bf p_k} \\ \quad \\ l(\alpha)=\phi({0})+c_1\phi'(0)({\bf x-x_k}),0