### Description

An implementation of the Nelder-Mead algorithm for derivative-free optimization / function minimization.

### Usage

neldermead( fn, x0, ..., adapt = TRUE,
tol = 1e-10, maxfeval = 10000,
step = rep(1.0, length(x0)))

tol = 1e-10, maxfeval = 10000,
step = rep(1, length(x0)))


### Arguments

 fn nonlinear function to be minimized. x0 starting point for the iteration. adapt logical; adapt to parameter dimension. tol terminating limit for the variance of function values; can be made *very* small, like tol=1e-50. maxfeval maximum number of function evaluations. step size and shape of initial simplex; relative magnitudes of its elements should reflect the units of the variables. ... additional arguments to be passed to the function. lower, upper lower and upper bounds.

### Details

Also called a ‘simplex’ method for finding the local minimum of a function of several variables. The method is a pattern search that compares function values at the vertices of the simplex. The process generates a sequence of simplices with ever reducing sizes.

The simplex function minimisation procedure due to Nelder and Mead (1965), as implemented by O'Neill (1971), with subsequent comments by Chambers and Ertel 1974, Benyon 1976, and Hill 1978. For another elaborate implementation of Nelder-Mead in R based on Matlab code by Kelley see package ‘dfoptim’.

eldermead can be used up to 20 dimensions (then ‘tol’ and ‘maxfeval’ need to be increased). With adapt=TRUE it applies adaptive coefficients for the simplicial search, depending on the problem dimension – see Fuchang and Lixing (2012). This approach especially reduces the number of function calls.

With upper and/or lower bounds, neldermeadb applies transfinite to define the function on all of R^n and to retransform the solution to the bounded domain. Of course, if the optimum is near to the boundary, results will not be as accurate as when the minimum is in the interior.

### Value

List with following components:

 xmin minimum solution found. fmin value of f at minimum. fcount number of iterations performed. restarts number of restarts. errmess error message

### Note

Original FORTRAN77 version by R O'Neill; MATLAB version by John Burkardt under LGPL license. Re-implemented in R by Hans W. Borchers.

### References

Nelder, J., and R. Mead (1965). A simplex method for function minimization. Computer Journal, Volume 7, pp. 308-313.

O'Neill, R. (1971). Algorithm AS 47: Function Minimization Using a Simplex Procedure. Applied Statistics, Volume 20(3), pp. 338-345.

J. C. Lagarias et al. (1998). Convergence properties of the Nelder-Mead simplex method in low dimensions. SIAM Journal for Optimization, Vol. 9, No. 1, pp 112-147.

Fuchang Gao and Lixing Han (2012). Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications, Vol. 51, No. 1, pp. 259-277.

hookejeeves

### Examples

##  Classical tests as in the article by Nelder and Mead
# Rosenbrock's parabolic valley
rpv <- function(x) 100*(x[2] - x[1]^2)^2 + (1 - x[1])^2
x0 <- c(-2, 1)

# Fletcher and Powell's helic valley
fphv <- function(x)
100*(x[3] - 10*atan2(x[2], x[1])/(2*pi))^2 +
(sqrt(x[1]^2 + x[2]^2) - 1)^2 +x[3]^2
x0 <- c(-1, 0, 0)
neldermead(fphv, x0)                    #  1 0 0

# Powell's Singular Function (PSF)
psf <- function(x)  (x[1] + 10*x[2])^2 + 5*(x[3] - x[4])^2 +
(x[2] - 2*x[3])^4 + 10*(x[1] - x[4])^4
x0 <- c(3, -1, 0, 1)
neldermead(psf, x0)         #  0 0 0 0, needs maximum number of function calls

lower <- c(-Inf, 0,   0)
upper <- c( Inf, 0.5, 1)
x0 <- c(0, 0.1, 0.1)
neldermeadb(fnRosenbrock, c(0, 0.1, 0.1), lower = lower, upper = upper)
# $xmin = c(0.7085595, 0.5000000, 0.2500000) #$fmin = 0.3353605

## Not run:
# Can run Rosenbrock's function in 30 dimensions in one and a half minutes:
# $xmin # [1] 0.9999998 1.0000004 1.0000000 1.0000001 1.0000000 1.0000001 # [7] 1.0000002 1.0000001 0.9999997 0.9999999 0.9999997 1.0000000 # [13] 0.9999999 0.9999994 0.9999998 0.9999999 0.9999999 0.9999999 # [19] 0.9999999 1.0000001 0.9999998 1.0000000 1.0000003 0.9999999 # [25] 1.0000000 0.9999996 0.9999995 0.9999990 0.9999973 0.9999947 #$fmin