jburkardt

COMPASS_SEARCH\ The Compass Search Optimization Algorithm {#compass_search-the-compass-search-optimization-algorithm align=”center”} =========================================


COMPASS_SEARCH is a C++ 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.

Licensing: {#licensing align=”center”}

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

Languages: {#languages align=”center”}

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

ASA047, a C++ 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 C++ library which defines test problems requiring the minimization of a scalar function of several variables.

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

Author: {#author align=”center”}

John Burkardt

Reference: {#reference align=”center”}

  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: {#source-code align=”center”}

Examples and Tests: {#examples-and-tests align=”center”}

List of Routines: {#list-of-routines align=”center”}

You can go up one level to the C++ source codes.


Last revised on 05 January 2012.