黃金分割搜索

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

黃金分割搜索示意圖

內容

基本概念

上圖表示了算法中找最小值的一個步驟。$f(x)$的函數值位於垂直坐標軸上，參數x位於水平坐標軸。已經有三個位於函數$f(x)$上的點的值被計算出來。: $x_{1}$，$x_{2}$，和$x_{3}$。可見$f_{2}$小於$f_{1}$和$f_{3}$，所以很明顯的，最小值處於$x_{1}$和$x_{3}$之間。

接下來的步驟是通過計算函數位於另一個點$x4$的值。在最大的區間選擇$x4$會更有效率，例如：$x_{2}$和$x_{3}$之間。從圖中我們可以看出，如果函數的值落在$f_{4a}$的話，最小值落於$x_{1}$和$x_{4}$之間，並且新的一組點將會是$x_{1}$和$x_{2}$和$x_{4}$。然而如果函數的值為$f_{4b}$的話，新的一組點將會是$x_{2}$和$x_{4}$和$x_{3}$。因此，無論是哪種情況，我們都可以建立一個新的更狹窄的區間，用於搜索函數的最小值。

點的選擇

由圖可知，新的區間會介於$x_{1}$和$x_{4}$，長度為a+c，或者介於$x_{2}$和$x_{3}$，長度為$b$。黃金分割搜索要求這些區間是相等的。若不是如此，較寬的區間會被使用很多次，降低了收斂率。為了確保$b$ = $a$ + $c$，算法應確保$x_{4}$ = $x_{1}$ - $x_{2}$ + $x_{3}$。

然而$x_{2}$的確定仍是一個問題。我們避免了$x_{2}$非常接近$x_{1}$或者$x_{3}$的情況，確保了每一次迭代區間寬度會縮小同樣的比例。

為了確保計算$f(x_{4})$後的值與之間的成比例，假設$f(x_{4})$的值為$f_{4}a$，且我們新的一組點為$x_{1}$，$x_{2}$和$x_{4}$，則必須使：

${\frac {c}{a}}={\frac {a}{b}}$。然而，如果$f(x_{4})$的值為$f_{4}b$，並且我們新的一組點為$x_{2}$，$x_{4}$和$x_{3}$，則必須使：

${\frac {c}{b-c}}={\frac {a}{b}}$。結合$b$ = $a$ + $c$可解得

${\frac {b}{a}}=\varphi$

而φ就是黃金比例：

$\varphi ={\frac {1+{\sqrt {5}}}{2}}=1.618033988\ldots$

這就是這個算法被稱為黃金分割搜索的原因。