golden_section.h

Go to the documentation of this file.

#ifndef TOON_GOLDEN_SECTION_H
#define TOON_GOLDEN_SECTION_H
#include <TooN/TooN.h>
#include <limits>
#include <cmath>
#include <cstdlib>
#include <iomanip>

namespace TooN
{
        using std::numeric_limits;

        template<class Functor, class Precision> Vector<2, Precision> golden_section_search(Precision a, Precision b, Precision c, Precision fb, const Functor& func, int maxiterations, Precision tol = sqrt(numeric_limits<Precision>::epsilon()))
        {
                using std::abs;
                //The golden ratio:
                const Precision g = (3.0 - sqrt(5))/2;

                Precision x1, x2, fx1, fx2;

                //Perform an initial iteration, to get a 4 point
                //bracketing. This is rather more convenient than
                //a 3 point bracketing.
                if(abs(b-a) > abs(c-b))
                {
                        x1 = b - g*(b-a);
                        x2 = b;

                        fx1 = func(x1);
                        fx2 = fb;
                }
                else
                {
                        x2 = b + g * (c-b);
                        x1 = b;

                        fx1 = fb;
                        fx2 = func(x2);
                }

                //We now have an ordered list of points a x1 x2 c

                //Termination condition from NR in C
                int itnum = 1; //We've already done one iteration.
                while(abs(c-a) > tol * (abs(x2)+abs(x1)) && itnum < maxiterations)
                {
                        if(fx1 > fx2)
                        {
                                // Bracketing does:
                                // a     x1     x2     c
                                //        a     x1  x2 c
                                a = x1;
                                x1 = x2;
                                x2 = x1 + g * (c-x1);
                                
                                fx1 = fx2;
                                fx2 = func(x2);
                        }
                        else
                        {
                                // Bracketing does:
                                // a     x1     x2     c
                                // a  x1 x2     c
                                c = x2;
                                x2 = x1;
                                x1= x2 - g * (x2 - a);
                                
                                fx2 = fx1;
                                fx1 = func(x1);
                        }
                }

                
                if(fx1 < fx2)
                        return makeVector<Precision>(x1, fx1);
                else
                        return makeVector<Precision>(x2, fx2);
        }

        template<class Functor, class Precision> Vector<2, Precision> golden_section_search(Precision a, Precision b, Precision c, const Functor& func, int maxiterations, Precision tol = sqrt(numeric_limits<Precision>::epsilon()))
        {
                return golden_section_search(a, b, c, func(b), func, maxiterations, tol);
        }

}
#endif

---

libtoon
Author(s): Florian Weisshardt
autogenerated on Fri Jan 11 10:09:37 2013