R port of the Scilab neldermead module

Description

The goal of this package is to provide a Nelder-Mead direct search optimization method. That Nelder-Mead algorithm may be used in the following optimization context:

  • there is no need to provide the derivatives of the objective function,

  • the number of parameters is small (up to 10-20),

  • there are bounds and/or non linear constraints.

Design

This package provides the following components:

  • neldermead provides various Nelder-Mead variants and manages for Nelder-Mead specific settings, such as the method to compute the initial simplex, the specific termination criteria,

  • fminsearch provides a simplified Nelder-Mead algorithm. Specific termination criteria, initial simplex and auxiliary settings are automatically configured.

  • fminbnd provides a simplified Box algorithm, ie the equivalent of fminsearch for unconstrained search.

  • optimset, optimget provide commands to emulate their Scilab counterparts.

  • optimplotfunccount, optimplotx and optimplotfval provide plotting features for the fminsearch function (Not implemented yet).

  • nmplot provides a high-level component which provides directly output pictures for Nelder-Mead algorithm. (Not implemented yet).

The current component is based on the following packages

  • optimbase: provides an abstract class for a general optimization component, including the number of variables, the minimum and maximum bounds, the number of non linear inequality constraints, the loggin system, various termination criteria, the cost function, etc...

  • optimsimplex: provides a class to manage a simplex made of an arbitrary number of vertices, including the computation of a simplex by various methods (axes, regular, Pfeffer's, randomized bounds), the computation of the size by various methods (diameter, sigma+, sigma-, etc...),

Features

The following is a list of features the Nelder-Mead prototype algorithm currently provides:

  • Provides 3 algorithms, including

    • the fixed shape algorithm of Spendley et al.,

    • the variable shape algorithm of Nelder and Mead,

    • Box's 'complex' algorithm managing bounds and nonlinear inequality constraints based on arbitrary number of vertices in the simplex.

  • Manage various simplex initializations:

    • initial simplex given by user,

    • initial simplex computed with a length and along the coordinate axes,

    • initial regular simplex computed with formula of Spendley et al.,

    • initial simplex computed by a small perturbation around the initial guess point.

  • Manage cost function:

    • optional additional argument,

    • direct communication of the task to perform: cost function or inequality constraints.

  • Manage various termination criteria, including maximum number of iterations, tolerance on function value (relative or absolute):

    • tolerance on x (relative or absolute),

    • tolerance on standard deviation of function value (original termination criteria in Box 1965),

    • maximum number of evaluations of cost function,

    • absolute or relative simplex size.

  • Manage the history of the convergence, including:

    • history of function values,

    • history of optimum point,

    • history of simplices,

    • history of termination criteria.

  • Provide a plot command which allows to graphically see the history of the simplices toward the optimum (Not yet implemented).

  • Provide query features for the status of the optimization process: number of iterations, number of function evaluations, status of execution, function value at initial point, function value at optimal point, etc...

  • Kelley restart based on simplex gradient.

  • O'Neill restart based on factorial search around optimum.

Details

Package: neldermead
Type: Package
Version: 1.0-10
Date: 2015-01-11
License: CeCILL-2
LazyLoad: yes

See vignette('neldermead',package='neldermead') for more information.

Author(s)

Author of Scilab neldermead module: Michael Baudin (INRIA - Digiteo)

Author of R adaptation: Sebastien Bihorel (sb.pmlab@gmail.com)

References

'Sequential Application of Simplex Designs in Optimisation and Evolutionary Operation', Spendley, W. and Hext, G. R. and Himsworth, F. R., American Statistical Association and American Society for Quality, 1962

'A Simplex Method for Function Minimization', Nelder, J. A. and Mead, R., The Computer Journal, 1965

'A New Method of Constrained Optimization and a Comparison With Other Methods', M. J. Box, The Computer Journal 1965 8(1):42-52, 1965 by British Computer Society

'Discussion and correspondence: modification of the complex method of constrained optimization', J. A. Guin, The Computer Journal, 1968

'Detection and Remediation of Stagnation in the Nelder–Mead Algorithm Using a Sufficient Decrease Condition', Kelley C. T., SIAM J. on Optimization, 1999

'Iterative Methods for Optimization', C. T. Kelley, SIAM Frontiers in Applied Mathematics, 1999

'Algorithm AS47 - Function minimization using a simplex procedure', O'Neill, R., Applied Statistics, 1971

See Also

optimbase optimsimplex