线搜索

最优化问题中，线搜索 是一种寻找目标函数 ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ 的局部最小值 ${\displaystyle \mathbf {x} ^{*}}$ 的近似方法。它是最基础的迭代近似方法之一，另一种是置信域方法。

线搜索近似首先找到一个使目标函数 ${\displaystyle f}$ 下降的方向，然后计算 ${\displaystyle \mathbf {x} }$ 应该沿着这个方向移动的步长。下降方向可以通过多种方法计算，比如梯度下降法，牛顿法和拟牛顿法（英语：Quasi-Newton method）。计算出的步长不一定是精确的。

应用举例

以一个梯度法作为例子，其中第四步中使用到了线搜索。

1. 令迭代计数器 ${\displaystyle \displaystyle k=0}$，为最小值做一个初始估计 ${\displaystyle \mathbf {x} _{0}}$
2. 重复以下步骤：
3.     计算下降方向（英语：descent direction） ${\displaystyle \mathbf {p} _{k}}$
4.     选择 ${\displaystyle \displaystyle \alpha _{k}}$ 以在 ${\displaystyle \alpha \in \mathbb {R} _{+}}$ 上粗略地最小化 ${\displaystyle h(\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$
5.     更新 ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}}$, 以及 ${\displaystyle \displaystyle k=k+1}$
6. 直到 ${\displaystyle \|\nabla f(\mathbf {x} _{k})\|}$ 小于容忍度。

在第四步的线搜索中算法可以通过解方程 ${\displaystyle h'(\alpha _{k})=0}$ 来精确地，或者只是通过寻找一个 ${\displaystyle h}$ 的充分下降来粗略地最小化 ${\displaystyle h}$。前者的一个例子是共轭梯度法。后者被称作不精确线搜索，有很多种实现方法，比如回溯线搜索（英语：backtracking line search）或者是使用沃尔夫条件（英语：Wolfe conditions）。

与其它的最优化方法类似，线搜索也可以跟模拟退火结合以越过一些局部最小值。

算法

直接搜索方法

这种方法里，必须先把最小值括在一个范围内，也就是说这个算法必须能够找到 ${\displaystyle x_{1}}$ 和 ${\displaystyle x_{2}}$ 使得要找的最小值在它们之间。接着通过计算这个区间内部的两个点 ${\displaystyle x_{3}}$ 和 ${\displaystyle x_{4}}$，把区间分成几个子区间，抛弃掉外面两个点中与 ${\displaystyle x_{3}}$ 和 ${\displaystyle x_{4}}$ 中函数值更小的那个点不相邻的那一个。接下来的每一步中，只需要计算 额外的一个内部的点。在各种划分区间的方法中，^[1] 黄金分割法是一种特别简单而高效的方法，它的划分比例在搜索进行中始终保持不变。

${\displaystyle {\frac {1}{\phi }}(x_{2}-x_{1})=x_{4}-x_{1}=x_{2}-x_{3}=\phi (x_{2}-x_{4})=\phi (x_{3}-x_{1})=\phi ^{2}(x_{4}-x_{3})}$ where ${\displaystyle \phi ={\frac {1}{2}}(1+{\sqrt {5}})\approx 1.618}$

参阅

• 割线法
• 牛顿法
• 黄金分割法

参考

1. Box, M. J.; Davies, D.; Swann, W. H. Non-Linear optimisation Techniques. Oliver & Boyd. 1969.