适用于,一维单峰函数搜索最小值或者最大值。
核心思想:
基于函数是一维单峰的特性,通过三个点来判断函数的大致走向,并且可以知道最小值一定落在已知最小点的相邻两点所界定的区间内。所以可以通过在区间内插入新的点,来逐步缩小最小值的所在的区间。
例子:
如图所示,如果点$x_4$的值为$f_{4a}$,则最小值落在$[x_1,x_4]$,相反如果值为$f_{4b}$的话,则最小值落在$[x_2,x_3]$。
点的选取:
为了使得每次搜索的均衡,则要求$a+c=b$。
为了确保每一次搜索后,最小值所在的区间能按相同的比例缩小,则要求:$c/a=a/b$。
联立两式可得,$\frac{a}{b}=\frac{1+\sqrt{5}}{2}=1.618033988…$
这个正是黄金比例,所以该算法叫做黄金分割搜索。