Bracket

Given two initial points, this algorithm finds another point such that a bracketing triple is formed.

Controller: CodeCogs

Contents

Interface
Bracket
Page Comments

Interface

C++

Bracket

voidbracket(	double	(`f`)(double)[function pointer]*
	double&	`a`
	double&	`b`
	double&	`c`	)

Given a user-defined function f and two distinct initial points a and b, this algorithm searches in the downhill direction (defined by the function as evaluated at the initial points) and returns a new point c such that the triplet $\inline (a, b, c)$ brackets a minimum of the function. Explicitly, bracketing the minimum means finding three values a, b and c such that

$a < b < c \qquad \wedge \squad f(a) > f(b) < f(c)$

(2)

In order to achieve this, an initial guess is made using the golden section

$c = b + \phi \cdot (b - a) \qquad \phi \approx 1.618034$

(3)

and then parabolic extrapolation is used as described below. Consider

$r = (b - a) \left( f(b) - f(c) \right) \qquad q = (b - c) \left( f(b) - f(a) \right)$

(4)

then the new extrapolated abscissa will be

$u = b - \mathrm{sign}(q - r) \frac {q(b - c) - r(b - a)} {2 |\mathrm{max}(q - r, \epsilon)|}$

(5)

If this does not create a new minimum point $\inline \left( u, f(u) \right)$ , default golden section interval magnification is used

$u = c + \phi \cdot (c - b)$

(6)

The function takes four parameters.

Example 1

#include <codecogs/maths/optimization/bracket.h>
 
#include <iostream>
#include <iomanip>
#include <cmath>
 
// user-defined function
double f(double x) {
    return x * sin(x);
}
 
int main() 
{
    double a = 5, b = 4, c;
    Maths::Optimization::bracket(f, a, b, c);
 
    std::cout << "The bracketing triple is: " << std::endl << std::endl;
    std::cout << "    a = 4" << std::endl << "    b = 5 " << std::endl;
    std::cout << "    c = " << std::setprecision(10) << c << std::endl;
    std::cout << std::endl;
 
    std::cout << "The corresponding function values are: " << std::endl;
    std::cout << std::endl;
    std::cout << " f(a) = " << f(4) << std::endl << " f(b) = " << f(5);
    std::cout << std::endl;
    std::cout << " f(c) = " << f(c) << std::endl << std::endl;
    return 0;
}

Output

The bracketing triple is:
 
    a = 4
    b = 5
    c = 6.618034
 
The corresponding function values are:
 
 f(a) = -3.027209981
 f(b) = -4.794621373
 f(c) = 2.174859828

Parameters

f	the user-defined function
a	the left endpoint of the initial interval
b	the right endpoint of the initial interval
c	the third point that will complete the bracketing triple

Returns

The new values of a, b and c creating a bracketing triple.

Authors

Lucian Bentea (August 2005)

Source Code

Source code is available when you buy a Commercial licence.

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