×

zbMATH — the first resource for mathematics

State of the art of “global optimization” methods. (État de l’art des méthodes d’“optimisation globale”.) (French) Zbl 1003.90032
Summary: We present a review of the main “global optimization” methods. The paper comprises one introduction and two parts. In the introduction, we recall some generalities about nonlinear constraint-less optimization and we list some classifications which have been proposed for the global optimization methods.
We then describe, in the first part, various “classical” global global optimization methods, most of which available long before the appearance of Simulated Annealing (a key event in this field). There exists plenty of papers and books dealing with these methods, and studying in particular their convergence properties.
The second part of the paper is devoted to more recent or atypical methods, mostly issued from combinatorial optimization. The three main methods are “metaheuristics”: Simulated annealing (and derived techniques), tabu search and genetic algorithms; we also describe three other less known methods. For these methods, theoretical studies of convergence are less abundant in the literature, and the use of convergence results is by far more limited in practice. However, the fitting of some of these techniques to continuous variables problems gave very promising results; that question is not discussed in detail in the paper, but useful references allowing to deepen the subject are given.

MSC:
90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML
References:
[1] E.H.L. Aarts et P.J.M. Van Laarhoven , Simulated annealing : Theory and applications . D. Reidel Publishing Company ( 1987 ). MR 904050 | Zbl 0643.65028 · Zbl 0643.65028
[2] R.S. Anderssen , Global optimization , édité par R.S. Anderssen, L.S. Jennings et D.M. Ryan. Optimization, Univ. of Queensland Press, St Lucia ( 1972 ) 28 - 48 . MR 423801 | Zbl 0335.90047 · Zbl 0335.90047
[3] J.P. Barthélémy , G. Cohen et A. Lobstein , Complexité algorithmique et problèmes de communication . Masson, Collection CNET-ENST ( 1992 ). MR 1188183 | Zbl 0765.68005 · Zbl 0765.68005
[4] R. Battiti et G. Tecchiolli , The continuous reactive tabu search : Blending Combinatorial Optimization and Stochastic Search for Global Optimization . Ann. Oper. Res. 63 ( 1996 ) 53 - 188 . Zbl 0851.90093 · Zbl 0851.90093
[5] R.W. Becker et G.V. Lago , A global optimization algorithm , dans Proc. of the 8th Allerton Conference on Circuits and Systems Theory. Montecillo, Illinois ( 1970 ) 3 - 12 .
[6] M. Bertocchi et C.D. Odoardo , A stochastic algorithm for global optimization based on threshold accepting technique , dans 11th European Congress on Operational Research EURO XI. Aachen, Germany ( 1991 ).
[7] G. Berthiau , La méthode du recuit simulé pour la conception des circuits électroniques : adaptation et comparaison avec d’autres méthodes d’optimisation . Thèse de Doctorat de l’École Centrale de Paris ( 1994 ).
[8] I.O. Bohachevsky , M.E. Johnson et M.L. Stein , Generalized Simulated Annealing for function optimization . Technometrics 28 ( 1986 ) 209 - 217 . Zbl 0609.65045 · Zbl 0609.65045
[9] F.H. Branin et S.K. Hoo , A method for finding multiple extrema of a function of \(n\) variables , édité par F.A. Lootsma, Numerical methods of nonlinear optimization. Academic Press, London ( 1972 ). MR 395218 | Zbl 0271.65035 · Zbl 0271.65035
[10] S.H. Brooks , A discussion of random methods for seeking maxima . Oper. Res. 6 ( 1958 ) 244 - 251 .
[11] D.G. Brooks et W.A. Verdini , Computational experience with Generalized Simulated Annealing over continuous variables . Amer. J. Math. Management Sci. 8 ( 1988 ) 425 - 449 . MR 1000617 | Zbl 0684.65061 · Zbl 0684.65061
[12] F. Catthoor , H. De Man et J. Vandewalle , SAMURAI : A general and efficient simulated annealing schedule with fully adaptive annealing parameters . Integration, The VLSI Journal 6 ( 1988 ) 147 - 178 .
[13] V. Cerny , Minimization of continuous functions by simulated annealing , Internal Documentation HU-TFT- 84 - 51 . Research Institute for Theoretical Physics, University of Helsinki, Siltavuorenpenger 20c, SF-00170, Helsinki 17, Finland ( 1984 ).
[14] V. Cerny , Thermodynamical approach to the traveling salesman problem : An efficient simulation algorithm . J. Optim. Theory Appl. 45 ( 1985 ) 41 - 51 . MR 778156 | Zbl 0534.90091 · Zbl 0534.90091
[15] I. Charon et O. Hudry , Le bruitage : une méthode prometteuse d’optimisation combinatoire . ENST, Département d’Informatique, Rapport Interne Télécom Paris 92-D- 005 ( 1992 ).
[16] Y. Cherruault et A. Guillez , Une méthode pour la recherche du minimum global d’une fonctionnelle . C. R. Acad. Sci. Paris Sér. I Math. 296 ( 1983 ) 175 - 178 . Zbl 0525.65047 · Zbl 0525.65047
[17] Y. Cherruault , Mathematical modelling in Biomedicine . D. Reidel Publishing Company ( 1986 ). MR 840658
[18] Y. Cherruault , A new method for global optimization (Alienor). Kybernetes 19 ( 1989 ) 19 - 32 . MR 1059596 | Zbl 0701.90083 · Zbl 0701.90083
[19] A. Corana , M. Marchesi , C. Martini et S. Ridella , Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm . ACM Trans. Math. Software 13 ( 1987 ) 262 - 280 . Zbl 0632.65075 · Zbl 0632.65075
[20] P. Courrieu , Un algorithme de recherche distribuée pour l’optimisation difficile . Univ. de Provence, Centre de Recherche en Psychologie Cognitive, Rapport Interne TF- 9101 ( 1991 ).
[21] M. Creutz , Microcanonical Monte-Carlo simulation . Phys. Rev. Lett. 50 ( 1983 ) 1411 - 1414 . MR 701663
[22] D. Cvijovic et J. Klinowski , Taboo search . An approach to the Multiple Minima Problem. Science 667 ( 1995 ) 664 - 666 . MR 1313474 · Zbl 1226.90101
[23] A. Dekkers et E.H.L. Aarts , Global optimization and simulated annealing . Math. Programming 50 ( 1991 ) 367 - 393 . MR 1114238 | Zbl 0753.90060 · Zbl 0753.90060
[24] L. Devroye , Progressive global random search of continuous functions . Math. Programming 15 ( 1978 ) 330 - 342 . MR 514614 | Zbl 0387.90083 · Zbl 0387.90083
[25] D. De Werra et A. Hertz , Tabu search techniques : A tutorial and an application to neural networks . OR Spektrum 11 ( 1989 ) 131 - 141 . MR 1013767 | Zbl 0672.90089 · Zbl 0672.90089
[26] L.C.W. Dixon et G.P. Szegö , Towards global optimization . North Holland, Amsterdam ( 1975 ). Zbl 0305.00008 · Zbl 0305.00008
[27] L.C.W. Dixon et G.P. Szegö , Towards global optimization 2 . North Holland, Amsterdam ( 1978 ). MR 522648 | Zbl 0385.00011 · Zbl 0385.00011
[28] G. Dueck et T. Scheuer , Threshold accepting . IBM Zentrum Heidelberg, Germany ( 1989 ).
[29] G. Dueck , New optimization heuristics, the great deluge and the record-to record travel . J. Comput. Phys. 104 ( 1993 ) 86 - 92 . Zbl 0773.65042 · Zbl 0773.65042
[30] S. Geman et C.R. Hwang , Diffusions for global optimization . SIAM J. Control Optim. 24 ( 1986 ) 1031 - 1043 . MR 854068 | Zbl 0602.60071 · Zbl 0602.60071
[31] M. Gendreau , A. Hertz et G. Laporte , A Tabu Search Algorithm for the Vehicle Routing Problem . Management Sci. 40 ( 1994 ) 1276 - 1290 . Zbl 0822.90053 · Zbl 0822.90053
[32] F. Glover , Future paths for integer programming and links to artificial intelligence . Comput. Oper. Res. 13 ( 1986 ) 533 - 549 . MR 868908 | Zbl 0615.90083 · Zbl 0615.90083
[33] F. Glover et H.J. Greenberg , New approaches for heuristic search : A bilateral linkage with artificial intelligence . Eur. J. Oper. Res. 39 ( 1989 ) 119 - 130 . MR 995734 | Zbl 0658.90079 · Zbl 0658.90079
[34] F. Glover , Tabu search fundamentals and uses , Working paper. Graduate School of Business, Box 419, University of Colorado, Boulder, CO ( 1995 ).
[35] F. Glover et M. Laguna , Tabu search . Kluwer Academic Publishers ( 1997 ). MR 1665424 | Zbl 0930.90083 · Zbl 0930.90083
[36] D.E. Goldberg , Genetic algorithms in search, optimization and machine learning . Addison-Wesley, Reading ( 1989 ). Zbl 0721.68056 · Zbl 0721.68056
[37] L. Hérault , Réseaux de neurones récursifs pour l’optimisation combinatoire ; Application à la théorie des graphes et à la vision par ordinateur , Thèse de Doctorat de l’Institut National Polytechnique de Grenoble. INPG, Grenoble ( 1989 ).
[38] J.H. Holland , Adaptation in natural and artificial systems . Univ. of Michigan Press, Ann Arbor ( 1975 ). MR 441393 | Zbl 0317.68006 · Zbl 0317.68006
[39] R. Horst , P.M. Pardalos , Handbook of Global Optimization . Kluwer Academic Publishers ( 1995 ). MR 1377081 | Zbl 0805.00009 · Zbl 0805.00009
[40] N. Hu , Tabu Search method with random moves for globally optimal design . Int. J. Numer. Meth. Eng. 35 ( 1992 ) 1055 - 1070 .
[41] R.B. Kearfott , Test results for an interval branch and bound algorithm for equality-constrained optimization , édité par C. Floudas et P.M. Pardalos, State of the Art in Global Optimization : Computational Methods and Applications. Kluwer, Dordrecht, Netherlands ( 1996 ) 181 - 200 . MR 1390533 | Zbl 0865.90120 · Zbl 0865.90120
[42] R.B. Kearfott et V. Kreinovich , Applications of Interval Computations . Kluwer, Dordrecht, Netherlands, Applied Optimization ( 1996 ). MR 1386896 | Zbl 0836.00038 · Zbl 0836.00038
[43] S. Kirkpatrick , C.D. Gelatt et M.P. Vecchi , Optimization by simulated annealing , Research Report RC 9355. IBM, Yorktown Heights, NY ( 1982 ). · Zbl 1225.90162
[44] S. Kirkpatrick , C.D. Gelatt et M.P. Vecchi , Optimization by simulated annealing . Science 220 ( 1983 ) 671 - 680 . MR 702485 · Zbl 1225.90162
[45] A.V. Levy et S. Gomez , The tunneling algorithm for the global optimization problem of constrained functions , Technical Report 231. Univ. Nat. Auton. de Mexico ( 1980 ).
[46] A.V. Levy et S. Gomez , The tunneling method applied to global optimization , édité par P.T. Boggs, R.H. Byrd et R.B. Schnanel, Numerical Optimization 1984. SIAM Philadelphia ( 1984 ). MR 802092 | Zbl 0565.65036 · Zbl 0565.65036
[47] A.V. Levy et A. Montalvo , The tunneling algorithm for the global minimization of functions . SIAM J. Sci. Stat. Comp. 6 ( 1985 ) 15 - 29 . MR 773277 | Zbl 0601.65050 · Zbl 0601.65050
[48] M. Lundy et A. Mees , Convergence of an annealing algorithm . Math. Programming 34 ( 1986 ) 111 - 124 . MR 819878 | Zbl 0581.90061 · Zbl 0581.90061
[49] N. Metropolis , A.R. Rosenbluth , M.N. Rosenbluth , A. Teller et E. Teller , Equation of state calculations by fast computing machines . J. Chem. Phys. 21 ( 1953 ).
[50] Z. Michalewicz , Genetic algorithms + Data structures = Evolution Programs . Springer ( 1996 ). MR 1329091 | Zbl 0841.68047 · Zbl 0841.68047
[51] M. Minoux , Programmation mathématique - Théorie et algorithmes . Édition Dunod ( 1983 ). Zbl 0546.90056 · Zbl 0546.90056
[52] R.E. Moore , On computing the range of values of a rational function of \(n\) variables over a bounded region . Computing 16 ( 1976 ) 1 - 15 . MR 421056 | Zbl 0345.65024 · Zbl 0345.65024
[53] R.E. Moore , Methods and applications of interval analysis . SIAM, Philadelphia ( 1979 ). MR 551212 | Zbl 0417.65022 · Zbl 0417.65022
[54] I. Mrad , La méthode du recuit simulé pour la synthèse automatique d’un schéma électrique équivalent . Application à la modélisation de composant et à l’adaptation à large bande. Thèse de Doctorat de l’École Centrale de Paris ( 1997 ).
[55] J.A. Nelder et R. Mead , A simplex method for function minimization . Comput. J. 7 ( 1965 ) 308 - 313 . Zbl 0229.65053 · Zbl 0229.65053
[56] C. Poivey , Méthodes d’optimisation globales pour la C .A.O. de circuits intégrés. Interface avec le simulateur SPICE-PAC. Thèse de Doctorat de l’Université de Clermont-Ferrand ( 1988 ).
[57] C.R. Reeves , Modern Heuristic Techniques for Combinatorial Problems . Mc Graw-Hill, Advanced Topics in Comput. Sci. Ser. ( 1995 ). · Zbl 0942.90500
[58] A.H.G. Rinnooy Kan et G.T. Timmer , Stochastic methods for global optimization . Amer. J. Math. Management Sci. 4 ( 1984 ) 7 - 40 . MR 770759 | Zbl 0556.90073 · Zbl 0556.90073
[59] A.H.G. Rinnooy Kan et G.T. Timmer , Global optimization , Report 8612/A. Erasmus Univ. Rotterdam ( 1986 ). · Zbl 0649.65034
[60] A.H.G. Rinnooy Kan et G.T. Timmer , Stochastic global optimization methods . Part I : Clustering methods. Math. Programming 39 ( 1987 ) 27 - 56 . MR 909007 | Zbl 0634.90066 · Zbl 0634.90066
[61] A.H.G. Rinnooy Kan et G.T. Timmer , Stochastic global optimization methods . Part II : Multi-level methods. Math. Programming 39 ( 1987 ) 57 - 78 . MR 909008 | Zbl 0634.90067 · Zbl 0634.90067
[62] E. Rolland , A Tabu Search Method for Constrained Real-Number Search : Applications to Portfolio Selection , Working Paper. The A. Gary Anderson Graduate School of Management, University of California, Riverside ( 1996 ).
[63] E. Rolland et H. Johnson , Skewness and the Mean-Variance Frontier : A Tabu Search Approach , Working Paper. The A. Gary Anderson Graduate School of Management, University of California, Riverside ( 1996 ).
[64] G. Rudolph , Convergence analysis of canonical genetic algorithms . IEEE Trans. Neural Networks 5 ( 1994 ) 96 - 101 .
[65] K. Schittkowski et W. Hock , Test examples for nonlinear programing codes . Springer-Verlag, Lecture Notes in Econom. and Math. Systems 187 ( 1981 ). MR 611512 | Zbl 0452.90038 · Zbl 0452.90038
[66] K. Schittkowski et W. Hock , More test examples for nonlinear programing codes . Springer-Verlag, Lecture Notes in Econom. and Math. Systems 282 ( 1988 ). MR 611512 | Zbl 0658.90060 · Zbl 0658.90060
[67] P. Siarry , La méthode du recuit simulé : application à la conception de circuits électroniques . Thèse de Doctorat de l’Université Pierre et Marie Curie, Paris 6 ( 1986 ).
[68] P. Siarry et G. Dreyfus , La méthode du recuit simulé : théorie et applications . Éditeur IDSET ( 1988 ).
[69] P. Siarry , La méthode du recuit simulé en électronique : adaptation et accélération . Comparaison avec d’autres méthodes d’optimisation. Application dans d’autres domaines, Rapport d’habilitation à diriger les recherches en sciences. Université de Paris Sud, Centre d’Orsay ( 1994 ).
[70] P. Siarry , G. Berthiau , F. Durbin et J. Haussy , Enhanced Simulated Annealing for globally minimizing functions of many-continuous variables . ACM Trans. Math. Software 23 ( 1997 ) 209 - 228 . MR 1671736 | Zbl 0887.65067 · Zbl 0887.65067
[71] P. Siarry et G. Berthiau , Fitting of Tabu Search to optimize functions of continuous variables . Int. J. Numer. Methods Eng. 40 ( 1997 ) 2449 - 2457 . MR 1454727 | Zbl 0882.65049 · Zbl 0882.65049
[72] E.G. Talbi , A taxonomy of hybrid meta-heuristics , Rapport AS-183 du Laboratoire d’Informatique Fondamentale de Lille. Université des Sciences et Technologies de Lille ( 1998 ).
[73] A. Törn , A search clustering approach to global optimization , édité par L.C.W. Dixon et G.P. Szegö. North Holland, Amsterdam, Towards Global Optimization 2 ( 1978 ). Zbl 0392.90073 · Zbl 0392.90073
[74] A. Törn et A. Zilinskas , Global optimization , édité par G. Goos et J. Hartmanis. Springer Verlag, No. 350 ( 1989 ). MR 988640 | Zbl 0752.90075 · Zbl 0752.90075
[75] D. Vanderbilt et S.G. Louïe , A Monte-Carlo simulated annealing approach to optimization over continuous variables . J. Comput. Phys. 56 ( 1984 ) 259 - 271 . MR 768477 | Zbl 0551.65045 · Zbl 0551.65045
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.