黄金分割搜索是一种通过不断缩小单峰函数的最值的已知范围，从而找到最值的方法。它的名称源于这个算法保持了间距具有黄金分割特性的三个点。这个算法与斐波那契搜索和二分查找关系紧密。黄金分割搜索是由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_4a，且我们新的一组点为x_1，x_2和x_4，则必须使：
:\frac{c}{a}=\frac{a}{b}。然而，如果f(x_4)的值为f_4b，并且我们新的一组点为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
这就是这个算法被称为黄金分割搜索的原因。
3.终止条件 |b-a|<ε
4.递归算法
5.斐波那契搜索
6.参阅
评论 (0)