人生如逆旅，我亦是行人。 — 宋 苏轼
🏰代码及环境配置：请参考 环境配置和代码运行!
上一节的梯度下降法和牛顿法测试中, 采用了固定的步长, 我们会发现固定步长有以下缺点:
- 远离极值点时, 如果步长过小, 下降可能很慢
- 接近极值点时, 如果步长过大, 可能会越过极值点达到更远的点
那么有没有什么方法, 可以得到最佳步长呢? 线搜索就是确定步长的常见方式.
5.3.1 线搜索概念
对于优化问题，我们将求解 f(x) 的最小值点的过程比喻成下山的过程．假设一个人处于某点 x 处， f(x) 表示此地的高度，为了寻找最低点，在点 x 处需要确定如下两件事情：第一，下一步该向哪一方向行走；第二，沿着该方向行走多远后停下以便选取下一个下山方向．以上这两个因素确定后，便可以一直重复，直至到达 f(x) 的最小值点．
x k + 1 = x k + α k d k x^{k+1}=x^k+\alpha_k d^k xk+1=xk+αkdk
在更新公式中, α k \alpha_k αk是第k次迭代的步长, d k d^k dk是下降方向. 寻找合适的步长 α k \alpha_k αk一般分为两种方法:
- 精确线搜索算法
通过构造一个最优化问题, 来寻找最佳步长 α k \alpha_k αk. 如下:
α k = arg min α > 0 ϕ ( α ) , \alpha_k=\underset{\alpha>0}{\arg \min } \phi(\alpha), αk=α>0argminϕ(α),
显而易见的是, 通过最优化问题选取 α k \alpha_k αk通常需要很大计算量，所以在实际应用中较少使用．
- 非精确线搜索算法
如果不追求每一次迭代都找到最佳步长, 而是转而求其次: 通过一些不等式, 判断步长是否合适, 通过缩放步长, 来快速找到满足不等式的步长.
这种方法计算简单, 所以大量运用在线搜索中. 这些不等式也被称为线搜索准则, 接下来将介绍几个常见的线搜索准则.
5.3.2 Armijo准则
若步长 α \alpha α满足不等式, 则称其满足Armijo 准则
f ( x k + α d k ) ⩽ f ( x k ) + c 1 α ∇ f ( x k ) T d k f\left(x^k+\alpha d^k\right) \leqslant f\left(x^k\right)+c_1 \alpha \nabla f\left(x^k\right)^{\mathrm{T}} d^k f(xk+αdk)⩽f(xk)+c1α∇f(xk)Tdk
其中 c 1 ∈ ( 0 , 1 ) c_1 \in(0,1) c1∈(0,1), 是一个常数.
接下来我们将借助辅助函数 ϕ ( α ) = f ( x k + α d k ) \phi(\alpha)=f\left(x^k+\alpha d^k\right) ϕ(α)=f(xk+αdk), 也就是执行该步长后的f函数值.
Armijo准则的几何意义如图, 它要求步长 α \alpha α必须在虚线之下. 也就是说它是为了保证每一步迭代后的函数值下降.
当初始步长不满足准则是, 我们一般使用一些简单的缩放来寻找满足要求的步长. 上图就是常见的回退法, 当步长 α \alpha α不满足要求时, 给定一个 γ ∈ ( 0 , 1 ) \gamma \in (0,1) γ∈(0,1), 不停的缩小步长直到其满足准则.
因为步长 α \alpha α是从大变小的, 这保证了 α \alpha α尽可能的大.
5.3.2 Goldstein准则
Armijo准则非常容易满足, 因为它几乎只保证了函数值会下降.
为了克服 Armijo 准则的缺陷，我们需要引入其他准则来保证每一步的 αk 不会太小．既然 Armijo 准则只要求点 (α, ϕ(α)) 必须处在某直线下方，我们也可使用相同的形式使得该点必须处在另一条直线的上方．这就是Armijo-Goldstein 准则，简称 Goldstein 准则:
f ( x k + α d k ) ⩽ f ( x k ) + c α ∇ f ( x k ) T d k f ( x k + α d k ) ⩾ f ( x k ) + ( 1 − c ) α ∇ f ( x k ) T d k \begin{aligned}& f\left(x^k+\alpha d^k\right) \leqslant f\left(x^k\right)+c \alpha \nabla f\left(x^k\right)^{\mathrm{T}} d^k \\& f\left(x^k+\alpha d^k\right) \geqslant f\left(x^k\right)+(1-c) \alpha \nabla f\left(x^k\right)^{\mathrm{T}} d^k\end{aligned} f(xk+αdk)⩽f(xk)+cα∇f(xk)Tdkf(xk+αdk)⩾f(xk)+(1−c)α∇f(xk)Tdk
若步长 α \alpha α满足不等式, 则称其满足Goldstein准则. 其中 c ∈ ( 0 , 1 / 2 ) c \in(0,1/2) c∈(0,1/2), 是一个常数.
Goldstein准则的几何意义如图, 它要求步长 α \alpha α必须在两条虚线之间 ( α 1 , α 2 ) (\alpha_1,\alpha_2) (α1,α2). 在保证函数值下降的同时, 也保证了步长 α \alpha α不会过分的小. 这保证每一步迭代后的函数值充分下降.
5.3.3 Wolfe准则
Goldstein 准则能够使得函数值充分下降，但是它可能避开了最优的函数值. 上面的图也可以看到, 最佳步长并不在 ( α 1 , α 2 ) (\alpha_1,\alpha_2) (α1,α2)之间. 因此引入了Wolfe准则:
f ( x k + α d k ) ⩽ f ( x k ) + c 1 α ∇ f ( x k ) T d k ∇ f ( x k + α d k ) T d k ⩾ c 2 ∇ f ( x k ) T d k \begin{aligned}& f\left(x^k+\alpha d^k\right) \leqslant f\left(x^k\right)+c_1 \alpha \nabla f\left(x^k\right)^{\mathrm{T}} d^k \\& \nabla f\left(x^k+\alpha d^k\right)^{\mathrm{T}} d^k \geqslant c_2 \nabla f\left(x^k\right)^{\mathrm{T}} d^k\end{aligned} f(xk+αdk)⩽f(xk)+c1α∇f(xk)Tdk∇f(xk+αdk)Tdk⩾c2∇f(xk)Tdk
在准则中，第一个不等式即是 Armijo 准则，而第二个不等式(6.1.4b) 则是 Wolfe 准则的本质要求。注意到 ∇f(xk+αdk)Tdk 恰好就是 ϕ(α) 的导数，Wolfe 准则实际要求 ϕ(α) 在点 α 处切线的斜率不能小于 ϕ′(0) 的 c2 倍. 如图6.3所示，在区间 [α1,α2] 中的点均满足 Wolfe 准则. 注意到在 ϕ(α) 的极小值点 α* 处有 ϕ′(α*) = ∇f(xk+αdk)Tdk* = 0 ，因此 *α*永远满足条件. 而选择较小的 c1 可使得 α 同时满足条件(6.1.4a),即 Wolfe 准则在绝大多数情况下会包含线搜索子问题的精确解。在实际应用中, 参数 c2 通常取为 0.9 .
Wolfe准则的几何意义如题, 可以看到, 最佳步长处在Wolfe准则定义的区间 [α1,α2] 内.
下一节, 我们将使用线搜索准则, 改进之前的梯度下降法, 并对比不同线搜索准则的效果.
参考链接
- 刘浩洋. 最优化: 建模, 算法与理论. 高等教育出版社, 2020.
_百度推广优化方案_郑州官网网络营销外包)
