Abstract
Several different approaches have been suggested for the numerical solution of the global optimization problem: space covering methods, trajectory methods, random sampling, random search and methods based on a stochastic model of the objective function are considered in this paper and their relative computational effectiveness is discussed. A closer analysis is performed of random sampling methods along with cluster analysis of sampled data and of Bayesian nonparametric stopping rules.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R.L. Anderson, Recent advances in finding best operating conditions, J. Amer. Stat. Assoc. 48(1953)80.
R.S. Anderssen, Global optimization, in: Anderssen, Jennings and Ryan, Optimization (University of Queensland Press, 1972) p. 26.
R.S. Anderssen and P. Bloomfield, Properties of the random search in global optimization, J.O.T.A. 16, no. 5/6 (1975)91.
F. Archetti, Evaluation of random gradient techniques for unconstrained optimization, Calcolo, Vol. XII, f.1 (1975)83.
F. Archetti, B. Betró and S. Steffé, A theoretical framework for global optimization via random sampling, Quaderni del Dipartimento di Ricerca Operativa e Scienze Statistiche A-25 (Universitá di Pisa, 1975).
F. Archetti and B. Betró, On the effectiveness of uniform random sampling in global optimization problems, Quaderni del Dipartimento di Ricerca Operativa e Scienze Statistiche A-32 (Universitá di Pisa, 1977).
F. Archetti and B. Betró, A priori analysis of determinisitic strategies for global optimization problems, in: Towards Global Optimization 2, ed. L.C.W. Dixon and G.P. Szego (North-Holland, Amsterdam, 1978) p. 31.
F. Archetti, A stopping criterion for global optimization algorithms, Quaderni del Dipartimento di Ricerca Operativa e Scienze Statistiche A-61 (Universitá di Pisa, 1979).
F. Archetti and B. Betró, A probabilistic algorithm for global optimization, Calcolo Vol. XVI, III(1979)335.
F. Archetti and B. Betró, Stochastic models and optimization, Bollettino della Unione Matematica Italiana 5, 17-A (1980) p. 295.
F. Archetti and F. Schoen, Asynchronous parallel search in global optimization problems, in: Proc. X IFIP Conf. on System Modeling and Optimization, Lecture Notes on Control and Information Sciences, Vol. 38 (Springer-Verlag, 1982) p. 500.
B. Betró, A Bayesian nonparametric approach to global optimization, Methods of operations research, ed. P. S. Stähly (Athenäum Verlag, 1983) p. 45, 47.
B. Betró, Bayesian testing of nonparametric hypotheses and its application to global optimization problems, J.O.T.A. 42(1984)31.
B. Betró and R. Rotondi, A Bayesian algorithm for global optimization, Oper. Res. 1(1984)111.
C.G.E. Boender, A.H.G. Rinnooy Kan, L. Stougie and G.T. Timmer, A stochastic method for global optimization, Math. Progr. 22(1982)125.
C.G.E. Boender and A.H.G. Rinnooy Kan, Optimal stopping rules for random sampling global optimization procedures, contributed talk at I.I.S.O. (1982).
F.H. Branin, jr. and S.K. Hoo, A method for finding multiple extrema of a function, ofN variables, in: Numerical Methods of Nonlinear Optimization (Academic Press, 1982).
F.H. Branin, jr., Widely convergent method for finding multiple solutions of simultaneous nonlinear equations, IBM J. Res. Develop. (September, 1972) p. 504.
P. Chiappa, G. Remotti and R. Rotondi, A clustering technique based onkth nearest neightbour distribution (1983), private communication.
D. Clough, An asymptotic extreme value sampling theory for estimation of global maximum, Can. Oper. Res. Soc. J. (1969)102.
L. De Haan, Estimation of the minimum of a function using order statistics, Report 7902/S (Econometric Institute, Erasmus University, Rotterdam, 1979).
Yu. M. Ermoliev, On the stochastic quasi-gradient method and stochastic quasi-Feyer sequences, Kibernetika 3(1969)18.
Yu. M. Ermoliev, Stochastic quasi-gradient methods and their application in systems optimization, Working Paper WP-81-2, I.I.A.S.A. (1981).
B. Everitt, Cluster Analysis (Heinemann, 1974).
Y.G. Evtushenko, Numerical methods for finding global extrema (Case of a non-uniform mesh), Zh. Vychisl. Mat. Fiz. 16,6(1971)1390.
J. Gomulka, Remarks on Branin's method for solving nonlinear equations, in: Towards Global Optimization, ed. L.C.W. Dixon and G.P. Szegö (North-Holland, Amsterdam, 1975) p. 96.
J. Gomulka, Two implementations of Branin's method: numerical experience, in: Towards Global Optimization 2, ed. L.C.W. Dixon and G.P. Szegö (North-Holland, Amsterdam, 1978) p. 151.
A.O. Griewank, Generalized descent for global optimization, J.O.T.A. 34, n.1 (1981)11.
J.W. Hardy, An implemented extension of Branin's method, in: Towards Global Optimization, ed. L.C.W. Dixon and G.P. Szegö (North-Holland, Amsterdam, 1975) p. 117.
J. Hartigan, Clustering Algorithms (Wiley, 1975).
M.J. Kushner, A new method for locating the maximum point of an arbitrary multipeak curve in presence of noise, J. Basic Engineering (1964) 97.
J.J. McKeown, Aspects of parallel computation in numerical optimization, in: Numerical Techniques for Stochastic Systems, ed. F. Archetti and M. Cugiani (North-Holland, Amsterdam, 1980) p. 297.
J. Mockus, On a method for allocation of observations for the solution of extremal problems, USSR Comp. Mat. and Mat. Fiz. 2(1964)103.
J. Mockus, V. Tiesis and A. Žilinskas, The application of Bayesian method for seeking the extremum, in: Towards Global Optimization 2, ed. L.C.W. Dixon and G.P. Szegö (North-Holland, Amsterdam, 1978) p. 117.
J. Mockus, The simple Bayesian algorithm for multidimensional Bayesian optimization, in: Numerical Techniques for Stochastic Systems, ed. F. Archetti and M. Cugiani (North-Holland, Amsterdam, 1980) p. 369.
J. Mockus, The Bayesian approach to global optimization, in: Proc. 10th IFIP Conf. on System Modeling and Optimization (Springer, 1981) p. 473.
K.D. Patel, Parallel computations and numerical optimization. Oper. Res. 1(1984)135.
J. Pinter, Sztochastikus modszerek optimalizalasi feladatok megoldasara, Alkalmazott Matematikai Lapok 7(1981)217.
L.A. Rastrigin, The convergence of the random search method in the extremal control of a many parameter system, Automat. Remote Control 24(1963)216.
R. Rotondi, Valutazione numerica di un algoritmo probabilistico di ottimizzazione globale, Rendiconti dell'Istituto Lombardo di Scienze e Lettere (1983) to appear.
R.Y. Rubinstein, Simulation and the Monte Carlo method (Wiley, 1891).
R.Y. Rubinstein and G. Samorodnitsky, Efficiency of the random search method, Math. and Comp. in Sim. 24(1982)257.
F. Schoen, On a sequential search strategy in global optimization, problems, Calcolo III (1982)321.
M.A. Schumer and K. Steiglitz, Adaptive step size random search. IEEE Transactions AC, Vol. AC-13(1968)351.
B.O. Shubert, A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9:3(1972)379.
F.J. Solis and R.B. Wets. Minimization by random search techniques, Math. Oper. Res. no. 1 (1981)19.
A.G. Sukharev, Optimal strategies for the search of an extremum. Zh. Vychisl. Mat. Fiz. 11, no.4 (1971)910.
A.G. Sukharev, Best sequential strategies for finding an extrenum. Zh. Vyschisl. Mat. Fiz. 18, no. 1 (1972)35.
A. Torn, Cluster analysis using seed points and density-determined hyperspheres with an application to global optimization, in: Proc. 3rd Int. Joint Conf on Pattern Recognition (1976) p. 394.
A. Torn, Probabilistic global optimization, a cluster analysis approach, in: Proc. 2nd European Congress on Operations Research (North-Holland, Amsterdam, 1976) p. 521.
G. Treccani, A new strategy for global minimization, in: Towards Global Optimization, ed. L.C.W. Dixon and G.P. Szegö (North-Holland, Amsterdam, 1975) p. 143.
G. Treccani, On the convergence of Branin's method: a counter example, in: Towards Global Optimization, ed. L.C.W. Dixon and G.P. Szegö (North-Holland, Amsterdam, 1975) p. 107.
G. Treccani, A global descent optimization strategy, in: Towards Global Optimization 2, ed. L.C.W. Dixon and G.P. Szegö (North-Holland, Amsterdam, 1978) p. 165.
A. Velasco Levy and S. Gomez, The tunneling algorithm for the global optimization of constrained functions, IIMAS-UNAM Tech. Rep. no. 231 (1980).
A. Velsco Levy and A. Montalvo, A modification to the tunneling algorithm for finding the global minima of an arbitrary one-dimensional scalar function, IIMAS-UNAM Tech. Rep. no. 240 (1980).
R. Zielinski, A statistical estimate of the structure of multi-extremal problems, Math. Progr. 21(1981)348.
A. Zilinskas, Axiomatic approach to statistical models and their use in multimodal optimization theory, Math. Progr., 22(1982).
F. Zirilli. The use of stochastic differential equations in global optimization (1982), private communication.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Archetti, F., Schoen, F. A survey on the global optimization problem: General theory and computational approaches. Ann Oper Res 1, 87–110 (1984). https://doi.org/10.1007/BF01876141
Issue Date:
DOI: https://doi.org/10.1007/BF01876141