jade::basic_simplex< TValue > Class Template Reference

A template for a class that implements the Nelder-Mead Simplex Method, which attempts to minimize an objective function in a many-dimensional space by continually refining a simplex. More...

#include <jade.simplex.hpp>

Collaboration diagram for jade::basic_simplex< TValue >:

Data Structures
struct	execute_args
	Arguments to the execute method. More...
struct	exit_condition
	An indication of what caused the execute to temrinate. More...
struct	log_args
	Arguments passed to the logging function. More...
struct	operation
	An operation performed during an iteration. More...
struct	options
	A data structure used to initialize the Nelder-Mead algorithm. More...
struct	stats
	Statistics about the behavior of the algorithm. More...

Public Types
typedef TValue	value_type
	The value type. More...
typedef std::vector< value_type >	container_type
	The container type. More...
typedef exit_condition::type	exit_condition_type
	The exit condition type. More...
typedef operation::type	operation_type
	The operation type. More...

Public Member Functions
template<typename TObjfunc >
	basic_simplex (const TObjfunc objfunc, const size_t n)
	Initializes a new instance of the class based on the specified required values. More...
template<typename TObjfunc >
	basic_simplex (const TObjfunc objfunc, const options &opts)
	Initializes a new instance of the class based on the specified options. More...
template<typename TObjfunc >
exit_condition_type	execute (const TObjfunc objfunc, const execute_args &exe_args)
	Calls the iterate method until an exit condition is reached. More...
value_type	get_delta () const
value_type	get_flux () const
value_type	get_length_squared () const
value_type	get_length () const
const options &	get_options () const
const stats &	get_stats () const
const value_type &	get_objval () const
const value_type &	get_objval (const size_t index) const
const container_type &	get_vertex () const
const container_type &	get_vertex (const size_t index) const
template<typename TObjfunc >
operation_type	iterate (const TObjfunc objfunc)
	Performs one iteration of the Nelder-Mead algorithm. In an iteration over two-dimensional space, a point p_min is reflected to point p_r, expanded to point p_e, or contracted to point p_c. If these test points do not improve the overall score of the simplex, then it shrinks around the point p_max with the highest score. More...

Detailed Description

template<typename TValue>
class jade::basic_simplex< TValue >

A template for a class that implements the Nelder-Mead Simplex Method, which attempts to minimize an objective function in a many-dimensional space by continually refining a simplex.

Definition at line 20 of file jade.simplex.hpp.

Member Typedef Documentation

container_type

template<typename TValue >

typedef std::vector<value_type> jade::basic_simplex< TValue >::container_type

The container type.

Definition at line 27 of file jade.simplex.hpp.

exit_condition_type

template<typename TValue >

typedef exit_condition::type jade::basic_simplex< TValue >::exit_condition_type

The exit condition type.

Definition at line 68 of file jade.simplex.hpp.

operation_type

template<typename TValue >

typedef operation::type jade::basic_simplex< TValue >::operation_type

The operation type.

Definition at line 109 of file jade.simplex.hpp.

value_type

template<typename TValue >

typedef TValue jade::basic_simplex< TValue >::value_type

The value type.

Definition at line 24 of file jade.simplex.hpp.

Constructor & Destructor Documentation

basic_simplex() [1/2]

template<typename TValue >

template<typename TObjfunc >

jade::basic_simplex< TValue >::basic_simplex ( const TObjfunc  objfunc, const size_t  n  )

inline

Initializes a new instance of the class based on the specified required values.

Parameters

objfunc	The objective function.
n	The number of dimensions.

Definition at line 498 of file jade.simplex.hpp.

            : basic_simplex(objfunc, options(n))
        {
        }

basic_simplex() [2/2]

template<typename TValue >

template<typename TObjfunc >

jade::basic_simplex< TValue >::basic_simplex ( const TObjfunc  objfunc, const options &  opts  )

inline

Initializes a new instance of the class based on the specified options.

Parameters

objfunc	The objective function.
opts	The options.

Definition at line 510 of file jade.simplex.hpp.

            : _n     (opts.vertex.size())
            , _opts  (opts)
            , _stats ()
            , _x     ()
            , _xbar  ()
            , _xr    ()
            , _xc    ()
            , _xcc   ()
            , _xe    ()
        {
            assert(_n > 0);
 
            assert(opts.rho > 0);
            assert(opts.chi >= 1 && opts.chi >= opts.rho);
            assert(opts.gamma > 0 && opts.gamma < 1);
            assert(opts.sigma > 0 && opts.sigma < 1);
            assert(opts.unit > 0);
            assert(opts.vertex.empty() || opts.vertex.size() == _n);
 
            //
            // Add N+1 vertices with N of them offset from the initial vertex by
            // one unit in a dimension corresponding to their index.
            //
            for (size_t i = 0; i <= _n; i++)
                _x.emplace_back(new vertex(opts, i));
 
            //
            // Initially evaluate the objective function for the simplex.
            //
            for (const auto & xi : _x)
                xi->objval = _evaluate(objfunc, xi->params);
 
            //
            // Initially sort the vertices.
            //
            std::sort(_x.begin(), _x.end(), _is_less);
 
            //
            // Declare vertices here to avoid memory allocations while
            // iterating.
            //
            _xbar.resize(_n);
            _xr.resize(_n);
            _xc.resize(_n);
            _xcc.resize(_n);
            _xe.resize(_n);
        }

