黄金分割搜索

黄金分割搜索是一种通过不断缩小单峰函数的最值的已知范围，从而找到最值的方法。它的名称源于这个算法保持了间距具有黄金分割特性的三个点。这个算法与斐波那契搜索和二分查找关系紧密。黄金分割搜索是由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$

这就是这个算法被称为黄金分割搜索的原因。