naginterfaces.library.opt.uncon_​simplex

naginterfaces.library.opt.uncon_simplex(x, tolf, tolx, funct, maxcal, monit=None, data=None)

uncon_simplex minimizes a general function $F\left(x\right)$ of $n$ independent variables $x={(x_1,x_2,\dots ,x_n)}^T$ by the Nelder and Mead simplex method (see Nelder and Mead (1965)). Derivatives of the function need not be supplied.

For full information please refer to the NAG Library document for e04cb

https://support.nag.com/numeric/nl/nagdoc_30.2/flhtml/e04/e04cbf.html

Parameters

xfloat, array-like, shape $\left(n\right)$

A guess at the position of the minimum. Note that the problem should be scaled so that the values of the $x[i-1]$ are of order unity.

tolffloat

The error tolerable in the function values, in the following sense. If $f_{\text{i}}$, for $\text{i}=1,2,\dots ,n+1$, are the individual function values at the vertices of the current simplex, and if $f_m$ is the mean of these values, then you can request that uncon_simplex should terminate if

$$\sqrt{\frac{1}{n+1}\sum _{i=1}^{n+1}{(f_i-f_m)}^2}<tolf\text{.}$$

You may specify $tolf=0$ if you wish to use only the termination criterion (2) on the spatial values: see the description of $tolx$.

tolxfloat

The error tolerable in the spatial values, in the following sense. If $LV$ denotes the ‘linearized’ volume of the current simplex, and if ${LV}_{init}$ denotes the ‘linearized’ volume of the initial simplex, then you can request that uncon_simplex should terminate if

$$\frac{LV}{{LV}_{init}}<tolx\text{.}$$

You may specify $tolx=0$ if you wish to use only the termination criterion (1) on function values: see the description of $tolf$.

functcallable fc = funct(xc, data=None)

$funct$ must evaluate the function $F$ at a specified point.

It should be tested separately before being used in conjunction with uncon_simplex.

Parameters

xcfloat, ndarray, shape $\left(n\right)$

The point at which the function value is required.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

fcfloat

The value of the function $F$ at the current point $x$.

maxcalint

The maximum number of function evaluations to be allowed.

monitNone or callable monit(fmin, fmax, sim, ncall, serror, vratio, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

$monit$ may be used to monitor the optimization process.

It is invoked once every iteration.

If no monitoring is required, $monit$ may be None.

Parameters

fminfloat

The smallest function value in the current simplex.

fmaxfloat

The largest function value in the current simplex.

simfloat, ndarray, shape $(n+1,n)$

The $n+1$ position vectors of the current simplex.

ncallint

The number of times that $funct$ has been called so far.

serrorfloat

The current value of the standard deviation in function values used in termination test (1).

vratiofloat

The current value of the linearized volume ratio used in termination test (2).

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

dataarbitrary, optional

User-communication data for callback functions.

Returns

xfloat, ndarray, shape $\left(n\right)$

The value of $x$ corresponding to the function value in $f$.

ffloat

The lowest function value found.

Raises

NagValueError

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 1$.

(errno $1$)

On entry, $tolx=0.0$ and $tolf=⟨value⟩$.

Constraint: if $tolx=0.0$ then $tolf$ is greater than or equal to the machine precision.

(errno $1$)

On entry, $tolf=0.0$ and $tolx=⟨value⟩$.

Constraint: if $tolf=0.0$ then $tolx$ is greater than or equal to the machine precision.

(errno $1$)

On entry, $tolf=⟨value⟩$ and $tolx=⟨value⟩$.

Constraint: if $tolf\ne 0.0$ and $tolx\ne 0.0$ then both should be greater than or equal to the machine precision.

(errno $1$)

On entry, $maxcal=⟨value⟩$.

Constraint: $maxcal\ge 1$.

Warns

NagAlgorithmicMajorWarning

(errno $2$)

$maxcal$ function evaluations have been completed without any other termination test passing. Check the coding of $funct$ before increasing the value of $maxcal$.

Notes

uncon_simplex finds an approximation to a minimum of a function $F$ of $n$ variables. You must supply a function to calculate the value of $F$ for any set of values of the variables.

The method is iterative. A simplex of $n+1$ points is set up in the $n$-dimensional space of the variables (for example, in $2$ dimensions the simplex is a triangle) under the assumption that the problem has been scaled so that the values of the independent variables at the minimum are of order unity. The starting point you have provided is the first vertex of the simplex, the remaining $n$ vertices are generated by uncon_simplex. The vertex of the simplex with the largest function value is reflected in the centre of gravity of the remaining vertices and the function value at this new point is compared with the remaining function values. Depending on the outcome of this test the new point is accepted or rejected, a further expansion move may be made, or a contraction may be carried out. See Nelder and Mead (1965) and Parkinson and Hutchinson (1972) for more details. When no further progress can be made the sides of the simplex are reduced in length and the method is repeated.

The method can be slow, but computational bottlenecks have been reduced following Singer and Singer (2004). However, uncon_simplex is robust, and, therefore, very useful for functions that are subject to inaccuracies.

There are the following options for successful termination of the method: based only on the function values at the vertices of the current simplex (see (1)); based only on a volume ratio between the current simplex and the initial one (see (2)); or based on which one of the previous two tests passes first. The volume test may be useful if $F$ is discontinuous, while the function-value test should be sufficient on its own if $F$ is continuous.

References

Nelder, J A and Mead, R, 1965, A simplex method for function minimization, Comput. J. (7), 308–313

Parkinson, J M and Hutchinson, D, 1972, An investigation into the efficiency of variants of the simplex method, Numerical Methods for Nonlinear Optimization, (ed F A Lootsma), Academic Press

Singer, S and Singer, S, 2004, Efficient implementation of the Nelder–Mead search algorithm, Appl. Num. Anal. Comp. Math. (1(3)), 524–534

See also

naginterfaces.library.examples.opt.uncon_simplex_ex.main()