Stochastic global optimization methods. II: Multi level methods. (English) Zbl 0634.90067

Rinnooy Kan, A. H. G.; Timmer, G. T.

Math. Program. 39, 57-78 (1987).

Summary: [For part I see the preceding review.]
Two stochastic methods for global optimization are described that, with probability 1, find all relevant local minima of the objective function with the smallest possible number of local searches. The computational performance of these methods is examined both analytically and empirically.

MSC:

90C30	Nonlinear programming
65K05	Numerical mathematical programming methods

Keywords:

stochastic methods for global optimization; local minima; computational performance

Citations:

Zbl 0534.90066

References:

[1]	J.L. Bentley, B.W. Weide and A.C. Yao, ”Optimal expected-time algorithms for closest point problems,”ACM Transactions on Mathematical Software 6 (1980) 563–580. · Zbl 0441.68077
[2]	C.G.E. Boender and A.H.G. Rinnooy Kan, ”Bayesian stopping rules for a class of stochastic global optimization methods,” Technical Report, Econometric Institute, Erasmus University Rotterdam (1985). · Zbl 0577.90064
[3]	F.H. Branin and S.K. Hoo, ”A method for finding multiple extrema of a function ofn variables,” in: F.A. Lootsma, ed.,Numerical Methods of Nonlinear Optimization (Academic Press, London, 1972) pp. 231–237. · Zbl 0271.65035
[4]	H. Bremmerman, ”A method of unconstrained global optimization,”Mathematical Biosciences 9 (1970) 1–15. · Zbl 0212.51204
[5]	L. De Biase and F. Frontini, ”A stochastic method for global optimization: its structure and numerical performance” (1978), in: Dixon and Szegö (1978a) pp. 85–102. · Zbl 0396.90082
[6]	L.C.W. Dixon, J. Gomulka and S.E. Hersom, ”Reflections on the global optimization problem,” in: L.C.W. Dixon, ed.,Optimization in Action (Academic Press, London 1976) 398–435.
[7]	L.C.W. Dixon and G.P. Szegö (eds.),Towards Global Optimization 2 (North-Holland, Amsterdam, 1978a). · Zbl 0385.00011
[8]	L.C.W. Dixon and G.P. Szegö, ”The global optimization problem” (1978b) in: Dixon and Szegö (1978a) pp. 1–15.
[9]	A. O. Griewank, ”Generalized descent for global optimization,”Journal of Optimization Techniques and Application 34 (1981) 11–39. · Zbl 0431.49036
[10]	J.T. Postmus, A.H.G. Rinnooy Kan and G.T. Timmer, ”An efficient dynamic selection method,”Communications of the ACM 26 (1983) 878–881.
[11]	W.L. Price, ”A controlled random search procedure for global optimization” (1978), in: Dixon and Szegö (1978a) pp. 71–84. · Zbl 0394.90092
[12]	A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastics Methods for global optimization,”American Journal of Mathematical and Management Sciences 4 (1984) 7–40. · Zbl 0556.90073
[13]	A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastic global optimization methods. Part I: clustering methods,”Mathematical Programming 38 (1987) 27–56 (this issue). · Zbl 0634.90066
[14]	J.A. Snijman and L.P. Fatti, ”A multistart global minimization algorithm with dynamic search trajectories,” Technical Report, University of Pretoria (Republic of South Africa, 1985).
[15]	R.E. Tarjan,Data Structures and Network Algorithms, Siam CBNS/NSF Regional Conference Series in Applied Mathematics (1983). · Zbl 0584.68077
[16]	A.A. Törn, ”Cluster analysis using seed points and density determined hyperspheres with an application to global optimization,” in:Proceeding of the Third International Conference on Pattern Recognition, Coronado, California (1976).
[17]	A.A. Törn, ”A search clustering approach to global optimization” (1978), in: Dixon and Szegö (1978a) pp. 49–62.