Class mmin_simp2 (o2scl)

O2scl : Class List

template<class func_t = multi_funct, class vec_t = boost::numeric::ublas::vector<double>>
class mmin_simp2 : public o2scl::mmin_base<multi_funct, multi_funct, boost::numeric::ublas::vector<double>>

Multidimensional minimization by the Simplex method (v2) (GSL)

This class mins a function using Nelder and Mead’s Simplex algorithm. A simplex in a N-dimensional space is defined as a set of N+1 points which describe an N-dimensional volume surrounding the minimum. The algorithm proceeds by shifting the simplex points until the simplex is sufficiently small and thus the minimum is known with sufficient accuracy.

This class has a high-level interface using mmin(), mmin_twovec() or mmin_simplex() which automatically performs the memory allocation and minimization, or a GSL-like interface using allocate(), free(), interate() and set() or set_simplex().

The simplex can be completely specified by the user (see mmin_simplex() and set_simplex()). Alternatively, the simplex is automatically specified given initial guess \( x_j \) and a step size vector \( s_k \) for \( 0\leq k<n_s \). The simplex \( p_{ij} \) with \( 0\leq i\leq n \) and \( 0\leq j<n \) is chosen with \( p_{0j} = x_j \) and

\[\begin{split}\begin{eqnarray*} p_{i+1,j} &=& x_j\quad\mathrm{for}\quad i\neq j \\ p_{i+1,j} &=& x_j+s_{j~\mathrm{mod}~n_s}\quad\mathrm{for}\quad i=j \end{eqnarray*}\end{split}\]

for \( 0<i<n \). The step size vector \( s \) is set by the set_step() member function. The prsence of \( \mathrm{mod} \) in the recipe above just indicates that elements of the step size vector are automatically re-used if there are less step sizes than dimensions in the minimization problem.

See an example for the usage of this class in Multidimensional minimizer example.

Default template arguments

• param_t - no default

• func_t - multi_funct

• vec_t - boost::numeric::ublas::vector < double >

Based on [Nelder65].

A variable count originally defined in the GSL simplex state is not present here, because it was unused.

Idea for Future:

Double check that the updates in gsl-1.13 are included here, and also add support for the nmsimplex2rand algorithm in GSL.

Note

It is important that the initial simplex contains sufficient variation in every direction of the parameter space over which one is minimizing. For example, if all three points in a simplex for minimizing over a two-dimensional space contain nearly the same value for the second parameter, then the minimizer may only minimize the function with respect to the first parameter.

Note

The algorithm used to estimate the simplex size does not work well any of the parameters in the minimization problem has a scale which is not close to 1.

Public Types

typedef boost::numeric::ublas::vector<double> ubvector

Public Functions

inline mmin_simp2()

inline virtual ~mmin_simp2()

template<class vec2_t>
inline int set_step(size_t nv, vec2_t &step)

Set the step sizes for each independent variable.

inline virtual int mmin(size_t nn, vec_t &xx, double &fmin, func_t &ufunc)

Calculate the minimum min of func w.r.t the array x of size nvar.

inline virtual int mmin_twovec(size_t nn, vec_t &xx, vec_t &xx2, double &fmin, func_t &ufunc)

Calculate the minimum min of func w.r.t the array x of size nvar, using xx and xx2 to specify the simplex.

template<class mat_t>
inline int mmin_simplex(size_t nn, mat_t &sx, double &fmin, func_t &ufunc)

Calculate the minimum min of func w.r.t the array x of size nvar, given an initial simplex.

The matrix sx should have the dim+1 initial points arranged in rows so that there are dim+1 rows and each row has dim columns.

inline virtual int allocate(size_t n)

Allocate the memory.

inline virtual int set(func_t &ufunc, size_t n, vec_t &ax, vec_t &step_size)

Set the function and initial guess.

template<class mat_t>
inline int set_simplex(func_t &ufunc, mat_t &sx)

Set the function and initial simplex.

The matrix sx should have the dim+1 initial points arranged in rows so that there are dim+1 rows and each row has dim columns.

inline virtual int iterate()

Perform an iteration.

inline virtual int print_iter(size_t nv, vec_t &xx, vec_t *simp, double y, int iter, double value, double limit, std::string comment)

Print out iteration information.

Depending on the value of the variable verbose, this prints out the iteration information. If verbose=0, then no information is printed, while if verbose>1, then after each iteration, the present values of x and y are output to std::cout along with the iteration number. If verbose>=2 then each iteration waits for a character.

inline virtual const char *type()

Return string denoting type(“mmin_simp2”)

Public Members

double size

Size of current simplex computed by iterate()

vec_t x

Present minimum vector computed by iterate()

double fval

Function value at minimum computed by iterate()

int print_simplex

Print simplex information in print_iter() (default 0)

If this is 1 and verbose is greater than 0, then print_iter() will print the function values at all the simplex points. If this is 2 and verbose is greater than 0, then print_iter() will print the simplex coordinates in addition to the function values.

Protected Functions

inline int compute_center()

Compute the center of the simplex.

inline double compute_size()

Compute the size of the simplex.

Calculates simplex size as average sum of length of vectors from simplex center to corner points:

\( (1/n) \sum || y - y_{\mathrm{center}} || \)

inline virtual int try_corner_move(const double coeff, size_t corner, vec_t &xc, func_t &f, size_t nvar, double &newval)

Move a corner of a simplex.

Moves a simplex corner scaled by coeff (negative value represents mirroring by the middle point of the “other” corner points) and gives new corner in xc and function value at xc in newval.

inline virtual int update_point(size_t i, vec_t &xx, double val)

Update point i in the simplex with values xx.

inline virtual int contract_by_best(size_t best, func_t &f, size_t nvar)

Contract the simplex towards the best point.

Function contracts the simplex in respect to best valued corner. All corners besides the best corner are moved.

Protected Attributes

vec_t *x1

An array of n+1 vectors containing the simplex.

ubvector y1

The n+1 function values at the simplex points.

vec_t ws1

Workspace vector 1.

vec_t ws2

Workspace vector 2.

vec_t ws3

Workspace vector 3.

vec_t center

Center of simplex.

vec_t delta

Desc.

vec_t xmc

Distance of vector from center.

double S2

Squared simplex size.

size_t dim

Number of variables to be mind over.

func_t *func

Function.

bool set_called

True if set() has been called.

ubvector step_vec

Vector of step sizes.

bool avoid_nonzero

If true, try to automatically avoid regions where the function returns a non-zero value (default false)

Note

This option doesn’t work yet, so I’ve made the variable protected to prevent the casual user from changing it.

Private Functions

mmin_simp2(const mmin_simp2<func_t, vec_t>&)

mmin_simp2<func_t, vec_t> &operator=(const mmin_simp2<func_t, vec_t>&)