neldermead.h File Reference

Derivative-free simplex minimization (Nelder and Mead, 1965), with optional box bounds imposed by a change of variables. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for neldermead.h:

Go to the source code of this file.

Classes
struct	line::NelderMeadOptions< T >
	Tuning of the simplex iteration. More...
struct	line::NelderMeadResult< T >
	Outcome of a simplex minimization. More...
struct	line::Bound< T >
	Box constraint on one variable. More...

Namespaces
namespace	line

Functions
template<class T>
NelderMeadOptions< T >	line::nelder_mead_defaults ()
	fminsearch's coefficients and initial simplex, with tighter tolerances.
template<class T>
Bound< T >	line::bound_free ()
	Unbounded variable.
template<class T>
Bound< T >	line::bound_lower (const T &lo)
	lo <= x.
template<class T>
Bound< T >	line::bound_upper (const T &hi)
	x <= hi.
template<class T>
Bound< T >	line::bound_box (const T &lo, const T &hi)
	lo <= x <= hi.
template<class T, class F>
NelderMeadResult< T >	line::nelder_mead (F f, const std::vector< T > &x0, const NelderMeadOptions< T > &opt)
	Unconstrained simplex minimization.
template<class T, class F>
NelderMeadResult< T >	line::nelder_mead (F f, const std::vector< T > &x0)
	nelder_mead with the default tuning.
template<class T, class F>
NelderMeadResult< T >	line::nelder_mead_box (F f, const std::vector< T > &x0, const std::vector< Bound< T > > &bounds, const NelderMeadOptions< T > &opt)
	Box-constrained simplex minimization by the transformation described in the header comment.
template<class T, class F>
NelderMeadResult< T >	line::nelder_mead_box (F f, const std::vector< T > &x0, const std::vector< Bound< T > > &bounds)
	nelder_mead_box with the default tuning.

Detailed Description

Derivative-free simplex minimization (Nelder and Mead, 1965), with optional box bounds imposed by a change of variables.

This is the fallback for objectives that are not a sum of squares, that are only piecewise smooth (the max(.) in an augmented Lagrangian's inequality term, the max/min clamping in the AMAP(2) autocorrelation bounds), or whose derivative is not worth n extra evaluations. Where the objective is a sum of squares, prefer line/util/levmar.h: it converges in far fewer evaluations and reports the residual vector.

ACCEPTANCE CONTRACT. As for levmar.h: this replaces MATLAB's fminsearch / fminsearchbnd / patternsearch / PSwarm, and the iterates do not and cannot agree with theirs. Correctness is judged on the returned objective value and on the specification the caller states, never on iterate-by-iterate agreement with a reference implementation.

DETERMINISM. The initial simplex is constructed from x0 alone: vertex 0 is x0 and vertex j+1 perturbs coordinate j by step_rel * |x0_j|, or by step_abs when x0_j is zero. This is the fminsearch construction and involves no random numbers, so a given (objective, x0, options) triple always produces the same answer, on any platform. Ties in the vertex ordering are broken by vertex index, which keeps the sort stable and the run reproducible.

BOX BOUNDS. Bounds are enforced by an unconstrained reparameterization of each variable, so the simplex itself is unconstrained and every evaluated point is strictly feasible: lower and upper: x = lo + (hi - lo) (sin(u) + 1)/2 lower only: x = lo + u^2 upper only: x = hi - u^2 The transformation is not a bijection (it folds), which is harmless for minimization but means the returned x, not the internal u, is the answer. A variable whose bounds coincide is held fixed at that value and removed from the search. Note the well-known cost of the technique: the objective seen by the simplex is flat at an active bound (dx/du = 0 there), so convergence onto a bound is slower than in the interior; the returned point still satisfies the bound exactly.

Gated on transcendental arithmetic: the method stops on tolerances, and the two-sided bound transformation needs sin/asin.

Definition in file neldermead.h.