# 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 )
where
• 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.

### 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.

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.

### Examples and Tests:

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

Last revised on 23 January 2016.