COMPASS_SEARCH
The Compass Search Optimization Algorithm

COMPASS_SEARCH is a Python library which seeks the minimizer of a scalar function of several variables using compass search, a direct search algorithm that does not use derivatives.

The algorithm, which goes back to Fermi and Metropolis, is easy to describe. The algorithm begins with a starting point X, and a step size DELTA.

For each dimension I, the algorithm considers perturbing X(I) by adding or subtracting DELTA.

If a perturbation is found which decreases the function, this becomes the new X. Otherwise DELTA is halved.

The iteration halts when DELTA reaches a minimal value.

The algorithm is not guaranteed to find a global minimum. It can, for instance, easily be attracted to a local minimum. Moreover, the algorithm can diverge if, for instance, the function decreases as the argument goes to infinity.

Usage:

[ x, fx, k ] = compass_search ( f, m, x, delta_tol, delta, k_max )

• f is the name of the function, of the form "def f ( m, x )", returning a single real scalar value.
• m is the number of variables.
• x is an M-vector containing a starting point for the iteration.
• delta_tol is the minimum allowed size of DELTA, and must be positive.
• delta is the starting stepsize.
• k_max is the maximum number of steps allowed. This is the only way to avoid an infinite loop if the function decreases as it goes to infinity.
• x is the program's estimate for the minimizer of the function;
• fx is the function value at x.
• k is the number of steps taken.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

COMPASS_SEARCH is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

ASA047, a Python library which minimizes a scalar function of several variables using the Nelder-Mead algorithm.

TOMS178, a Python library which optimizes a scalar functional of multiple variables using the Hooke-Jeeves method, by Arthur Kaupe. This is a version of ACM TOMS algorithm 178.

Author:

John Burkardt

Reference:

1. Tamara Kolda, Robert Michael Lewis, Virginia Torczon,
   Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods,
   SIAM Review,
   Volume 45, Number 3, 2003, pages 385-482.

Source Code:

• beale.py, defines Beale's function.
• bohach1.py, defines the Bohachevsky function #1.
• bohach2.py, defines the Bohachevsky function #2.
• broyden.py, defines Beale's function.
• compass_search.py, the coordinate search optimization algorithm.
• extended_rosenbrock.py, defines the extended Rosenbrock function.
• goldstein_price.py, defines the Goldstein-Price polynomial.
• himmelblau.py, defines the Himmelblau function.
• local.py, defines the "local" function.
• mckinnon.py, defines the McKinnon function.
• powell.py, defines the Powell function.
• r8vec_print.py, prints an R8VEC.
• rosenbrock.py, defines the Rosenbrock function.
• timestamp.py, prints the YMDHMS date as a timestamp.

Examples and Tests:

• compass_search_test.py, calls all the tests.
• compass_search_test.sh, runs all the tests.
• compass_search_test.txt, the output file.

You can go up one level to the Python source codes.