跳至內容

線搜索

維基百科,自由的百科全書

最優化問題中,線搜索 是一種尋找目標函數 局部最小值 的近似方法。它是最基礎的迭代近似方法之一,另一種是置信域方法

線搜索近似首先找到一個使目標函數 下降的方向,然後計算 應該沿著這個方向移動的步長。下降方向可以通過多種方法計算,比如梯度下降法牛頓法擬牛頓法英語Quasi-Newton method。計算出的步長不一定是精確的。

應用舉例

[編輯]

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

  1. 令迭代計數器 ,為最小值做一個初始估計
  2. 重複以下步驟:
  3.     計算下降方向英語descent direction
  4.     選擇 以在 上粗略地最小化
  5.     更新 , 以及
  6. 直到 小於容忍度。

在第四步的線搜索中算法可以通過解方程 精確地,或者只是通過尋找一個 的充分下降來粗略地最小化 。前者的一個例子是共軛梯度法。後者被稱作不精確線搜索,有很多種實現方法,比如回溯線搜索英語backtracking line search或者是使用沃爾夫條件英語Wolfe conditions

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

算法

[編輯]

直接搜索方法

[編輯]

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

where

參閱

[編輯]

參考

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