Interactive Educational Modules in
Scientific Computing

Golden Section Search

This module demonstrates golden section search for minimizing a nonlinear function in one dimension. Given an objective function that is unimodal on a given initial interval, function values are computed at two points whose relative locations in the interval are determined by the golden ratio, τ ≈ 0.618. Comparison of the resulting values allows a portion of the interval to be discarded, since it cannot contain the minimum. The process is repeated on the new, shorter interval until the minimum has been isolated as accurately as desired.

The user selects a problem either by choosing a preset example or typing in a desired objective function f(x) and initial interval [a, b]. The successive steps of golden section search are then carried out sequentially by repeatedly clicking on NEXT or on the currently highlighted step. The current points x within [a, b] and corresponding function values f(x) are indicated by bullets on the plot and are also shown numerically in the table below. At each iteration, the function values at the two interior points are compared, the appropriate portion of the interval is discarded, and the process is then repeated. Eventually, the minimum of the function, which always remains within the interval provided the function f is unimodal, is located as accurately as desired.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 6.4.1, especially Algorithm 6.1 and Example 6.8.

Developers: Jeffrey Naisbitt and Michael Heath