AMOEBA

The AMOEBA function performs multidimensional minimization of a function Func(x), where x is an n-dimensional vector, using the downhill simplex method ¹.

The downhill simplex method is not as efficient as Powell’s method, and usually requires more function evaluations. However, the simplex method requires only function evaluations—not derivatives—and may be more reliable than Powell’s method.

This routine is written in the IDL language. Its source code can be found in the file amoeba.pro in the lib subdirectory of the IDL distribution ².

Examples

Use AMOEBA to find the slope and intercept of a straight line that fits a given set of points, minimizing the maximum error. The function to be minimized (FUNC, in this case) returns the maximum error, given p[0] = intercept, and p[1] = slope.

; First define the function FUNC:
FUNCTION FUNC, P
COMMON FUNC_XY, X, Y
RETURN, MAX(ABS(Y - (P[0] + P[1] * X)))
END
; Put the data points into a common block so they are accessible to
; the function: 
COMMON FUNC_XY, X, Y
; Define the data points:
X = FINDGEN(17)*5
Y = [ 12.0,  24.3,  39.6,  51.0,  66.5,  78.4,  92.7, 107.8, $
    120.0, 135.5, 147.5, 161.0, 175.4, 187.4, 202.5, 215.4, 229.9]
; Call the function. Set the fractional tolerance to 1 part in
; 10^5, the initial guess to [0,0], and specify that the minimum
; should be found within a distance of 100 of that point: 
R = AMOEBA(1.0e-5, SCALE=1.0e2, P0 = [0, 0], FUNCTION_VALUE=fval)
; Check for convergence:
IF N_ELEMENTS(R) EQ 1 THEN MESSAGE, 'AMOEBA failed to converge'
; Print results:
PRINT, 'Intercept, Slope:', r, $
       'Function value (max error): ', fval[0]
END

IDL prints:

Intercept, Slope:      11.4100      2.72800

Function value:       1.33000

Syntax

Result = AMOEBA( Ftol [, FUNCTION_NAME=string] [, FUNCTION_VALUE=variable] [, NCALLS=value] [, NMAX=value] [, P0=vector, SCALE=vector | , SIMPLEX=array] )

Return Value

If the minimum is found, AMOEBA returns an n-element vector corresponding to the function’s minimum value. If a minimum within the given tolerance is not found within the specified number of iterations, AMOEBA returns a scalar value of -1. Results are returned with the same precision (single- or double-precision floating-point) as is returned by the user-supplied function to be minimized.

Arguments

Ftol

The fractional tolerance to be achieved in the function value—this is the fractional range between the maximum and minimum values of the function at the simplex points [2*abs(max-min)/[abs(max) + abs(min)]]. If the function you supply returns a single-precision result, Ftol should never be less than your machine’s floating-point precision—the value contained in the EPS field of the structure returned by the MACHAR function. If the function you supply returns a double-precision floating-point value, Ftol should not be less than your machine's double-precision floating-point precision. See MACHARfor details.

Keywords

FUNCTION_NAME

Set this keyword equal to a string containing the name of the function to be minimized. If this keyword is omitted, AMOEBA assumes that an IDL function named “FUNC” is to be used.

The function to be minimized must be written as an IDL function and compiled prior to calling AMOEBA. This function must accept an n-element vector as its only parameter and return a scalar single- or double precision floating-point value as its result.

See the Example section below for an example function.

FUNCTION_VALUE

Set this keyword equal to a named variable that will contain an (n+1)-element vector of the function values at the simplex points. The first element contains the function minimum.

NCALLS

Set this keyword equal to a named variable that will contain a count of the number of times the function was evaluated.

NMAX

Set this keyword equal to a scalar value specifying the maximum number of function evaluations allowed before terminating. The default is 5000.

P0

Set this keyword equal to an n-element single- or double-precision floating-point vector specifying the initial starting point. Note that if you specify P0, you must also specify SCALE.

For example, in a 3-dimensional problem, if the initial guess is the point [0,0,0], and you know that the function’s minimum value occurs in the interval:

-10 < X[0] < 10, -100 < X[1] < 100, -200 < X[(2] < 200,

specify: P0=[0,0,0] and SCALE=[10, 100, 200].

Alternately, you can omit P0 and SCALE and specify SIMPLEX.

SCALE

Set this keyword equal to a scalar or n-element vector containing the problem’s characteristic length scale for each dimension. SCALE is used with P0 to form an initial (n+1) point simplex. If all dimensions have the same scale, set SCALE equal to a scalar.

If SCALE is specified as a scalar, the function’s minimum lies within a distance of SCALE from P0. If SCALE is an N-dimensional vector, the function's minimum lies within the Ndim+1 simplex with the vertices P0, P0 + [1,0,...,0] * SCALE, P0 + [0,1,0,...,0] * SCALE, ..., and P0+[0,0,...,1] * SCALE.

SIMPLEX

Set this keyword equal to an n by n+1 single- or double-precision floating-point array containing the starting simplex. After AMOEBA has returned, the SIMPLEX array contains the simplex enclosing the function minimum. The first point in the array, SIMPLEX[*,0], corresponds to the function’s minimum. This keyword is ignored if the P0 and SCALE keywords are set.

Version History

5.0	Introduced

Resources and References

1. Nelder and Mead, 1965, Computer Journal, Vol 7, pp 308-313.

2. AMOEBA is based on the routine amoeba described in section 10.4 of Numerical Recipes in C: The Art of Scientific Computing (Second Edition), published by Cambridge University Press, and is used by permission.