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.

Related Data and Programs: {#related-data-and-programs align=”center”}

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”}

• compass_search.cpp, the source code.
• compass_search.hpp, the include file.

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

• compass_search_prb.cpp, a sample calling program.
• compass_search_prb_output.txt, the output file.

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

• COMPASS_SEARCH carries out a direct search minimization algorithm.
• R8_ABS returns the absolute value of an R8.
• R8VEC_COPY copies an R8VEC.
• R8VEC_PRINT prints an R8VEC.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

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

---

Last revised on 05 January 2012.