Algorithm 744: a stochastic algorithm for global optimization with constraints

ABSTRACT

A stochastic algorithm is presented for finding the global optimum of a function of n variables subject to general constraints. The algorithm is intended for moderate values of n, but it can accommodate objective and constraint functions that are discontinuous and can take advantage of parallel processors. The performance of this algorithm is compared to that of the Nelder-Mead Simplex algorithm and a Simulated Annealing algorithm on a variety of nonlinear functions. In addition, one-, two-, four-, and eight-processor versions of the algorithm are compared using 64 of the nonlinear problems with constraints collected by Hock and Schittkowski. In general, the algorithm is more robust than the Simplex algorithm, but computationally more expensive. The algorithm appears to be as robust as the Simulated Annealing algorithm, but computationally cheaper. Issues discussed include algorithm speed and robustness, applicability to both computer and mathematical models, and parallel efficiency.

REFERENCES

• 1: A. Corana , M. Marchesi , C. Martini , S. Ridella, Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm, ACM Transactions on Mathematical Software (TOMS), v.13 n.3, p.262-280, Sept. 1987 [doi>10.1145/29380.29864]
• 2: Willi Hock , K. Schittkowski, Test Examples for Nonlinear Programming Codes, Springer-Verlag New York, Inc., Secaucus, NJ, 1981
• 3: KIRKPATRICK, S., GELATT, C. D., AND VECCHI, M.P. 1983. Optimization by simulated annealing. Science 220, 671-679.
• 4: LUENBERCER, D. G. 1986. Linear and Nonlinear Programming. Addison-Wesley, Reading, Mass.
• 5: MASRI, S. F. AND BEKEY, G.A. 1980. A global optimization algorithm using adaptive random search. Appl. Math. Comput. 7, 353-375.
• 6: NELDER, J. A. AND MEAD, R. 1965. A simplex method for function minimization. Comput. J. 7, 308-313.
• 7: PANNETIER, J. 1990. Simulated annealing: An introductory review. Inst. Phys. Conf. Ser. 107, 23 -44.
• 8: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 9: Aimo Torn , Antanas Zilinskas, Global optimization, Springer-Verlag New York, Inc., New York, NY, 1989

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing

General Terms:
Algorithms, Performance

Keywords:
constrained optimization, global optimization, stochastic optimization, test functions