線搜索

最優化問題中，線搜索 是一種尋找目標函數 $f:\mathbb {R} ^{n}\to \mathbb {R}$ 的局部最小值 $\mathbf {x} ^{*}$ 的近似方法。它是最基礎的迭代近似方法之一，另一種是置信域方法。

線搜索近似首先找到一個使目標函數 $f$ 下降的方向，然後計算 $\mathbf {x}$ 應該沿着這個方向移動的步長。下降方向可以通過多種方法計算，比如梯度下降法，牛頓法和擬牛頓法。計算出的步長不一定是精確的。

應用舉例

以一個梯度法作為例子，其中第四步中使用到了線搜索。

1. 令迭代計數器 $\displaystyle k=0$，為最小值做一個初始估計 $\mathbf {x} _{0}$
2. 重複以下步驟：
3.     計算下降方向 $\mathbf {p} _{k}$
4.     選擇 $\displaystyle \alpha _{k}$ 以在 $\alpha \in \mathbb {R} _{+}$ 上粗略地最小化 $h(\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})$
5.     更新 $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}$, 以及 $\displaystyle k=k+1$
6. 直到 $\|\nabla f(\mathbf {x} _{k})\|$ 小於容忍度。

在第四步的線搜索中算法可以通過解方程 $h'(\alpha _{k})=0$ 來精確地，或者只是通過尋找一個 $h$ 的充分下降來粗略地最小化 $h$。前者的一個例子是共軛梯度法。後者被稱作不精確線搜索，有很多種實現方法，比如回溯線搜索或者是使用沃爾夫條件。

與其它的最優化方法類似，線搜索也可以跟模擬退火結合以越過一些局部最小值。

算法

直接搜索方法

這種方法裡，必須先把最小值括在一個範圍內，也就是說這個算法必須能夠找到 $x_{1}$ 和 $x_{2}$ 使得要找的最小值在它們之間。接着通過計算這個區間內部的兩個點 $x_{3}$ 和 $x_{4}$，把區間分成幾個子區間，拋棄掉外面兩個點中與 $x_{3}$ 和 $x_{4}$ 中函數值更小的那個點不相鄰的那一個。接下來的每一步中，只需要計算 額外的一個內部的點。在各種劃分區間的方法中， 黃金分割法是一種特別簡單而高效的方法，它的劃分比例在搜索進行中始終保持不變。

${\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 $\phi ={\frac {1}{2}}(1+{\sqrt {5}})\approx 1.618$

參閱

• 割線法
• 牛頓法
• 黃金分割法