e04cbf : NAG Library, Mark 26

e04cbf minimizes a general function

F (x)

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.

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 nagmk26.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)

e04cbf finds an approximation to a minimum of a function

F

of

n

variables. You must supply a subroutine 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 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

F

is discontinuous, while the function-value test should be sufficient on its own if

F

is continuous.

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

If on entry

ifail = 0

or

- 1

, explanatory error messages are output on the current error message unit (as defined by x04aaf).

Errors or warnings detected by the routine:

On a successful exit the accuracy will be as defined by tolf or tolx, depending on which criterion was satisfied first.

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

n^{2} + 6 n + 2

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

1

or

2

function evaluations unless the size of the simplex is reduced, in which case

n + 1

function evaluations are required.

This example finds a minimum of the function

F (x_{1}, x_{2}) = e^{x_{1}} (4 x_{1}^{2} + 2 x_{2}^{2} + 4 x_{1} x_{2} + 2 x_{2} + 1) .

This example uses the initial point

(- 1, 1)

(see Section 10.3), and we expect to reach the minimum at

(0.5, - 1)

.

None.

NAG Library Routine Document

e04cbf (uncon_simplex)

▸▿ Contents

1

Purpose

2

Specification

3

Description

4

References

5

Arguments

6

Error Indicators and Warnings

7

Accuracy

8

Parallelism and Performance

9

Further Comments

10

Example

10.1

Program Text

10.2

Program Data

10.3

Program Results

NAG Library Routine Document

e04cbf (uncon_simplex)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results