Member Function Documentation

execute()

template<typename TValue >

template<typename TObjfunc >

exit_condition_type jade::basic_simplex< TValue >::execute ( const TObjfunc  objfunc, const execute_args &  exe_args  )

inline

Calls the iterate method until an exit condition is reached.

Returns

The exit condition.

Parameters

objfunc	The objective function.
exe_args	The execution arguments.

Definition at line 567 of file jade.simplex.hpp.

        {
            typedef std::chrono::high_resolution_clock clock_type;
            typedef std::chrono::duration<double>      duration_type;
 
            const auto t0 = clock_type::now();
            const auto get_seconds = [t0]() -> double
            {
                return duration_type(clock_type::now() - t0).count();
            };
 
            auto iteration = size_t(0);
            auto flux0     = get_flux();
 
            for (;;)
            {
                if (exe_args.is_max_iterations_assigned())
                    if (iteration >= exe_args.max_iterations)
                        return exit_condition_type::iteration;
 
                if (exe_args.is_max_seconds_assigned())
                    if (get_seconds() >= exe_args.max_seconds)
                        return exit_condition_type::timeout;
 
                if (exe_args.is_min_delta_assigned())
                    if (get_delta() <= exe_args.min_delta)
                        return exit_condition_type::delta;
 
                if (exe_args.is_min_length_assigned())
                    if (get_length() <= exe_args.min_length)
                        return exit_condition_type::length;
 
                iterate(objfunc);
                iteration++;
 
                if (exe_args.is_logfunc_assigned())
                    exe_args.logfunc(log_args(
                            this,
                            get_seconds(),
                            iteration,
                            exe_args.user));
 
                auto flux = get_flux();
 
                if (exe_args.is_min_epsilon_assigned())
                    if (std::fabs(flux0 - flux) <= exe_args.min_epsilon)
                        return exit_condition::epsilon;
                flux0 = flux;
            }
        }

Here is the call graph for this function:

Here is the caller graph for this function:

get_delta()

template<typename TValue >

value_type jade::basic_simplex< TValue >::get_delta ( ) const

inline

Returns

The difference between the best and worst values returned from the objective function for all vertices of the simplex.

Definition at line 624 of file jade.simplex.hpp.

        {
            return _x.back()->objval - _x.front()->objval;
        }

Here is the caller graph for this function:

get_flux()

template<typename TValue >

value_type jade::basic_simplex< TValue >::get_flux ( ) const

inline

Returns

The difference between the value compared to the epsilon in the execute method. This value is determined by dividing the sum of the non-infinite values by the number of non-infinite values squared.

Definition at line 635 of file jade.simplex.hpp.

        {
            static const auto inf = std::numeric_limits<value_type>::max();
 
            auto sum   = value_type(0);
            auto count = 0;
 
            for (const auto & x : _x)
            {
                if (x->objval < inf)
                {
                    sum += x->objval;
                    count++;
                }
            }
 
            return count == 0 ? value_type(0) : sum / count / count;
        }

Here is the caller graph for this function:

get_length()

template<typename TValue >

value_type jade::basic_simplex< TValue >::get_length ( ) const

inline

Returns

The maximum length of the vector connecting the vertex with the minimum value returned from the objective function and any other vertex of the simplex.

Definition at line 690 of file jade.simplex.hpp.

        {
            return std::sqrt(get_length_squared());
        }

Here is the call graph for this function:

Here is the caller graph for this function:

get_length_squared()

template<typename TValue >

value_type jade::basic_simplex< TValue >::get_length_squared ( ) const

inline

Returns

The square of the maximum length of the vector connecting the vertex with the minimum value returned from the objective function and any other vertex of the simplex.

Definition at line 659 of file jade.simplex.hpp.

        {
            container_type vec;
            vec.resize(_n);
 
            value_type max = value_type(0);
 
            const auto & p0 = _x[0]->params;
 
            for (size_t i = 1; i <= _n; i++)
            {
                const auto & p = _x[i]->params;
 
                _subtract(vec, p, p0);
                _multiply(vec, vec, vec);
 
                max = std::max(max, std::accumulate(
                    vec.begin(),
                    vec.end(),
                    value_type(0),
                    std::plus<value_type>()));
            }
 
            return max;
        }

Here is the caller graph for this function:

get_objval() [1/2]

template<typename TValue >

const value_type& jade::basic_simplex< TValue >::get_objval ( ) const

inline

