The golden-section search is a technique for finding an
extremum (minimum or maximum) of a function inside a specified interval. For a strictly
unimodal function with an extremum inside the interval, it will find that extremum, while for an interval containing multiple extrema (possibly including the interval boundaries), it will converge to one of them. If the only extremum on the interval is on a boundary of the interval, it will converge to that boundary point. The method operates by successively narrowing the range of values on the specified interval, which makes it relatively slow, but very robust. The technique derives its name from the fact that the algorithm maintains the function values for four points whose three interval widths are in the ratio ''φ:1:φ'' where ''φ'' is the
golden ratio. These ratios are maintained for each iteration and are maximally efficient. Excepting boundary points, when searching for a minimum, the central point is always less than or equal to the outer points, assuring that a minimum is contained between the outer points. The converse is true when searching for a maximum. The algorithm is the limit of
Fibonacci search
In computer science, the Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Note that the running time analysis is this a ...
(also described below) for many function evaluations. Fibonacci search and golden-section search were discovered by
Kiefer (1953) (see also Avriel and Wilde (1966)).
Basic idea
The discussion here is posed in terms of searching for a minimum (searching for a maximum is similar) of a
unimodal function. Unlike finding a zero, where two function evaluations with opposite sign are sufficient to bracket a root, when searching for a minimum, three values are necessary. The golden-section search is an efficient way to progressively reduce the interval locating the minimum. The key is to observe that regardless of how many points have been evaluated, the minimum lies within the interval defined by the two points adjacent to the point with the least value so far evaluated.
The diagram above illustrates a single step in the technique for finding a minimum. The functional values of
are on the vertical axis, and the horizontal axis is the ''x'' parameter. The value of
has already been evaluated at the three points:
,
, and
. Since
is smaller than either
or
, it is clear that a minimum lies inside the interval from
to
.
The next step in the minimization process is to "probe" the function by evaluating it at a new value of ''x'', namely
. It is most efficient to choose
somewhere inside the largest interval, i.e. between
and
. From the diagram, it is clear that if the function yields
, then a minimum lies between
and
, and the new triplet of points will be
,
, and
. However, if the function yields the value
, then a minimum lies between
and
, and the new triplet of points will be
,
, and
. 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
and
with a length of ''a'' + ''c'', or between
and
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
.
However, there still remains the question of where
should be placed in relation to
and
. 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
or
. By maintaining the same proportion of spacing throughout the algorithm, we avoid a situation in which
is very close to
or
and guarantee that the interval width shrinks by the same constant proportion in each step.
Mathematically, to ensure that the spacing after evaluating
is proportional to the spacing prior to that evaluation, if
is
and our new triplet of points is
,
, and
, then we want
:
However, if
is
and our new triplet of points is
,
, and
, 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
Any number of termination conditions may be applied, depending upon the application. The interval ''ΔX = X
4 − X
1'' is a measure of the absolute error in the estimation of the minimum ''X'' and may be used to terminate the algorithm. The value of ''ΔX'' is reduced by a factor of ''r = φ − 1'' for each iteration, so the number of iterations to reach an absolute error of ''ΔX'' is about ''ln(ΔX/ΔX
o) / ln(r)'' where ''ΔX
o'' is the initial value of ''ΔX''.
Because smooth functions are flat (their first derivative is close to zero) near a minimum, attention must be paid not to expect too great an accuracy in locating the minimum. The termination condition provided in the book
Numerical Recipes in C is based on testing the gaps among
,
,
and
, terminating when within the relative accuracy bounds
:
where
is a tolerance parameter of the algorithm, and
is the
absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), an ...
of
. The check is based on the bracket size relative to its central value, because that relative error in
is approximately proportional to the squared absolute error in
in typical cases. For that same reason, the Numerical Recipes text recommends that
, where
is the required absolute precision of
.
Algorithm
Note! The examples here describe an algorithm that is for finding the ''minimum'' of a function. For maximum, the comparison operators need to be reversed.
Iterative algorithm
# Specify the function to be minimized, f(x), the interval to be searched as , and their functional values F
1 and F
4.
# Calculate an interior point and its functional value F
2. The two interval lengths are in the ratio ''c : r'' or ''r : c'' where ''r = φ − 1;'' and ''c = 1 − r'', with ''φ'' being the golden ratio.
# Using the triplet, determine if convergence criteria are fulfilled. If they are, estimate the X at the minimum from that triplet and return.
# From the triplet, calculate the other interior point and its functional value. The three intervals will be in the ratio ''c:cr:c''.
# The three points for the next iteration will be the one where F is a minimum, and the two points closest to it in X.
# Go to step 3
"""Python program for golden section search. This implementation
does not reuse function evaluations and assumes the minimum is c
or d (not on the edges at a or b)"""
import math
gr = (math.sqrt(5) + 1) / 2
def gss(f, a, b, tol=1e-5):
"""Golden-section search
to find the minimum of f on ,b f: a strictly unimodal function on ,b
Example:
>>> f = lambda x: (x-2)**2
>>> x = gss(f, 1, 5)
>>> print("%.15f" % x)
2.000009644875678
"""
c = b - (b - a) / gr
d = a + (b - a) / gr
while abs(b - a) > tol:
if f(c) < f(d): # f(c) > f(d) to find the maximum
b = d
else:
a = c
# We recompute both c and d here to avoid loss of precision which may lead to incorrect results or infinite loop
c = b - (b - a) / gr
d = a + (b - a) / gr
return (b + a) / 2
"""Python program for golden section search. This implementation
reuses function evaluations, saving 1/2 of the evaluations per
iteration, and returns a bounding interval."""
import math
invphi = (math.sqrt(5) - 1) / 2 # 1 / phi
invphi2 = (3 - math.sqrt(5)) / 2 # 1 / phi^2
def gss(f, a, b, tol=1e-5):
"""Golden-section search.
Given a function f with a single local minimum in
the interval ,b gss returns a subset interval
,dthat contains the minimum with d-c <= tol.
Example:
>>> f = lambda x: (x-2)**2
>>> a = 1
>>> b = 5
>>> tol = 1e-5
>>> (c,d) = gss(f, a, b, tol)
>>> print(c, d)
1.9999959837979107 2.0000050911830893
"""
(a, b) = (min(a, b), max(a, b))
h = b - a
if h <= tol:
return (a, b)
# Required steps to achieve tolerance
n = int(math.ceil(math.log(tol / h) / math.log(invphi)))
c = a + invphi2 * h
d = a + invphi * h
yc = f(c)
yd = f(d)
for k in range(n-1):
if yc < yd: # yc > yd to find the maximum
b = d
d = c
yd = yc
h = invphi * h
c = a + invphi2 * h
yc = f(c)
else:
a = c
c = d
yc = yd
h = invphi * h
d = a + invphi * h
yd = f(d)
if yc < yd:
return (a, d)
else:
return (c, b)
Recursive algorithm
public class GoldenSectionSearch
import math
invphi = (math.sqrt(5) - 1) / 2 # 1 / phi
invphi2 = (3 - math.sqrt(5)) / 2 # 1 / phi^2
def gssrec(f, a, b, tol=1e-5, h=None, c=None, d=None, fc=None, fd=None):
""" Golden-section search, recursive.
Given a function f with a single local minimum in
the interval ,b gss returns a subset interval
,dthat contains the minimum with d-c <= tol.
Example:
>>> f = lambda x: (x-2)**2
>>> a = 1
>>> b = 5
>>> tol = 1e-5
>>> (c,d) = gssrec(f, a, b, tol)
>>> print (c, d)
1.9999959837979107 2.0000050911830893
"""
(a, b) = (min(a, b), max(a, b))
if h is None: h = b - a
if h <= tol: return (a, b)
if c is None: c = a + invphi2 * h
if d is None: d = a + invphi * h
if fc is None: fc = f(c)
if fd is None: fd = f(d)
if fc < fd: # fc > fd to find the maximum
return gssrec(f, a, d, tol, h * invphi, c=None, fc=None, d=c, fd=fc)
else:
return gssrec(f, c, b, tol, h * invphi, c=d, fc=fd, d=None, fd=None)
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
In computer science, the Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Note that the running time analysis is this a ...
''.
Fibonacci search was first devised by
Kiefer (1953) as a
minimax
Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...
search for the maximum (minimum) of a unimodal function in an interval.
;;;
See also
*
Ternary search
*
Brent's method
In numerical analysis, Brent's method is a hybrid root-finding algorithm combining the bisection method, the secant method and inverse quadratic interpolation. It has the reliability of bisection but it can be as quick as some of the less-reliable ...
*
Binary search
References
*
*
*
{{DEFAULTSORT:Golden Section Search
Golden ratio
Fibonacci numbers
Optimization algorithms and methods
Articles with example Java code
Articles with example Python (programming language) code
Search algorithms