黄金分割搜索

黄金分割搜索是一种通过不断缩小单峰函数最值的已知范围,从而找到最值的方法。它的名称源于这个算法保持了间距具有黄金分割特性的三个点。这个算法与斐波那契搜索和二分查找关系紧密。黄金分割搜索是由Kiefer提出的,而斐波那契搜索是由Avriel和Wilde所提出。

黄金分割搜索示意图

内容

基本概念

上图表示了算法中找最小值的一个步骤。的函数值位于垂直坐标轴上,参数x位于水平坐标轴。已经有三个位于函数上的点的值被计算出来。: ,和。可见小于,所以很明显的,最小值处于之间。

接下来的步骤是通过计算函数位于另一个点的值。在最大的区间选择会更有效率,例如:之间。从图中我们可以看出,如果函数的值落在的话,最小值落于之间,并且新的一组点将会是。然而如果函数的值为的话,新的一组点将会是。因此,无论是哪种情况,我们都可以建立一个新的更狭窄的区间,用于搜索函数的最小值。

点的选择

由图可知,新的区间会介于,长度为a+c,或者介于,长度为。黄金分割搜索要求这些区间是相等的。若不是如此,较宽的区间会被使用很多次,降低了收敛率。为了确保 = + ,算法应确保 = - +

然而的确定仍是一个问题。我们避免了非常接近或者的情况,确保了每一次迭代区间宽度会缩小同样的比例。

为了确保计算后的值与之间的成比例,假设的值为,且我们新的一组点为,则必须使:

。然而,如果的值为,并且我们新的一组点为,则必须使:
。结合 = + 可解得

而φ就是黄金比例

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

3.终止条件

4.递归算法

5.斐波那契搜索

6.参阅