Golden

Given a user-defined function f and a bracketing triplet of abscissas (such that a < b < c and ) this routine performs a golden section search for the minimum, isolating it to a fractional precision ofabout eps . Finally it returns the abscissa corresponding to the minimum of the function.

This method involves evaluating the function at some point x in the larger of the two intervals or . If then x replaces the midpoint b, and b becomes an end point. If then b remains the midpoint with x replacing one of the end points. Either way the width of the bracketing interval will reduce and the position of the minima will be better defined. The procedure is then repeated until the width achieves a desired tolerance. It can be shown that if the new test point x is chosen to be a proportion (the golden section) along the larger sub-interval, measured from the mid-point b, then the width of the full interval will reduce at an optimal rate.

Below you will find a diagram describing the evolution of the golden section search algorithm. The triples at consecutive steps are

(1)

#include <codecogs/maths/optimization/golden.h>

#include <iostream>
#include <iomanip>
#include <cmath>

// user-defined function
double f(double x) {
    return x * sin(x) - 2 * cos(x);
}

int main() 
{
    double x = Maths::Optimization::golden(f, 5, 6, 7);
    std::cout << "Function minimum is Y = " << std::setprecision(13) << f(x);
    std::cout << std::endl;
    std::cout << "for X = " << x << std::endl;
    return 0;
}

Function minimum is Y = -4.794621373204
for X = 5.000000000244

References

• N.A.Thacker, T.F.Cootes, "Vision Through Optimization", http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/BMVA96Tut/node17.html

Parameters

Returns