Diagram of a golden section search The golden section search is a technique for finding the extremum (minimum or maximum) of a unimodal function by successively narrowing the range of values inside which the extremum is known to exist. The technique derives its name from the fact that the algorithm maintains the function values for triples of points whose distances form a golden ratio. The algorithm is closely related to a Fibonacci search (also described below) and to a binary search. Golden section search was introduced by Kiefer (1953), and Fibonacci search by Avriel and Wilde (1966). The diagram on the right illustrates a single step in the technique for finding a minimum. The functional values of f(x) are on the vertical axis, and the horizontal axis is the x parameter. The value of f(x) has already been evaluated at the three points: x_{1}, x_{2}, and x_{3}. Since f_{2} is smaller than either f_{1} or f_{3}, it is clear that a minimum lies inside the interval from x_{1} to x_{3}. The next step in the minimization process is to "probe" the function by evaluating it at a new value of x, namely x_{4}. It is most efficient to choose x4 somewhere inside the largest interval, i.e. between x_{2} and x_{3}. From the diagram, it is clear that if the function yields f_{4a} then a minimum lies between x1 and x_{4} and the new triplet of points will be x1, x_{2}, and x_{4}. However if the function yields the value f_{4b} then a minimum lies between x_{2} and x_{3}, and the new triplet of points will be x_{2}, x_{4}, and x_{3}. Thus, in either case, we can construct a new narrower search interval that is guaranteed to contain the function's minimum. Probe point selection From the diagram above, it is seen that the new search interval will be either between x1 and x4 with a length of a+c , or between x_{2} and x_{3} with a length of b . The golden section search requires that these intervals be equal. If they are not, a run of "bad luck" could lead to the wider interval being used many times, thus slowing down the rate of convergence. To ensure that b = a+c, the algorithm should choose x_{4} = x_{1} − x_{2} + x_{3}. However there still remains the question of where x2 should be placed in relation to x_{1} and x_{3}. The golden section search chooses the spacing between these points in such a way that these points have the same proportion of spacing as the subsequent triple x_{1},x_{2},x_{4} or x_{2},x_{4},x_{3}. By maintaining the same proportion of spacing throughout the algorithm, we avoid a situation in which x_{2} is very close to x1 or x_{3}, and guarantee that the interval width shrinks by the same constant proportion in each step. Mathematically, to ensure that the spacing after evaluating f(x_{4}) is proportional to the spacing prior to that evaluation, if f(x_{4}) is f_{4a} and our new triplet of points is x_{1}, x_{2}, and x_{4} then we want:
However, if f(x_{4}) is f_{4b} and our new triplet of points is x_{2}, x_{4}, and x_{3} then we want:
Eliminating c from these two simultaneous equations yields:
or
where φ is the golden ratio:
The appearance of the golden ratio in the proportional spacing of the evaluation points is how this search algorithm gets its name. Termination condition In addition to a routine for reducing the size of the bracketing of the solution, a complete algorithm must have a termination condition. The one provided in the book Numerical Recipes in C is based on testing the gaps among x0, x1, x2 and x3, terminating when within the relative accuracy bounds:
where τ is a tolerance parameter of the algorithm and x is the absolute value of x. The check is relative to the size of x2 and x3 because the fraction (nonexponent) part of a floating point number is of fixed precision. Fibonacci search A very similar algorithm can also be used to find the extremum (minimum or maximum) of a sequence of values that has a single local minimum or local maximum. In order to approximate the probe positions of golden section search while probing only integer sequence indices, the variant of the algorithm for this case typically maintains a bracketing of the solution in which the length of the bracketed interval is a Fibonacci number. For this reason, the sequence variant of golden section search is often called Fibonacci search. References * Avriel, Mordecai & Wilde, Douglass J. (1966), "Optimality proof for the symmetric Fibonacci search technique", Fibonacci Quarterly 4: 265–269, MR0208812 * Kiefer, J. (1953), "Sequential minimax search for a maximum", Proceedings of the American Mathematical Society 4: 502–506, MR0055639, doi:10.2307/2032161 * Press, W. H.; Teukolsky, S. A. & Vetterling, W. T. et al. (1999), Numerical Recipes in C, The Art of Scientific Computing (second ed.), Cambridge University Press, Cambridge, ISBN 0521431085 Retrieved from "http://en.wikipedia.org/"

