MCS: Global Optimization by Multilevel Coordinate Search

MCS is a Matlab program for bound constrained global optimization using function values only, based on a multilevel coordinate search that balances global and local search. The local search is done via sequential quadratic programming.

MCS attempts to find the global minimizer of the bound constrained optimization problem

   min  f(data,x)
   s.t. x in [u,v] (a box in R^n)
where data is a fixed data vector (or other data structure), and f is a function of data and x defined by a user-provided m-File,

The search is not exhaustive; so the global minimum may be missed. However, a comparison to other global optimization algorithms shows excellent performance in many cases, especially in low dimensions.

The easy to use version runs without any parameters that need to be set by the user; but experienced users may make more sophisticated choices. See runmcs.m (9K) for a test driver, and advice on how to choose the tuning parameters.

The required m-files (Version 2.0 from Feb. 8, 2000, with a lot of changes to the first version) can be downloaded as the gzipped tar file mcs.tar.gz (35K).

To run the programs you also need the Matlab 5 programs MINQ (bound constrained quadratic program solver) and GLS (global line search).


Derivation of the algorithm and underlying theory is in:

W. Huyer and A. Neumaier, Global optimization by multilevel coordinate search, J. Global Optimization 14 (1999), 331-355.
pdf file (361K),

Abstract. Inspired by the DIRECT method by Jones, Perttunen and Stuckman, we present a global optimization algorithm based on multilevel coordinate search. It is guaranteed to converge if the function is continuous in the neighborhood of a global minimizer. By starting a local search from certain good points, an improved convergence result is obtained. We discuss implementation details and give some numerical results.


Source: http://www.mat.univie.ac.at/~neum/software/mcs/


Global (and Local) Optimization

my home page (http://www.mat.univie.ac.at/~neum)

Arnold Neumaier (Arnold.Neumaier@univie.ac.at)