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 (also described below) for many function evaluations. Fibonacci search and golden-section search were discovered by Kiefer (1953) (see also Avriel and Wilde (1966)).
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
f(x)
f(x)
x1
x2
x3
f2
f1
f3
x1
x3
The next step in the minimization process is to "probe" the function by evaluating it at a new value of x, namely
x4
x4
x2
x3
f4a>f(x2)
x1
x4
x1
x2
x4
f4b<f(x2)
x2
x3
x2
x4
x3
From the diagram above, it is seen that the new search interval will be either between
x1
x4
x2
x3
x4=x1+(x3-x2)
However, there still remains the question of where
x2
x1
x3
x1,x2,x4
x2,x4,x3
x2
x1
x3
Mathematically, to ensure that the spacing after evaluating
f(x4)
f(x4)
f4a
x1
x2
x4
| c | |
| a |
=
| a | |
| b |
.
However, if
f(x4)
f4b
x2
x4
x3
| c | |
| b-c |
=
| a | |
| b |
.
Eliminating c from these two simultaneous equations yields
| \left( | b |
| a |
\right)2-
| b | |
| a |
=1,
or
| b | |
| a |
=\varphi,
where φ is the golden ratio:
\varphi=
| 1+\sqrt{5 | |
The appearance of the golden ratio in the proportional spacing of the evaluation points is how this search algorithm gets its name.
Any number of termination conditions may be applied, depending upon the application. The interval ΔX = X4 − X1 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/ΔX0) / ln(r), where ΔX0 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
x1
x2
x3
x4
|x3-x1|<\tau(|x2|+|x4|),
where
\tau
|x|
x
x
f(x)
\tau=\sqrt{\varepsilon}
\varepsilon
f(x)
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.
import math
invphi = (math.sqrt(5) - 1) / 2 # 1 / phi
def gss(f, a, b, tolerance=1e-5): """ Golden-section search to find the minimum of f on [a,b]
* f: a strictly unimodal function on [a,b]
Example: >>> def f(x): return (x - 2) ** 2 >>> x = gss(f, 1, 5) >>> print(f"") 2.00000
""" while abs(b - a) > tolerance: c = b - (b - a) * invphi d = a + (b - a) * invphi if f(c) < f(d): b = d else: # f(c) > f(d) to find the maximum a = c
return (b + a) / 2
import math
invphi = (math.sqrt(5) - 1) / 2 # 1 / phiinvphi2 = (3 - math.sqrt(5)) / 2 # 1 / phi^2
def gss(f, a, b, tolerance=1e-5): """ Golden-section search.
Given a function f with a single local minimum in the interval [a,b], gss returns a subset interval [c,d] that contains the minimum with d-c <= tolerance.
Example: >>> def f(x): return (x - 2) ** 2 >>> print(*gss(f, a=1, b=5, tolerance=1e-5)) 1.9999959837979107 2.0000050911830893 """ a, b = min(a, b), max(a, b) h = b - a if h <= tolerance: return (a, b)
# Required steps to achieve tolerance n = int(math.ceil(math.log(tolerance / h) / math.log(invphi)))
c, d = a + invphi2 * h, a + invphi * h yc, yd = f(c), f(d)
for _ in range(n - 1): h *= invphi if yc < yd: b, d = d, c yd = yc c = a + invphi2 * h yc = f(c) else: # yc > yd to find the maximum a, c = c, d yc = yd d = a + invphi * h yd = f(d)
return (a, d) if yc < yd else (c, b)
invphi = (math.sqrt(5) - 1) / 2 # 1 / phiinvphi2 = (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 [a, b], gss returns a subset interval [c, d] that 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)
See main article: Fibonacci search technique.
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.
Fibonacci search was first devised by Kiefer (1953) as a minimax search for the maximum (minimum) of a unimodal function in an interval.
The Bisection method is a similar algorithm for finding a zero of a function. Note that, for bracketing a zero, only two points are needed, rather than three. The interval ratio decreases by 2 in each step, rather than by the golden ratio.