知识点：线搜索方法

知识点概述

线搜索是设计迭代优化算法的一个基本框架。在每一步迭代中，算法首先确定一个下降方向，然后沿这个方向进行一维搜索（线搜索），以找到一个合适的步长，使得目标函数值有“足够”的下降。

迭代框架: $x_{k + 1} = x_{k} + α_{k} d_{k}$
- 下降方向 (Descent Direction) $d_{k}$ : 一个使得函数值在当前点 $x_{k}$ 附近可以下降的方向。对于可微函数，只要满足 $\nabla f (x_{k})^{T} d_{k} < 0$ ，就是一个下降方向。例如，最速下降方向 $d_{k} = - \nabla f (x_{k})$ 。
- 步长 (Step Length) $α_{k}$ : 沿着方向 $d_{k}$ 移动的距离。
线搜索的任务: 确定步长 $α_{k}$ 。
- 精确线搜索: 求解 $min_{α > 0} f (x_{k} + α d_{k})$ 。这本身是一个一维优化问题，计算成本高，实践中很少使用。
- 非精确线搜索: 寻找一个能让函数值有“满意下降”且计算成本不高的步长。
Armijo-Wolfe 条件: 一组保证步长“足够好”的常用准则。
1. Armijo 条件 (Sufficient Decrease): $f (x_{k} + α_{k} d_{k}) \leq f (x_{k}) + c_{1} α_{k} \nabla f (x_{k})^{T} d_{k}$ (其中 $c_{1} \in (0, 1)$ )。保证函数值有足够的下降，防止步长太小。
2. Wolfe 条件 (Curvature Condition): $\nabla f (x_{k} + α_{k} d_{k})^{T} d_{k} \geq c_{2} \nabla f (x_{k})^{T} d_{k}$ (其中 $c_{1} < c_{2} < 1$ )。保证步长不会太小，排除了函数值下降不明显的点。