NELDER_MEAD is a MATLAB program which seeks the minimizer of a scalar function of several variables, by Jeff Borggaard.
The algorithm is easy to visualize. The user supplies an initial set of points that represent solution estimates. The number of points supplied is one greater than the spatial dimension, so they form a "simplex" - in 2D, this is simply a triangle. The algorithm then evaluates the function at each point on the simplex, and then considers various ways of seeking a better estimate, including replacing one vertex of the simplex by its reflected image, or by shrinking or expanding the simplex. An animation of the procedure looks almost like a little triangular creature trying to blindly feel its way downhill.
Although the user specifies an initial simplex of starting values, the algorithm is not constrained to search only within that simplex. This means that the user cannot force the algorithm to search only within a restricted region.
x_opt = nelder_mead ( simplex, f, flag )where
Very simple functions can be input as a quoted string. Thus, one could specify the f argument as '(x(1)-2*x(2)+7)^2'; However, for more complicated functions it makes sense to prepare an M-file that defines the function. For this same example, a suitable M-file would be:
function f = example ( x )
f = ( x(1) - 2 * x(2) + 7 )^2;
If this information was stored in an M-file called example.m, then one might invoke the optimization program with a command like
x_opt = nelder_mead ( x_init, @example, 0 )
MATLAB's built in command fminsearch minimizes a scalar function of several variables using the Nelder-Mead algorithm.
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
NELDER_MEAD is available in a MATLAB version.
ASA047, a MATLAB library which minimizes a scalar function of several variables using the Nelder-Mead algorithm.
COMPASS_SEARCH, a MATLAB library which seeks the minimizer of a scalar function of several variables using compass search, a direct search algorithm that does not use derivatives.
ENTRUST, a MATLAB program which minimizes a scalar function of several variables using trust-region methods.
POLYNOMIALS, a MATLAB library which defines multivariate polynomials over rectangular domains, for which certain information is to be determined, such as the maximum and minimum values.
PRAXIS, a MATLAB library which implements the principal axis method for minimization of a function without the use of derivatives, by Richard Brent.
TEST_OPT, a MATLAB library which defines test problems requiring the minimization of a scalar function of several variables.
TOMS178, a MATLAB library which optimizes a scalar functional of multiple variables using the Hooke-Jeeves method.
Jeff Borggaard, Mathematics Department, Virginia Tech.
BEALE is the Beale function, for which N = 2.
BOHACH1 is the Bohachevsky function #1, for which N=2.
BOHACH2 is the Bohachevsky function #2, for which N=2.
EXTENDED_ROSENBROCK is the "extended" Rosenbrock function. This version of the Rosenbrock function allows the spatial dimension to be arbitrary, except that it must be even.
GOLDSTEIN_PRICE is the Goldstein-Price polynomial, for which N=2.
HIMMELBLAU is the Himmelblau function:
f(x) = (x(1)^2 + x(2) - 11)^2 + (x(1) + x(2)^2 - 7)^2
which has four global minima.
LOCAL is a badly scaled function with a local minimum, for which N=2.
MCKINNON is the McKinnon function, for which N=2. This function can cause problems for the Nelder-Mead optimization algorithm.
POWELL is the Powell singular quartic function, for which N = 4.
ROSENBROCK is the Rosenbrock "banana" function. The contour lines form a nested set of "banana", which can make convergence very slow:
f(x) = ( 1 - x(1) )^2 + 100 * ( x(2) - x(1) * x(1) )^2
You can go up one level to the MATLAB source codes.