NAG CL Interface
e04cbc (uncon_simplex)
1
Purpose
e04cbc minimizes a general function
$F\left(\mathbf{x}\right)$ of
$n$ independent variables
$\mathbf{x}={\left({x}_{1},{x}_{2},\dots ,{x}_{n}\right)}^{\mathrm{T}}$ by the Nelder and Mead simplex method (see
Nelder and Mead (1965)). Derivatives of the function need not be supplied.
2
Specification
void 
e04cbc (Integer n,
double x[],
double *f,
double tolf,
double tolx,
void 
(*funct)(Integer n,
const double xc[],
double *fc,
Nag_Comm *comm),


Integer maxcal,
Nag_Comm *comm,
NagError *fail) 

The function may be called by the names: e04cbc, nag_opt_uncon_simplex or nag_opt_simplex_easy.
3
Description
e04cbc 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
e04cbc. 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,
e04cbc 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 functionvalue test should be sufficient on its own if
$F$ is continuous.
4
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
5
Arguments

1:
$\mathbf{n}$ – Integer
Input

On entry: $n$, the number of variables.
Constraint:
${\mathbf{n}}\ge 1$.

2:
$\mathbf{x}\left[{\mathbf{n}}\right]$ – double
Input/Output

On entry: a guess at the position of the minimum. Note that the problem should be scaled so that the values of the ${\mathbf{x}}\left[i1\right]$ are of order unity.
On exit: the value of
$\mathbf{x}$ corresponding to the function value in
f.

3:
$\mathbf{f}$ – double *
Output

On exit: the lowest function value found.

4:
$\mathbf{tolf}$ – double
Input

