线搜索

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

线搜索近似首先找到一个使目标函数 $f$ 下降的方向，然后计算 $𝐱$ 应该沿着这个方向移动的步长。下降方向可以通过多种方法计算，比如梯度下降法，牛顿法和拟牛顿法。计算出的步长不一定是精确的。

应用举例

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

1. 令迭代计数器 $k=0$，为最小值做一个初始估计 ${𝐱}_0$
2. 重复以下步骤：
3.     计算Template:Link-en ${𝐩}_k$
4.     选择 ${\alpha }_k$ 以在 $\alpha \in {ℝ}_{+}$ 上粗略地最小化 $h(\alpha )=f({𝐱}_k+\alpha {𝐩}_k)$
5.     更新 ${𝐱}_{k+1}={𝐱}_k+{\alpha }_k{𝐩}_k$, 以及 $k=k+1$
6. 直到 $\Vert \mathrm{\nabla }f({𝐱}_k)\Vert$ 小于容忍度。

在第四步的线搜索中算法可以通过解方程 $h^{\prime }({\alpha }_k)=0$ 来精确地，或者只是通过寻找一个 $h$ 的充分下降来粗略地最小化 $h$。前者的一个例子是共轭梯度法。后者被称作不精确线搜索，有很多种实现方法，比如Template:Link-en或者是使用Template:Link-en。

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

算法

直接搜索方法

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

$\frac{1}{\varphi }(x_2-x_1)=x_4-x_1=x_2-x_3=\varphi (x_2-x_4)=\varphi (x_3-x_1)={\varphi }^2(x_4-x_3)$ where $\varphi =\frac{1}{2}(1+\sqrt{5})\approx 1.618$

参阅

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