黃金分割搜尋

概況

黃金分割搜尋是一種通過不斷縮小單調函式的最值的已知範圍，從而找到最值的方法。它的名稱源於這個算法保持了間距具有黃金分割特性的三個點。這個算法與斐波那契搜尋和二分查找關係緊密。黃金分割搜尋是由Kiefer提出的，而斐波那契搜尋是由Avriel和Wilde所提出。

內容

基本概念

上圖表示了算法中找最小值的一個步驟。f(x)的函式值位於垂直坐標軸上,參數x位於水平坐標軸。已經有三個位於函式f(x)上的點的值被計算出來。: x1, x2, 和x3。可見f2小於 f1和f3, 所以很明顯的，最小值處於x1和x3之間。
接下來的步驟是通過計算函式位於另一個點x4的值。在最大的區間選擇x4會更有效率，例如：x2和x3之間。從圖中我們可以看出，如果函式的值落在f4a的話，最小值落於x1和x4之間，並且新的一組點將會是x1和x2和x4。然而如果函式的值為f4b的話，新的一組點將會是x2和x4和x3。因此，無論是哪種情況，我們都可以建立一個新的更狹窄的區間，用於搜尋函式的最小值。