黄金分割搜索

适用于,一维单峰函数搜索最小值或者最大值。

核心思想:

基于函数是一维单峰的特性,通过三个点来判断函数的大致走向,并且可以知道最小值一定落在已知最小点的相邻两点所界定的区间内。所以可以通过在区间内插入新的点,来逐步缩小最小值的所在的区间。

例子:

如图所示,如果点$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…$

这个正是黄金比例,所以该算法叫做黄金分割搜索。


扩展阅读:


  转载请注明: 石锅拌饭 黄金分割搜索

 上一篇
Five-point stencil Five-point stencil
Five-point stencil 在一维和二维中的形式: 在数值分析中,给定一个一维或二维的网格,某一点的 Five-point stencil(FPS)即为该点加上它邻近的四个点。FPS主要用于求解导数在格点上的有限差分近似。 On
2018-12-04
下一篇 
解决numpy 0d arrays error 解决numpy 0d arrays error
使用numpy array时,可能会遇到 “iteration over a 0-d array” 的错误。 例1:import numpy as np a = 1 a = np.asarray(a) for i in a: prin
2018-12-04
  目录