CodeCogs

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

You're viewing an older version of this page (#86). View the current version.

Interface

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

using namespace Maths::Optimization;

void bracket (double (*f)(double), 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 $(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)$

(1)

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$

(2)

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)$

(3)

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)|}$

(4)

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

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

(5)

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

the user-defined function

the left endpoint of the initial interval

the right endpoint of the initial interval

the third point that will complete the bracketing triple

Returns

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

Bracket

Interface

Example 1

Output

Parameters

Returns