5708 Rate this article:
No rating

A recursive one-dimensional search routine

Ron Kneusel recently shared with our PWUISATAI group a recursive 1D golden section search routine (no derivatives necessary) that he's used to locate function minima. Here's the source code for Ron's routine, GOLDENSECTIONSEARCH. To use it, say I want to find the value of x that minimizes the function:
f(x) = sin(x) cos(2x)
on the domain [0, 2π]. Start by writing an IDL function to represent f(x):
function f, x
   compile_opt idl2

   return, sin(x)*cos(2*x)
This is a technique used in IDL curve-fitting routines like CURVEFIT, LMFIT, SVDFIT, etc. To help understand the output of GOLDENSECTIONSEARCH, visualize the graph of f(x) over [0, 2π] with:
IDL> n = 100
IDL> x = (2*!pi/(n-1))*findgen(n)
IDL> p = plot(x, f(x), xstyle=1, $
>      name='sin(x) cos(2x)', $
>      xtitle='x', $
>      ytitle='f(x)', $
>      title='Finding minima with a golden section search')
IDL> lgd = legend(target=p, position=[0.85,0.25], shadow=0)
IDL> xleft = 0.0
IDL> xright = 2*!pi
IDL> xmid = 4.2
IDL> tol = 1e-3
IDL> func = 'f'
IDL> minx = goldensectionsearch(xleft, xmid, xright, tol, func)
The parameters xleft and xright are the bounds of the search, while xmid is a point chosen between the bounds. For a function with local minima, GOLDENSECTIONSEARCH is sensitive to the choice of xmid. The algorithm iterates on a solution until candidates within tol are achieved. The result:
IDL> print, minx
The result, visualized:
IDL> q = plot([minx,minx], p.yrange, /overplot, color='red')
The result of a golden section search