Mathematics Source Library
C & ASM

 Home Optimization Home Nonlinear Optimization Home One-Dimensional Optimization Home Rosenbrock's Success/Failure Routines Exhaustive Grid Search Three Point Equal Interval Search Golden Section Search Fibonacci Search Parabolic Extrapolation for Bracketing an Extremum Parabolic Interpolation Minimize Down the Line / Maximize Up the Line

## Golden Section Search

Given an interval of uncertainty [a,b] which contains an extremum for a unimodal function f:[a,b]→R the Golden Section search method is performed by initially chosing two internal points of the interval so that the distance of the right-most internal point to the left-most endpoint equals to the distance of the right-most endpoint to the left-most internal point. Both the distances are equal to a fixed constant, λ, times the length of the interval. In order that λ be fixed for each iteration and that successive iterations require the addition of only one new internal point and consequently only one new function evaluation it is easy to show that λ ² + λ - 1 = 0 or λ = (√5 - 1) / 2. The name Golden Section comes from Euclid.

The algorithm proceeds as follows: Given a function f(x) for which a local minimum is sought, an initial interval [a,b], which brackets the local minimum and a tolerance, ε, calculate the internal points x1 = b - λ * (b - a) and x2 = a + λ (b - a). Iterate unless the stopping criterion is satisfied. Otherwise if f(x1) < f(x2) then the interval (x2,b] can be deleted, in which case set the new value for b = x2, set x2 = x1, and calculate the new internal point x1 = a + (1 - λ) * (b - a). Otherwise the interval [a, x1) can be eliminated, in which case set the new value for a = x1, set x1 = x2, and set new value for x2 = b - (1 - λ) * (b - a).

The algorithm for finding a local maximum is analogous to the method described above.

The function f should be unimodal on the interval [a,b].

### Function List

• void Min_Search_Golden_Section( double (*f)(double), double* a, double *fa, double* b, double* fb, double tolerance )

This routine attempts to shorten the interval [*a,*b] which brackets a local minimum of the user-supplied function f(x) by partitioning the interval into three subintervals. The endpoints of the intervals are determined by Euclid's golden section. The function is then evaluated at the interior points. Successive iterations require only one new interior point and consequently only one new function evaluation. The two subintervals with the common endpoint at which the function is a minimum is retained. The process is terminated if the magnitude of the midpoint of the interval of uncertainty is less than or equal to one when the length of the interval of uncertainty is less than the tolerance and if the magnitude of the midpoint is greater than one when the when the relative length of the interval of uncertainty to the magnitude of its midpoint is less than the tolerance. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

On input the parameters *a and *b, with *a < *b, should bracket a local minimum and the parameters, *fa and *fb, should be the values of f(x) evaluated at *a and *b respectively. The function f should be unimodal on the interval [*a, *b].

• void Max_Search_Golden_Section( double (*f)(double), double* a, double *fa, double* b, double* fb, double tolerance )

This routine attempts to shorten the interval [*a,*b] which brackets a local maximum of the user-supplied function f(x) by partitioning the interval into three subintervals. The endpoints of the intervals are determined by Euclid's golden section. The function is then evaluated at the interior points. Successive iterations require only one new interior point and consequently only one new function evaluation. The two subintervals with the common endpoint at which the function is a maximum is retained. The process is terminated if the magnitude of the midpoint of the interval of uncertainty is less than or equal to one when the length of the interval of uncertainty is less than the tolerance and if the magnitude of the midpoint is greater than one when the when the relative length of the interval of uncertainty to the magnitude of its midpoint is less than the tolerance. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

On input the parameters *a and *b, with *a < *b, should bracket a local maximum and the parameters, *fa and *fb, should be the values of f(x) evaluated at *a and *b respectively. The function f should be unimodal on the interval [*a, *b].

• void Min_Line_Search_Golden_Section( double (*f)(double*), double* base, double* direction, double* x, int n, double* a, double *fa, double* b, double* fb, double tolerance )

Given the user-supplied real-valued function f of an n-dimensional vector and the line segment base - λ direction where a ≤ λ ≤ b this routine attempts to shorten the interval of uncertainty [*a,*b] which brackets a local minimum of g(λ) = f(base - λ direction) by partitioning the interval into three subintervals. The endpoints of the intervals are determined by Euclid's golden section. The function is then evaluated at the interior points. Successive iterations require only one new interior point and consequently only one new function evaluation. The two subintervals with the common endpoint at which the function is a minimum is retained. The process is repeated until the length of the retained interval is less than or equal to tolerance. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

On input the parameters *a and *b, with *a < *b, should bracket a local minimum of g(λ) = f(base - λ direction) with a ≤ λ ≤ b and the parameters, *fa and *fb, should be the values of f(x) evaluated at base - *a direction and base - *b direction respectively. The function f should be unimodal on the line segment base - λ direction, *a ≤ λ ≤ *b.

• void Max_Line_Search_Golden_Section( double (*f)(double*), double* base, double* direction, double* x, int n, double* a, double *fa, double* b, double* fb, double tolerance )

Given the user-supplied real-valued function f of an n-dimensional vector and the line segment base + λ direction where a ≤ λ ≤ b this routine attempts to shorten the interval of uncertainty [*a,*b] which brackets a local maximum of g(λ) = f(base + λ direction) by partitioning the interval into three subintervals. The endpoints of the intervals are determined by Euclid's golden section. The function is then evaluated at the interior points. Successive iterations require only one new interior point and consequently only one new function evaluation. The two subintervals with the common endpoint at which the function is a maximum is retained. The process is repeated until the length of the retained interval is less than or equal to tolerance. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

On input the parameters *a and *b, with *a < *b, should bracket a local maximum of g(λ) = f(base + λ direction) with a ≤ λ ≤ b, *fa and *fb, should be the values of f(x) evaluated at base + *a direction and base + *b direction respectively. The function f should be unimodal on the line segment base + λ direction, *a ≤ λ ≤ *b.