NAG FL Interface
e04cbf (uncon_simplex)
1
Purpose
e04cbf minimizes a general function
of
independent variables
by the Nelder and Mead simplex method (see
Nelder and Mead (1965)). Derivatives of the function need not be supplied.
2
Specification
Fortran Interface
Subroutine e04cbf ( |
n, x, f, tolf, tolx, funct, monit, maxcal, iuser, ruser, ifail) |
Integer, Intent (In) |
:: |
n, maxcal |
Integer, Intent (Inout) |
:: |
iuser(*), ifail |
Real (Kind=nag_wp), Intent (In) |
:: |
tolf, tolx |
Real (Kind=nag_wp), Intent (Inout) |
:: |
x(n), ruser(*) |
Real (Kind=nag_wp), Intent (Out) |
:: |
f |
External |
:: |
funct, monit |
|
C Header Interface
#include <nag.h>
void |
e04cbf_ (const Integer *n, double x[], double *f, const double *tolf, const double *tolx, void (NAG_CALL *funct)(const Integer *n, const double xc[], double *fc, Integer iuser[], double ruser[]), void (NAG_CALL *monit)(const double *fmin, const double *fmax, const double sim[], const Integer *n, const Integer *ncall, const double *serror, const double *vratio, Integer iuser[], double ruser[]), const Integer *maxcal, Integer iuser[], double ruser[], Integer *ifail) |
|
C++ Header Interface
#include <nag.h> extern "C" {
void |
e04cbf_ (const Integer &n, double x[], double &f, const double &tolf, const double &tolx, void (NAG_CALL *funct)(const Integer &n, const double xc[], double &fc, Integer iuser[], double ruser[]), void (NAG_CALL *monit)(const double &fmin, const double &fmax, const double sim[], const Integer &n, const Integer &ncall, const double &serror, const double &vratio, Integer iuser[], double ruser[]), const Integer &maxcal, Integer iuser[], double ruser[], Integer &ifail) |
}
|
The routine may be called by the names e04cbf or nagf_opt_uncon_simplex.
3
Description
e04cbf finds an approximation to a minimum of a function of variables. You must supply a subroutine to calculate the value of for any set of values of the variables.
The method is iterative. A simplex of
points is set up in the
-dimensional space of the variables (for example, in
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
vertices are generated by
e04cbf. 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,
e04cbf 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
is discontinuous, while the function-value test should be sufficient on its own if
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:
– Integer
Input
-
On entry: , the number of variables.
Constraint:
.
-
2:
– Real (Kind=nag_wp) array
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 are of order unity.
On exit: the value of
corresponding to the function value in
f.
-
3:
– Real (Kind=nag_wp)
Output
-
On exit: the lowest function value found.
-
4:
– Real (Kind=nag_wp)
Input
-
On entry: the error tolerable in the function values, in the following sense. If
, for
, are the individual function values at the vertices of the current simplex, and if
is the mean of these values, then you can request that
e04cbf should terminate if
You may specify
if you wish to use only the termination criterion
(2) on the spatial values: see the description of
tolx.
Constraint:
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:
– Real (Kind=nag_wp)
Input
-
On entry: the error tolerable in the spatial values, in the following sense. If
denotes the ‘linearized’ volume of the current simplex, and if
denotes the ‘linearized’ volume of the initial simplex, then you can request that
e04cbf should terminate if
You may specify
if you wish to use only the termination criterion
(1) on function values: see the description of
tolf.
Constraint:
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:
– Subroutine, supplied by the user.
External Procedure
-
funct must evaluate the function
at a specified point. It should be tested separately before being used in conjunction with
e04cbf.
The specification of
funct is:
Fortran Interface
Integer, Intent (In) |
:: |
n |
Integer, Intent (Inout) |
:: |
iuser(*) |
Real (Kind=nag_wp), Intent (In) |
:: |
xc(n) |
Real (Kind=nag_wp), Intent (Inout) |
:: |
ruser(*) |
Real (Kind=nag_wp), Intent (Out) |
:: |
fc |
|
C Header Interface
void |
funct_ (const Integer *n, const double xc[], double *fc, Integer iuser[], double ruser[]) |
|
C++ Header Interface
#include <nag.h> extern "C" {
void |
funct_ (const Integer &n, const double xc[], double &fc, Integer iuser[], double ruser[]) |
}
|
-
1:
– Integer
Input
-
On entry: , the number of variables.
-
2:
– Real (Kind=nag_wp) array
Input
-
On entry: the point at which the function value is required.
-
3:
– Real (Kind=nag_wp)
Output
-
On exit: the value of the function at the current point .
-
4:
– Integer array
User Workspace
-
5:
– Real (Kind=nag_wp) array
User Workspace
-
funct is called with the arguments
iuser and
ruser as supplied to
e04cbf. You should use the arrays
iuser and
ruser to supply information to
funct.
funct must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which
e04cbf is called. Arguments denoted as
Input must
not be changed by this procedure.
Note: funct should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by
e04cbf. If your code inadvertently
does return any NaNs or infinities,
e04cbf is likely to produce unexpected results.
-
7:
– Subroutine, supplied by the NAG Library or the user.
External Procedure
-
monit may be used to monitor the optimization process. It is invoked once every iteration.
If no monitoring is required,
monit may be the dummy monitoring routine
e04cbk supplied by the NAG Library.
The specification of
monit is:
Fortran Interface
Integer, Intent (In) |
:: |
n, ncall |
Integer, Intent (Inout) |
:: |
iuser(*) |
Real (Kind=nag_wp), Intent (In) |
:: |
fmin, fmax, sim(n+1,n), serror, vratio |
Real (Kind=nag_wp), Intent (Inout) |
:: |
ruser(*) |
|
C++ Header Interface
#include <nag.h> extern "C" {
}
|
-
1:
– Real (Kind=nag_wp)
Input
-
On entry: the smallest function value in the current simplex.
-
2:
– Real (Kind=nag_wp)
Input
-
On entry: the largest function value in the current simplex.
-
3:
– Real (Kind=nag_wp) array
Input
-
On entry: the position vectors of the current simplex.
-
4:
– Integer
Input
-
On entry: , the number of variables.
-
5:
– Integer
Input
-
On entry: the number of times that
funct has been called so far.
-
6:
– Real (Kind=nag_wp)
Input
-
On entry: the current value of the standard deviation in function values used in termination test
(1).
-
7:
– Real (Kind=nag_wp)
Input
-
On entry: the current value of the linearized volume ratio used in termination test
(2).
-
8:
– Integer array
User Workspace
-
9:
– Real (Kind=nag_wp) array
User Workspace
-
monit is called with the arguments
iuser and
ruser as supplied to
e04cbf. You should use the arrays
iuser and
ruser to supply information to
monit.
monit must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which
e04cbf is called. Arguments denoted as
Input must
not be changed by this procedure.
-
8:
– Integer
Input
-
On entry: the maximum number of function evaluations to be allowed.
Constraint:
.
-
9:
– Integer array
User Workspace
-
10:
– Real (Kind=nag_wp) array
User Workspace
-
iuser and
ruser are not used by
e04cbf, but are passed directly to
funct and
monit and may be used to pass information to these routines.
-
11:
– Integer
Input/Output
-
On entry:
ifail must be set to
,
. If you are unfamiliar with this argument you should refer to
Section 4 in the Introduction to the NAG Library FL Interface for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
is recommended. If the output of error messages is undesirable, then the value
is recommended. Otherwise, if you are not familiar with this argument, the recommended value is
.
When the value is used it is essential to test the value of ifail on exit.
On exit:
unless the routine detects an error or a warning has been flagged (see
Section 6).
6
Error Indicators and Warnings
If on entry
or
, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
-
On entry, .
Constraint: .
On entry, .
Constraint: .
On entry, and .
Constraint: if then is greater than or equal to the machine precision.
On entry, and .
Constraint: if and then both should be greater than or equal to the machine precision.
On entry, and .
Constraint: if then is greater than or equal to the machine precision.
-
maxcal function evaluations have been completed without any other termination test passing. Check the coding of
funct before increasing the value of
maxcal.
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 7 in the Introduction to the NAG Library FL Interface for further information.
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library FL Interface for further information.
Dynamic memory allocation failed.
See
Section 9 in the Introduction to the NAG Library FL Interface for further information.
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
e04cbf 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 routine. Please also consult the
Users' Note for your implementation for any additional implementation-specific information.
Local workspace arrays of fixed lengths (depending on
n) are allocated internally by
e04cbf. The total size of these arrays amounts to
real elements.
The time taken by e04cbf 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 or function evaluations unless the size of the simplex is reduced, in which case function evaluations are required.
10
Example
This example finds a minimum of the function
This example uses the initial point
(see
Section 10.3), and we expect to reach the minimum at
.
10.1
Program Text
10.2
Program Data
None.
10.3
Program Results