A global optimization algorithm using stochastic differential equations

ABSTRACT

SIGMA is a set of FORTRAN subprograms for solving the global optimization problem, which implements a method founded on the numerical solution of a Cauchy problem for a stochastic differential equation inspired by statistical mechanics. This paper gives a detailed description of the method as implemented in SIGMA and reports the results obtained by SIGMA attacking, on two different computers, a set of 37 test problems which were proposed elsewhere by the present authors to test global optimization software. The main conclusion is that SIGMA performs very well, solving 35 of the problems, including some very hard ones. Unfortunately, the limited results available to us at present do not appear sufficient to enable a conclusive comparison with other global optimization methods.

REFERENCES

• 1: Filippo Aluffi-Pentini , Valerio Parisi , Francesco Zirilli, A differential-equations algorithm for nonlinear equations, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.299-316, Sept. 1984 [doi>10.1145/1271.1631]
• 2: Filippo Aluffi-Pentini , Valerio Parisi , Francesco Zirilli, Algorithm 617 DAFNE: a differential-equations algorithm for nonlinear equations, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.317-324, Sept. 1984 [doi>10.1145/1271.1632]
• 3: ALUFFI-PENTINI, F., PARISI, V., AND ZIRILLI, F. Test problems for global optimization software. Tech Rep. ROM2F/85/030, Dip. di Fisica, 2a Univ. di Roma (Tot Vergata), Dec. 1985. To appear in the Computer J.
• 4: ALUFFI-PENTINI, F., PARISI, V., AND ZIRILLI, F. Global optimization and stochastic differential equations. J. Optim. Theo. App{. 47 (1986), 1-16.
• 5: ANGELETTI, A., CASTAGNARI, C., AND ZIRILLI, F. Asymptotic eigenvalue degeneracy for a class of one dimensional Fokker-Planck operators. J. Math. Phys. 26 (1985), 678-691.
• 6: BOENDER, C. G. E., RINNOOY KAN, A. H. G., TIMMER, G. T., AND STOUGIE, L. A stochastic method for global optimization. Math. Program. 22 (1982), 125-140.
• 7: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 8: DIXON, L. C. W., AND SZEG0, G. P., Eds. Towards Global Optimization 2. North-Holland, Amsterdam, The Netherlands, 1978.
• 9: KIRKPATRICK, S., GELATT, C. D., JR., AND VECCHI, M.P. Optimization by simulated annealing. Science 220 {1983), 671-680.
• 10: LEVY, A. V., AND MONTALVO, A. Algoritmo de tunelizaciSn para la optimizaciSn global de funciones. Comunicaciones t~cnicas, Serie Naranja, n. 204. IIMAS-UNAM, Mexico, D.F., 1979.
• 11: LEVY, A. V., AND MONTALVO, A. The tunneling algorithm for the global minimization of functions. SIAM J. Sci. Star. Comput. 6 (1985), 15-29.
• 12: POWELL, M. J. D., Ed. Nonlinear Optimization 1981. Academic Press, London, 1982.
• 13: RINNOOY KAN, A. H. G., AND TIMMER, G.W. Stochastic methods for global optimization. Tech. Rep. 8317/0, Erasmus Univ., Rotterdam, The Netherlands, 1984.
• 14: SCHUSS, Z. Theory And Applications Of Stochastic Differential Equations. J. Wiley, New York, 1980, Chap. 8.
• 15: ZXRILLI, F. The use of ordinary differential equations in the solution of nonlinear systems of equations. In Nonlinear Optimization 1981, M. J. D. Powell, Ed., Academic Press, London, 1982, 39-47.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis; Certification and testing

General Terms:
Algorithms, Languages, Theory, Verification