On entry: the error tolerable in the function values, in the following sense. If
${f}_{\mathit{i}}$, for
$\mathit{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
e04cbc should terminate if
You may specify
${\mathbf{tolf}}=0$ if you wish to use only the termination criterion
(2) on the spatial values: see the description of
tolx.
Constraint:
${\mathbf{tolf}}$ must be greater than or equal to the
machine precision (see
Chapter X02), or if
tolf equals zero, then
tolx must be greater than or equal to the
machine precision.

5:
$\mathbf{tolx}$ – double
Input

On entry: the error tolerable in the spatial values, in the following sense. If
$LV$ denotes the ‘linearized’ volume of the current simplex, and if
${LV}_{\mathrm{init}}$ denotes the ‘linearized’ volume of the initial simplex, then you can request that
e04cbc should terminate if
You may specify
${\mathbf{tolx}}=0$ if you wish to use only the termination criterion
(1) on function values: see the description of
tolf.
Constraint:
${\mathbf{tolx}}$ must be greater than or equal to the
machine precision (see
Chapter X02), or if
tolx equals zero, then
tolf must be greater than or equal to the
machine precision.

6:
$\mathbf{funct}$ – function, supplied by the user
External Function

funct must evaluate the function
$F$ at a specified point. It should be tested separately before being used in conjunction with
e04cbc.
The specification of
funct is:
void 
funct (Integer n,
const double xc[],
double *fc,
Nag_Comm *comm)



1:
$\mathbf{n}$ – Integer
Input

On entry: $n$, the number of variables.

2:
$\mathbf{xc}\left[{\mathbf{n}}\right]$ – const double
Input

On entry: the point at which the function value is required.

3:
$\mathbf{fc}$ – double *
Output

On exit: the value of the function $F$ at the current point $\mathbf{x}$.

4:
$\mathbf{comm}$ – Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to
funct.
 user – double *
 iuser – Integer *
 p – Pointer
The type Pointer will be
void *. Before calling
e04cbc you may allocate memory and initialize these pointers with various quantities for use by
funct when called from
e04cbc (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).
Note: funct should not return floatingpoint NaN (Not a Number) or infinity values, since these are not handled by
e04cbc. If your code inadvertently
does return any NaNs or infinities,
e04cbc is likely to produce unexpected results.

7:
$\mathbf{monit}$ – function, supplied by the user
External Function

monit may be used to monitor the optimization process. It is invoked once every iteration.
If no monitoring is required,
monit may be specified as NULLFN.
The specification of
monit is:

1:
$\mathbf{fmin}$ – double
Input

On entry: the smallest function value in the current simplex.

2:
$\mathbf{fmax}$ – double
Input

On entry: the largest function value in the current simplex.

3:
$\mathbf{sim}\left[\left({\mathbf{n}}+1\right)\times {\mathbf{n}}\right]$ – const double
Input

On entry: the $n+1$ position vectors of the current simplex, where ${\mathbf{sim}}\left[\left(j1\right)\times \left(n+1\right)+i1\right]$ is the $j$th coordinate of the $i$th position vector.

4:
$\mathbf{n}$ – Integer
Input

On entry: $n$, the number of variables.

5:
$\mathbf{ncall}$ – Integer
Input

On entry: the number of times that
funct has been called so far.

6:
$\mathbf{serror}$ – double
Input

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

7:
$\mathbf{vratio}$ – double
Input

On entry: the current value of the linearized volume ratio used in termination test
(2).

8:
$\mathbf{comm}$ – Nag_Comm *
Pointer to structure of type Nag_Comm; the following members are relevant to
monit.
 user – double *
 iuser – Integer *
 p – Pointer
The type Pointer will be
void *. Before calling
e04cbc you may allocate memory and initialize these pointers with various quantities for use by
monit when called from
e04cbc (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).

8:
$\mathbf{maxcal}$ – Integer
Input

On entry: the maximum number of function evaluations to be allowed.
Constraint:
${\mathbf{maxcal}}\ge 1$.

9:
$\mathbf{comm}$ – Nag_Comm *

The NAG communication argument (see
Section 3.1.1 in the Introduction to the NAG Library CL Interface).

10:
$\mathbf{fail}$ – NagError *
Input/Output

The NAG error argument (see
Section 7 in the Introduction to the NAG Library CL Interface).
6
Error Indicators and Warnings
 NE_ALLOC_FAIL

Dynamic memory allocation failed.
See
Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
 NE_BAD_PARAM

On entry, argument $\u2329\mathit{\text{value}}\u232a$ had an illegal value.
 NE_INT

On entry, ${\mathbf{maxcal}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{maxcal}}\ge 1$.
On entry, ${\mathbf{n}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{n}}\ge 1$.
 NE_INTERNAL_ERROR

An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact
NAG for assistance.
See
Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
 NE_NO_LICENCE

Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library CL Interface for further information.
 NE_REAL

On entry, ${\mathbf{tolf}}=0.0$ and ${\mathbf{tolx}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{tolf}}=0.0$ then ${\mathbf{tolx}}$ is greater than or equal to the machine precision.
On entry, ${\mathbf{tolx}}=0.0$ and ${\mathbf{tolf}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{tolx}}=0.0$ then ${\mathbf{tolf}}$ is greater than or equal to the machine precision.
 NE_REAL_2

On entry, ${\mathbf{tolf}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{tolx}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: if ${\mathbf{tolf}}\ne 0.0$ and ${\mathbf{tolx}}\ne 0.0$ then both should be greater than or equal to the machine precision.
 NW_TOO_MANY_FEVALS

maxcal function evaluations have been completed without any other termination test passing. Check the coding of
funct before increasing the value of
maxcal.
7
Accuracy
On a successful exit the accuracy will be as defined by
tolf or
tolx, depending on which criterion was satisfied first.
8
Parallelism and Performance
e04cbc makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the
X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the
Users' Note for your implementation for any additional implementationspecific information.
Local workspace arrays of fixed lengths (depending on
n) are allocated internally by
e04cbc. The total size of these arrays amounts to
${{\mathbf{n}}}^{2}+6{\mathbf{n}}+2$ double elements.
The time taken by e04cbc depends on the number of variables, the behaviour of the function and the distance of the starting point from the minimum. Each iteration consists of $1$ or $2$ function evaluations unless the size of the simplex is reduced, in which case $n+1$ function evaluations are required.
10
Example
This example finds a minimum of the function
This example uses the initial point
$\left(1,1\right)$ (see
Section 10.3), and we expect to reach the minimum at
$\left(0.5,1\right)$.
10.1
Program Text
10.2
Program Data
None.
10.3
Program Results