Golden

viewed 3537 times and licensed 122 times

Calculates the minimum of a one-dimensional real function using the golden section search method.

Controller: CodeCogs

Contents

Interface
Golden
Page Comments

Interface

C++

Golden

doublegolden(	double	(`f`)(double)[function pointer]*
	double	`a`
	double	`b`
	double	`c`
	double	`eps` `= 1E-10`	)

Given a user-defined function f and a bracketing triplet of abscissas $\inline (a, b, c)$ (such that a < b < c and $\inline f(a) > f(b) < f(c)$ ) 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 $\inline (a, b)$ or $\inline (b, c)$ . If $\inline f(x) < f(b)$ then x replaces the midpoint b, and b becomes an end point. If $\inline f(x) > f(b)$ 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 $\inline \phi = \left( 3 - \sqrt(5) \right) / 2$ (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, 3, 2) \qquad (5, 3, 2) \qquad (5, 3, 4) \qquad (5, 3, 6)$

(2)

MISSING IMAGE!

1/golden-378.png cannot be found in /users/1/golden-378.png. Please contact the submission author.

Example 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;
}

Output:

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

f	the user-defined function
a	the first point of the bracketing triplet
b	the second point of the triplet
c	the third point of the triplet
eps	Default value = 1E-10

Returns

The approximated abscissa coresponding to the minimum of the function.

Authors

Lucian Bentea (August 2005)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.