1. Basic idea

2. Probe point selection

3. Termination condition

4. Algorithm
    Iterative algorithm  Recursive algorithm 

5. Fibonacci search

6. See also

7. References

The golden-section search is a technique for finding the extremum (minimum or maximum) of a strictly unimodal function by successively narrowing the range of values inside which the extremum is known to exist. The technique derives its name from the fact that the algorithm maintains the function values for triples of points whose distances form a golden ratio. The algorithm is the limit of Fibonacci search (also described below) for a large number of 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

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 .

Algorithm

Iterative algorithm

• Let [a, b] be interval of current bracket. f(a), f(b) would already have been computed earlier. .
• Let c = b - (b – a)/φ , d = a + (b – a)/φ. If f(c), f(d) not available, compute them.
• If f(c) < f(d) (this is to find min, to find max, just reverse it) then move the data: (b, f(b)) ← (d, f(d)), (d, f(d)) ← (c, f(c)) and update c = b - (b - a)/φ and f(c);
• otherwise, move the data: (a, f(a)) ← (c, f(c)), (c, f(c)) ← (d, f(d)) and update d = a + (b − a)/φ and f(d).
• At the end of the iteration, [a, c, d, b] bracket the minimum point.

gr = (math.sqrt(5) + 1) / 2

def gss(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)    >>> x    2.000009644875678

    '''    c = b - (b - a) / gr    d = a + (b - a) / gr     while abs(c - d) > tol:        if f(c) < f(d):            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

   reuses function evaluations, saving 1/2 of the evaluations per   iteration, and returns a bounding interval.'''

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 [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 - 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 xrange(n-1):        if yc < yd:            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 {

  public static final double invphi = (Math.sqrt(5.0)-1)/2.0;  public static final double invphi2 = (3-Math.sqrt(5.0))/2.0;

  public interface Function {    double of(double x);  }

  // returns subinterval of [a,b] containing minimum of f                                                                                                     public static double[] gss(Function f, double a, double b, double tol) {    return gss(f,a,b,tol,b-a,true,0,0,true,0,0);  }  private static double[] gss(Function f, double a, double b, double tol,                              double h, boolean noC, double c, double fc,                              boolean noD, double d, double fd) {    if (Math.abs(h) <= tol) {      return new double[] { 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) {      return gss(f,a,d,tol,h*invphi,true,0,0,false,c,fc);    } else {      return gss(f,c,b,tol,h*invphi,false,d,fd,true,0,0);    }  }

  public static void main(String[] args) {    Function f = (x)->Math.pow(x-2,2);    double a = 1;    double b = 5;    double tol = 1e-5;    double [] ans = gss(f,a,b,tol);    System.out.println("[" + ans[0] + "," + ans[1] + "]");    // [1.9999959837979107,2.0000050911830893]                                                                                                                }

}

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 [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 == None: h=b-a    if h <= tol: return (a,b)    if c == None: c = a + invphi2*h    if d == None: d = a + invphi*h    if fc == None: fc = f(c)    if fd == None: fd = f(d)    if fc < fd:        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.

Fibonacci search was first devised by Kiefer (1953) as a minimax search for the maximum (minimum) of a unimodal function in an interval.

;;

See also

• Ternary search
• Brent's method
• Binary search

References

• {{citation

• {{citation

• {{Citation | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | publication-place=New York | isbn=978-0-521-88068-8 | chapter=Section 10.2. Golden Section Search in One Dimension | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=492}}

• Roc del Comptador
• Roc d'Enfer
• Roc des Saints Peres
• Roc des Saints Pères
• ROC (disambiguation)
• Roc d'Orzival
• Rocefin
• Rocehmed
• Rocephine
• Roces (Gijon)
• Roces, Gijón
• Rocester Abbey
• Rocester F. C.
• Rocester FC
• Rocester F C
• Rocester railway station
• Rocevnica
• ROCF
• ROC Finance Minister
• Roch
• Rocha dos Bordões
• Rochaeva
• Rocha FC
• Rocha F C
• Rocha F. C.