COMPASS_SEARCH
The Compass Search Optimization Algorithm

COMPASS_SEARCH is a MATLAB 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 "function handle"; that is, either a quoted expression for the function, or the name of an M-file that defines the function, preceded by an "@" sign; The function should have the form function value = f(m,x).
• 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 FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

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

ENTRUST, a MATLAB program which minimizes a scalar function of several variables using trust-region methods.

NELDER_MEAD, a MATLAB program which minimizes a scalar function of several variables using the Nelder-Mead algorithm.

PRAXIS, a FORTRAN90 library which implements the principal axis method of Richard Brent for minimization of a function without the use of derivatives.

TEST_OPT, a MATLAB library which defines test problems requiring the minimization of a scalar function of several variables.

TOMS178, a MATLAB library which optimizes a scalar functional of multiple variables using the Hooke-Jeeves method.

Author:

John Burkardt

Reference:

1. Evelyn Beale,
   On an Iterative Method for Finding a Local Minimum of a Function of More than One Variable,
   Technical Report 25,
   Statistical Techniques Research Group,
   Princeton University, 1958.
2. Richard Brent,
   Algorithms for Minimization without Derivatives,
   Dover, 2002,
   ISBN: 0-486-41998-3,
   LC: QA402.5.B74.
3. Charles Broyden,
   A class of methods for solving nonlinear simultaneous equations,
   Mathematics of Computation,
   Volume 19, 1965, pages 577-593.
4. David Himmelblau,
   Applied Nonlinear Programming,
   McGraw Hill, 1972,
   ISBN13: 978-0070289215,
   LC: T57.8.H55.
5. 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.
6. Ken McKinnon,
   Convergence of the Nelder-Mead simplex method to a nonstationary point,
   SIAM Journal on Optimization,
   Volume 9, Number 1, 1998, pages 148-158.
7. Zbigniew Michalewicz,
   Genetic Algorithms + Data Structures = Evolution Programs,
   Third Edition,
   Springer, 1996,
   ISBN: 3-540-60676-9,
   LC: QA76.618.M53.
8. Jorge More, Burton Garbow, Kenneth Hillstrom,
   Testing unconstrained optimization software,
   ACM Transactions on Mathematical Software,
   Volume 7, Number 1, March 1981, pages 17-41.
9. Michael Powell,
   An Iterative Method for Finding Stationary Values of a Function of Several Variables,
   Computer Journal,
   Volume 5, 1962, pages 147-151.
10. Howard Rosenbrock,
    An Automatic Method for Finding the Greatest or Least Value of a Function,
    Computer Journal,
    Volume 3, 1960, pages 175-184.

Source Code:

• compass_search.m, the coordinate search optimization algorithm.
• r8vec_print.m, prints an R8VEC.
• timestamp.m, prints the YMDHMS date as a timestamp.

Examples and Tests:

COMPASS_SEARCH_TEST calls all the tests.

• compass_search_test.m, calls all the tests.
• compass_search_test_output.txt, the output file.

BEALE is the Beale function, for which M=2.

• beale.m, defines Beale's function.
• beale_test.m, tests COMPASS_SEARCH with the function.

BOHACH1 is the Bohachevsky function #1, for which M=2.

• bohach1.m, defines the Bohachevsky function #1.
• bohach1_test.m, tests COMPASS_SEARCH with the function.

BOHACH2 is the Bohachevsky function #2, for which M=2.

• bohach2.m, defines the Bohachevsky function #2.
• bohach2_test.m, tests COMPASS_SEARCH with the function.

BROYDEN is the two dimensional modified Broyden function, for which M=2.

• broyden.m, defines Beale's function.
• broyden_test.m, tests COMPASS_SEARCH with the function.

EXTENDED_ROSENBROCK is the "extended" Rosenbrock function. This version of the Rosenbrock function allows the spatial dimension M to be arbitrary, except that it must be even.

• extended_rosenbrock.m, defines the extended Rosenbrock function.
• extended_rosenbrock_test.m, tests COMPASS_SEARCH with the function.

GOLDSTEIN_PRICE is the Goldstein-Price polynomial, for which M=2.

• goldstein_price.m, defines the Goldstein-Price polynomial.
• goldstein_price_test.m, tests COMPASS_SEARCH with the function.

HIMMELBLAU is the Himmelblau function, for which M = 2, and which has four global minima.

• himmelblau.m, defines the Himmelblau function.
• himmelblau_test.m, tests COMPASS_SEARCH with the function.

LOCAL is a badly scaled function with a local minimum, for which M=2.

• local.m, defines the "local" function.
• local_test.m, tests COMPASS_SEARCH with the function.

MCKINNON is the McKinnon function, for which M=2. This function can cause problems for the Nelder-Mead optimization algorithm.

• mckinnon.m, defines the McKinnon function.
• mckinnon_test.m, tests COMPASS_SEARCH with the function.

POWELL is the Powell singular quartic function, for which M = 4.

• powell.m, defines the Powell function.
• powell_test.m, tests COMPASS_SEARCH with the function.

ROSENBROCK is the Rosenbrock "banana" function, for which M = 2.

• rosenbrock.m, defines the Rosenbrock function.
• rosenbrock_test.m, tests COMPASS_SEARCH with the function.

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