×

Global optimization and simulated annealing. (English) Zbl 0753.90060

The first six pages of this well-written paper can be considered an introduction to global optimization algorithms that first focuses on stochastic methods, then on simulated annealing. The authors then present theoretical results for an idealized simulated annealing algorithm that are based on the ergodic theory of Markov chains. The main result gives a formula for the probability that this idealized algorithm converges to within a given tolerance of global minima of the objective function.
A second part of the paper considers practical variants of the ideal algorithm. Here, the authors present natural choices for tuning parameters, such as the length of the truncated Markov chains, stopping criteria, and initial choice of and amount to decrement the control parameter. A theorem, analogues to that for the ideal algorithm, is presented.
Numerical results comparing six other algorithms to the one in the paper are reported. The authors claim that the new algorithm may allow solution of higher-dimensional optimization problems, since it uses less storage than alternatives, yet does not require substantially greater running time. They indicate that further research is necessary to refine the ideas. A significant set of test problems for global optimization appears in two appendices. Twenty-seven references appear.

MSC:

90C30 Nonlinear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E.H.L. Aarts and P.J.M. van Laarhoven, ”Statistical cooling: a general approach to combinatorial optimization problems,”Philips Journal of Research 40 (1985) 193–226.
[2] E.H.L. Aarts and J.H.M. Korst,Simulated Annealing and Boltzmann Machines (Wiley, Chichester, 1988). · Zbl 0674.90059
[3] F. Aluffi-Pentini, V. Parisi and F. Zirilli, ”Global optimization and stochastic differential equations,”Journal of Optimization Theory and Applications 47 (1985) 1–16. · Zbl 0549.65038 · doi:10.1007/BF00941312
[4] I.O. Bohachevsky, M.E. Johnson and M.L. Stein, ”Generalized simulated annealing for function optimization,”Technometrics 28 (1986) 209–217. · Zbl 0609.65045 · doi:10.2307/1269076
[5] T.-S. Chiang, C.-R. Hwang and S.-J. Sheu, ”Diffusion for global optimization in \(\mathbb{R}\) n ,”SIAM Journal on Control and Optimization 25 (1987) 737–753. · Zbl 0622.60093 · doi:10.1137/0325042
[6] L. De Biase and F. Frontini, ”A stochastic method for global optimization: its structure and numerical performance,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation 2 (North-Holland, Amsterdam, 1978) pp. 85–102. · Zbl 0396.90082
[7] L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation 2 (North-Holland, Amsterdam, 1978a). · Zbl 0385.00011
[8] L.C.W. Dixon and G.P. Szegö, ”The global optimisation problem: an introduction,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation 2 (North-Holland, Amsterdam, 1978b) pp. 1–15.
[9] J.L. Doob,Stochastic Processes (Wiley, New York, 1953).
[10] W. Feller,An Introduction to Probability Theory and its Applications, Vol 1 (Wiley, New York, 1957). · Zbl 0077.12201
[11] S. Geman and C.-R. Hwang, ”Diffusions for global optimization,”SIAM Journal on Control and Optimization 24 (1986) 1031–1043. · Zbl 0602.60071 · doi:10.1137/0324060
[12] J. Gomulka, ”Deterministic versus probabilistic approaches to global optimisation,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation 2 (North-Holland, Amsterdam, 1978a) pp. 19–30. · Zbl 0401.90087
[13] J. Gomulka, ”A users experience with Törn’s clustering algorithm,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation 2 (North-Holland, Amsterdam, 1978b) pp. 63–70. · Zbl 0388.90086
[14] A. Khachaturyan, ”Statistical mechanics approach in minimizing a multivariable function,”Journal of Mathematical Physics 27 (1986) 1834–1838. · Zbl 0595.60099 · doi:10.1063/1.527052
[15] S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi, ”Optimization by simulated annealing,”Science 220 (1983) 671–680. · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[16] H.J. Kushner, ”Asymptotic global behavior for stochastic approximation and diffusions with slowly decreasing noise effects: global minimization via Monte Carlo,”SIAM Journal on Applied Mathematics 47 (1987) 169–185. · Zbl 0615.60024 · doi:10.1137/0147010
[17] P.J.M. van Laarhoven and E.H.L. Aarts,Simulated Annealing: Theory and Applications (Reidel, Dordrecht, 1987). · Zbl 0643.65028
[18] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller and E. Teller, ”Equation of state calculations by fast computing machines,”The Journal of Chemical Physics 21 (1953) 1087–1092. · doi:10.1063/1.1699114
[19] W.L. Price, ”A controlled random search procedure for global optimisation,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation 2 (North-Holland, Amsterdam, 1978) pp. 71–84. · Zbl 0394.90092
[20] A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastic methods for global optimization,”American Journal of Mathematical and Management Sciences 4 (1984) 7–40. · Zbl 0556.90073
[21] A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastic global optimization methods. part I: clustering methods,”Mathematical Programming 39 (1987a) 27–56. · Zbl 0634.90066 · doi:10.1007/BF02592070
[22] A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastic global optimization methods. part II: multi level methods,”Mathematical Programming 39 (1987b) 57–78. · Zbl 0634.90067 · doi:10.1007/BF02592071
[23] L.E. Scales,Introduction to Non-linear Optimization (Macmillan, London, 1985).
[24] A.A. Törn, ”A search-clustering approach to global optimization,” in: L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimisation 2 (North-Holland, Amsterdam, 1978) pp. 49–62.
[25] Tovey et al. (1989), unpublished manuscript.
[26] D. Vanderbilt and S.G. Louie, ”A Monte Carlo simulated annealing approach to optimization over continuous variables,”Journal of Computational Physics 56 (1984) 259–271. · Zbl 0551.65045 · doi:10.1016/0021-9991(84)90095-0
[27] A.J. Weir,Lebesgue Integration and Measure (Cambridge University Press, Cambridge, 1973). · Zbl 0257.26001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.