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 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.
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.
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/ΔXo) / ln(r) where ΔXo 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 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 .
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.
"""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)"""importmathgr=(math.sqrt(5)+1)/2defgss(f,a,b,tol=1e-5):"""Golden-section search to find the minimum of f on [a,b] f: a strictly unimodal function on [a,b] Example: >>> f = lambda x: (x - 2) ** 2 >>> x = gss(f, 1, 5) >>> print("%.15f" % x) 2.000009644875678 """whileabs(b-a)>tol:c=b-(b-a)/grd=a+(b-a)/griff(c)<f(d):# f(c) > f(d) to find the maximumb=delse:a=creturn(b+a)/2
// a and c define range to search// func(x) returns value of function at x to be minimizedfunctiongoldenSection(a,c,func){functionsplit(x1,x2){returnx1+0.6180339887498949*(x2-x1);}varb=split(a,c);varbv=func(b);while(a!=c){varx=split(a,b);varxv=func(x);if(xv<bv){bv=xv;c=b;b=x;}else{a=c;c=x;}}returnb;}functiontest(x){return-Math.sin(x);}console.log(goldenSection(0,3,test));// prints PI/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."""importmathinvphi=(math.sqrt(5)-1)/2# 1 / phiinvphi2=(3-math.sqrt(5))/2# 1 / phi^2defgss(f,a,b,tol=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 <= 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-aifh<=tol:return(a,b)# Required steps to achieve tolerancen=int(math.ceil(math.log(tol/h)/math.log(invphi)))c=a+invphi2*hd=a+invphi*hyc=f(c)yd=f(d)forkinrange(n-1):ifyc<yd:# yc > yd to find the maximumb=dd=cyd=ych=invphi*hc=a+invphi2*hyc=f(c)else:a=cc=dyc=ydh=invphi*hd=a+invphi*hyd=f(d)ifyc<yd:return(a,d)else:return(c,b)
publicclassGoldenSectionSearch{publicstaticfinaldoubleinvphi=(Math.sqrt(5.0)-1)/2.0;publicstaticfinaldoubleinvphi2=(3-Math.sqrt(5.0))/2.0;publicinterfaceFunction{doubleof(doublex);}// Returns subinterval of [a,b] containing minimum of fpublicstaticdouble[]gss(Functionf,doublea,doubleb,doubletol){returngss(f,a,b,tol,b-a,true,0,0,true,0,0);}privatestaticdouble[]gss(Functionf,doublea,doubleb,doubletol,doubleh,booleannoC,doublec,doublefc,booleannoD,doubled,doublefd){if(Math.abs(h)<=tol){returnnewdouble[]{a,b};}if(noC){c=a+invphi2*h;fc=f.of(c);}if(noD){d=a+invphi*h;fd=f.of(d);}if(fc<fd){// fc > fd to find the maximumreturngss(f,a,d,tol,h*invphi,true,0,0,false,c,fc);}else{returngss(f,c,b,tol,h*invphi,false,d,fd,true,0,0);}}publicstaticvoidmain(String[]args){Functionf=(x)->Math.pow(x-2,2);doublea=1;doubleb=5;doubletol=1e-5;double[]ans=gss(f,a,b,tol);System.out.println("["+ans[0]+","+ans[1]+"]");// [1.9999959837979107,2.0000050911830893]}}
importmathinvphi=(math.sqrt(5)-1)/2# 1 / phiinvphi2=(3-math.sqrt(5))/2# 1 / phi^2defgssrec(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))ifhisNone:h=b-aifh<=tol:return(a,b)ifcisNone:c=a+invphi2*hifdisNone:d=a+invphi*hiffcisNone:fc=f(c)iffdisNone:fd=f(d)iffc<fd:# fc > fd to find the maximumreturngssrec(f,a,d,tol,h*invphi,c=None,fc=None,d=c,fd=fc)else:returngssrec(f,c,b,tol,h*invphi,c=d,fc=fd,d=None,fd=None)
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.
In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn . The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the sequence begins
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities and with , is in a golden ratio to if
In mathematics, the logarithm is the inverse function to exponentiation. That means that the logarithm of a number x to the base b is the exponent to which b must be raised to produce x. For example, since 1000 = 103, the logarithm base 10 of 1000 is 3, or log10 (1000) = 3. The logarithm of x to base b is denoted as logb (x), or without parentheses, logb x, or even without the explicit base, log x, when no confusion is possible, or when the base does not matter such as in big O notation.
In mathematics, the mean value theorem states, roughly, that for a given planar arc between two endpoints, there is at least one point at which the tangent to the arc is parallel to the secant through its endpoints. It is one of the most important results in real analysis. This theorem is used to prove statements about a function on an interval starting from local hypotheses about derivatives at points of the interval.
In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is
In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before the 20th century, the distinction was unclear between a polynomial and its associated polynomial function; so "quadratic polynomial" and "quadratic function" were almost synonymous. This is still the case in many elementary courses, where both terms are often abbreviated as "quadratic".
In calculus, integration by substitution, also known as u-substitution, reverse chain rule or change of variables, is a method for evaluating integrals and antiderivatives. It is the counterpart to the chain rule for differentiation, and can loosely be thought of as using the chain rule "backwards."
In calculus, Rolle's theorem or Rolle's lemma essentially states that any real-valued differentiable function that attains equal values at two distinct points must have at least one stationary point somewhere between them—that is, a point where the first derivative is zero. The theorem is named after Michel Rolle.
In mathematics and physical science, spherical harmonics are special functions defined on the surface of a sphere. They are often employed in solving partial differential equations in many scientific fields. A list of the spherical harmonics is available in Table of spherical harmonics.
In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction a/b is b/a. For the multiplicative inverse of a real number, divide 1 by the number. For example, the reciprocal of 5 is one fifth (1/5 or 0.2), and the reciprocal of 0.25 is 1 divided by 0.25, or 4. The reciprocal function, the function f(x) that maps x to 1/x, is one of the simplest examples of a function which is its own inverse (an involution).
In number theory, the Mertens function is defined for all positive integers n as
In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x1, ..., xN has a low discrepancy.
In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function f. The secant method can be thought of as a finite-difference approximation of Newton's method. However, the secant method predates Newton's method by over 3000 years.
In mathematics, the bisection method is a root-finding method that applies to any continuous function for which one knows two values with opposite signs. The method consists of repeatedly bisecting the interval defined by these values and then selecting the subinterval in which the function changes sign, and therefore must contain a root. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods. The method is also called the interval halving method, the binary search method, or the dichotomy method.
The Gauss–Newton algorithm is used to solve non-linear least squares problems, which is equivalent to minimizing a sum of squared function values. It is an extension of Newton's method for finding a minimum of a non-linear function. Since a sum of squares must be nonnegative, the algorithm can be viewed as using Newton's method to iteratively approximate zeroes of the components of the sum, and thus minimizing the sum. In this sense, the algorithm is also an effective method for solving overdetermined systems of equations. It has the advantage that second derivatives, which can be challenging to compute, are not required.
In optimization, line search is a basic iterative approach to find a local minimum of an objective function . It first finds a descent direction along which the objective function will be reduced, and then computes a step size that determines how far should move along that direction. The descent direction can be computed by various methods, such as gradient descent or quasi-Newton method. The step size can be determined either exactly or inexactly.
In probability theory and statistics, the continuous uniform distributions or rectangular distributions are a family of symmetric probability distributions. Such a distribution describes an experiment where there is an arbitrary outcome that lies between certain bounds. The bounds are defined by the parameters, and which are the minimum and maximum values. The interval can either be closed or open. Therefore, the distribution is often abbreviated where stands for uniform distribution. The difference between the bounds defines the interval length; all intervals of the same length on the distribution's support are equally probable. It is the maximum entropy probability distribution for a random variable under no constraint other than that it is contained in the distribution's support.
In mathematics (specifically multivariable calculus), a multiple integral is a definite integral of a function of several real variables, for instance, f(x, y) or f(x, y, z). Physical (natural philosophy) interpretation: S any surface, V any volume, etc.. Incl. variable to time, position, etc.
In mathematics, the ATS theorem is the theorem on the approximation of a trigonometric sum by a shorter one. The application of the ATS theorem in certain problems of mathematical and theoretical physics can be very helpful.
In numerical analysis, the ITP method, short for Interpolate Truncate and Project, is the first root-finding algorithm that achieves the superlinear convergence of the secant method while retaining the optimal worst-case performance of the bisection method. It is also the first method with guaranteed average performance strictly better than the bisection method under any continuous distribution. In practice it performs better than traditional interpolation and hybrid based strategies, since it not only converges super-linearly over well behaved functions but also guarantees fast performance under ill-behaved functions where interpolations fail.