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/Δ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 , , 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 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. When the base is clear from the context or is irrelevant it is sometimes written log x.
In probability theory and 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, the Haar wavelet is a sequence of rescaled "square-shaped" functions which together form a wavelet family or basis. Wavelet analysis is similar to Fourier analysis in that it allows a target function over an interval to be represented in terms of an orthonormal basis. The Haar sequence is now recognised as the first known wavelet basis and is extensively used as a teaching example.
The calculus of variations is a field of mathematical analysis that uses variations, which are small changes in functions and functionals, to find maxima and minima of functionals: mappings from a set of functions to the real numbers. Functionals are often expressed as definite integrals involving functions and their derivatives. Functions that maximize or minimize functionals may be found using the Euler–Lagrange equation of the calculus of variations.
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, 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
Branch and bound is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
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.
In mathematics, the regula falsi, method of false position, or false position method is a very old method for solving an equation with one unknown; this method, in modified form, is still in use. In simple terms, the method is the trial and error technique of using test ("false") values for the variable and then adjusting the test value according to the outcome. This is sometimes also referred to as "guess and check". Versions of the method predate the advent of algebra and the use of equations.
In mathematics, the Gauss–Kuzmin–Wirsing operator is the transfer operator of the Gauss map that takes a positive number to the fractional part of its reciprocal. It is named after Carl Gauss, Rodion Kuzmin, and Eduard Wirsing. It occurs in the study of continued fractions; it is also related to the Riemann zeta function.
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 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).
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.