compass_search

compass_search, a Python code 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 MIT 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 code which minimizes a scalar function of several variables using the Nelder-Mead algorithm.

toms178, a Python code 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:

• compass_search.py, the source code.
• compass_search.sh, runs all the tests.
• compass_search.txt, the output file.