跳至內容

黃金分割搜索

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

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

黃金分割搜索示意圖

內容

基本概念

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

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

點的選擇

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

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

為了確保計算後的值與之間的成比例,假設的值為,且我們新的一組點為,則必須使:

。然而,如果的值為,並且我們新的一組點為,則必須使:
。結合 = + 可解得

而φ就是黃金比例

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

3.終止條件

4.遞歸算法

5.斐波那契搜索

6.參閱