Returns

The minimum objective value.

Definition at line 714 of file jade.simplex.hpp.

        {
            return _x[0]->objval;
        }

Here is the caller graph for this function:

get_objval() [2/2]

template<typename TValue >

const value_type& jade::basic_simplex< TValue >::get_objval ( const size_t  index ) const

inline

Returns

The minimum objective value.

Parameters

index

The vertex index.

Definition at line 722 of file jade.simplex.hpp.

        {
            assert(index <= _n);
            return _x[index]->objval;
        }

get_options()

template<typename TValue >

const options& jade::basic_simplex< TValue >::get_options ( ) const

inline

Returns

The options used for the class.

Definition at line 698 of file jade.simplex.hpp.

        {
            return _opts;
        }

get_stats()

template<typename TValue >

const stats& jade::basic_simplex< TValue >::get_stats ( ) const

inline

Returns

The statistics about the execution.

Definition at line 706 of file jade.simplex.hpp.

        {
            return _stats;
        }

get_vertex() [1/2]

template<typename TValue >

const container_type& jade::basic_simplex< TValue >::get_vertex ( ) const

inline

Returns

The vertex with the minimum value returned from the objective function.

Definition at line 734 of file jade.simplex.hpp.

        {
            return _x[0]->params;
        }

Here is the caller graph for this function:

get_vertex() [2/2]

template<typename TValue >

const container_type& jade::basic_simplex< TValue >::get_vertex ( const size_t  index ) const

inline

Returns

The vertex with the minimum value returned from the objective function.

Parameters

index

The vertex index.

Definition at line 743 of file jade.simplex.hpp.

        {
            assert(index <= _n);
            return _x[index]->params;
        }

iterate()

template<typename TValue >

template<typename TObjfunc >

operation_type jade::basic_simplex< TValue >::iterate ( const TObjfunc  objfunc )

inline

Performs one iteration of the Nelder-Mead algorithm. In an iteration over two-dimensional space, a point p_min is reflected to point p_r, expanded to point p_e, or contracted to point p_c. If these test points do not improve the overall score of the simplex, then it shrinks around the point p_max with the highest score.

Returns

The operation performed by the iteration.

Parameters

objfunc

The objective function.

Definition at line 761 of file jade.simplex.hpp.

        {
            const auto & x0 = _x[0];
 
            _stats.iterations++;
 
            //
            // REFLECTION
            //
            _copy(_xbar, x0->params);
            for (size_t i = 1; i < _n; i++)
                _add(_xbar, _xbar, _x[i]->params);
            _scale(_xbar, value_type(1.0) / value_type(_n));
 
            _subtract(_xr, _xbar, _x[_n]->params);
            _scale(_xr, _opts.rho);
            _add(_xr, _xr, _xbar);
 
            const auto fr = _evaluate(objfunc, _xr);
            if (x0->objval <= fr && fr < _x[_n - 1]->objval)
                return _accept(_xr, fr, _stats.reflections,
                    operation::reflection);
 
            //
            // EXPANSION
            //
            if (fr < x0->objval)
            {
                _subtract(_xe, _xr, _xbar);
                _scale(_xe, _opts.chi);
                _add(_xe, _xe, _xbar);
 
                const auto fe = _evaluate(objfunc, _xe);
                return fe < fr
                    ? _accept(_xe, fe, _stats.expansions,
                        operation::expansion)
                    : _accept(_xr, fr, _stats.reflections,
                        operation::reflection);
            }
 
            //
            // CONTRACTION
            //
            if (fr >= _x[_n - 1]->objval)
            {
                if (fr < _x[_n]->objval)
                {
                    _subtract(_xc, _xr, _xbar);
                    _scale(_xc, _opts.gamma);
                    _add(_xc, _xc, _xbar);
 
                    const auto fc = _evaluate(objfunc, _xc);
                    if (fc <= fr)
                        return _accept(_xc, fc, _stats.contractions_out,
                            operation::contraction_out);
                }
                else
                {
                    _subtract(_xcc, _xbar, _x[_n]->params);
                    _scale(_xcc, _opts.gamma);
                    _subtract(_xcc, _xbar, _xcc);
 
                    const auto fcc = _evaluate(objfunc, _xcc);
                    if (fcc < _x[_n]->objval)
                        return _accept(_xcc, fcc, _stats.contractions_in,
                            operation::contraction_in);
                }
            }
 
            //
            // SHRINKAGE
            //
            for (size_t i = 1; i <= _n; i++)
            {
                auto & xi = _x[i];
                _subtract(xi->params, xi->params, x0->params);
                _scale(xi->params, _opts.sigma);
                _add(xi->params, xi->params, x0->params);
                xi->objval = _evaluate(objfunc, xi->params);
            }
 
            std::sort(_x.begin(), _x.end(), _is_less);
            _stats.shrinkages++;
            return operation::shrinkage;
        }

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• jade.simplex.hpp