5.3 数值优化基础:线搜索 | 自动驾驶小白说

5.3.1 线搜索概念

对于优化问题，我们将求解 f(x) 的最小值点的过程比喻成下山的过程．假设一个人处于某点 x 处， f(x) 表示此地的高度，为了寻找最低点，在点 x 处需要确定如下两件事情：第一，下一步该向哪一方向行走；第二，沿着该方向行走多远后停下以便选取下一个下山方向．以上这两个因素确定后，便可以一直重复，直至到达 f(x) 的最小值点．

在更新公式中, 是第k次迭代的步长, 是下降方向. 寻找合适的步长一般分为两种方法:

精确线搜索算法

通过构造一个最优化问题, 来寻找最佳步长. 如下:

显而易见的是, 通过最优化问题选取通常需要很大计算量，所以在实际应用中较少使用．

非精确线搜索算法

如果不追求每一次迭代都找到最佳步长, 而是转而求其次: 通过一些不等式, 判断步长是否合适, 通过缩放步长, 来快速找到满足不等式的步长.

这种方法计算简单, 所以大量运用在线搜索中. 这些不等式也被称为线搜索准则, 接下来将介绍几个常见的线搜索准则.

5.3.2 Armijo准则

若步长满足不等式, 则称其满足Armijo 准则

其中, 是一个常数.

接下来我们将借助辅助函数, 也就是执行该步长后的f函数值.

Armijo准则的几何意义如图, 它要求步长必须在虚线之下. 也就是说它是为了保证每一步迭代后的函数值下降.

当初始步长不满足准则是, 我们一般使用一些简单的缩放来寻找满足要求的步长. 上图就是常见的回退法, 当步长不满足要求时, 给定一个, 不停的缩小步长直到其满足准则.

因为步长是从大变小的, 这保证了尽可能的大.

5.3.2 Goldstein准则

Armijo准则非常容易满足, 因为它几乎只保证了函数值会下降.

为了克服 Armijo 准则的缺陷，我们需要引入其他准则来保证每一步的 αk 不会太小．既然 Armijo 准则只要求点 (α, ϕ(α)) 必须处在某直线下方，我们也可使用相同的形式使得该点必须处在另一条直线的上方．这就是Armijo-Goldstein 准则，简称 Goldstein 准则:

若步长满足不等式, 则称其满足Goldstein准则. 其中, 是一个常数.

Goldstein准则的几何意义如图, 它要求步长必须在两条虚线之间. 在保证函数值下降的同时, 也保证了步长不会过分的小. 这保证每一步迭代后的函数值充分下降.

5.3.3 Wolfe准则

Goldstein 准则能够使得函数值充分下降，但是它可能避开了最优的函数值. 上面的图也可以看到, 最佳步长并不在之间. 因此引入了Wolfe准则:

在准则中，第一个不等式即是 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.