線搜尋

最最佳化問題中，線搜尋是一種尋找目標函式的局部最小值的近似方法。它是最基礎的疊代近似方法之一，另一種是置信域方法。

基本介紹

• 中文名：線搜尋
• 外文名：line search
• 套用：計算機算法
• 作用：最佳化方法

定義

線搜尋是一種尋找目標函式 的局部最小值的近似方法。

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

方法

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

套用

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

1. 令疊代計數器 k=0，為最小值做一個初始估計 x0；
2. 重複以下步驟；
3. 計算下降方向pk；
4. 選擇以在R上粗略地最小化

5.更新

6.直到小於容忍度。

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

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