Stochastic global optimization methods. I: Clustering methods.(English)Zbl 0634.90066
Summary: In this stochastic approach to global optimization, clustering techniques are applied to identify local minima of a real valued objective function that are potentially global. Three different methods of this type are described; their accuracy and efficiency are analyzed in detail.
Keywords:
sampling methods;stochastic approach to global optimization;clustering techniques;local minima;potentially globalCitations:
Zbl 0534.90067Cite
References:
| [1] | R.S. Anderssen, ”Global optimization,” in: R.S. Anderssen, L.S. Jennings and D.M. Ryan, eds.,Optimization (University of Queensland Press, 1972) pp. 1–15. ·Zbl 0335.90047 |
| [2] | R.S. Anderssen and P. Bloomfield, ”Properties of the random search in global optimization,”Journal of Optimization Theory and Applications 16 (1975) 383–398. ·Zbl 0294.90037 ·doi:10.1007/BF00933849 |
| [3] | F. Archetti and B. Betro, ”A priori analysis of deterministic strategies for global optimization,” in: Dixon and Szegö (1978a) pp. 31–48. ·Zbl 0404.90082 |
| [4] | F. Archetti and B. Betro, ”On the effectiveness of uniform random sampling in global optimization problems,” Technical Report, University of Pisa (Pisa, Italy, 1978b). ·Zbl 0404.90082 |
| [5] | F. Archetti and F. Frontini, ”The application of a global optimization method to some technological problems,” (1978), in: Dixon and Szegö (1978a) pp. 179–188. ·Zbl 0387.90108 |
| [6] | R.R. Bahadur, ”A note on quantiles in large samples,”Annals of Mathematical Statistics 37 (1966) 577–580. ·Zbl 0147.18805 ·doi:10.1214/aoms/1177699450 |
| [7] | R.W. Becker and G.V. Lago, ”A global optimization algorithm,” in:Proceedings of the 8th Allerton Conference on Circuits and Systems Theory (1970). |
| [8] | B. Betro, ”Bayesian testing of nonparametric hypotheses and its application to global optimization,” Technical Report, CNR-IAMI (Italy, 1981). ·Zbl 0506.60014 |
| [9] | C.G.E. Boender, A.H.G. Rinnooy Kan, L. Stougie and G.T. Timmer, ”Global optimization: A stochastic approach,” in: F. Archetti and M. Cugiani, eds.,Numerical Techniques for Stochastic Systems (North-Holland, Amsterdam, 1980) pp. 387–394. ·Zbl 0458.90056 |
| [10] | C.G.E. Boender, A.H.G. Rinnooy Kan, L. Stougie and G.T. Timmer, ”A stochastic method for global optimization,”Mathematical Programming 22 (1982) 125–140. ·Zbl 0525.90076 ·doi:10.1007/BF01581033 |
| [11] | C.G.E. Boender and A.H.G. Rinnooy Kan, ”A Bayesian analysis of the number of cells of a multinomial distribution,”The Statistician 32 (1983) 240–248. ·doi:10.2307/2987621 |
| [12] | C.G.E. Boender, ”The generalized multinomial distribution: A Bayesian analysis and application,” Ph.D. Dissertation, Erasmus Universiteit Rotterdam (Centrum voor Wiskunde en Informatica, Amsterdam, 1984). |
| [13] | 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 |
| [14] | C.G.E. Boender, A.H.G. Rinnooy Kan and G.T. Timmer, ”A stochastic approach to global optimization,” in: K. Schittkowski, ed.,Computational Mathematical Programming (NATO ASI Series, Vol. F15, Springer-Verlag, Berlin, 1985) pp. 291–308. ·Zbl 0577.90064 |
| [15] | S.H. Brooks, ”A discussion of random methods for seeking maxima,”Operations Research 6 (1958) 244–251. ·doi:10.1287/opre.6.2.244 |
| [16] | K. L. Chung,A Course in Probability Theory (Academic Press, London, 1974). ·Zbl 0345.60003 |
| [17] | L. Devroye, ”Progressive global random search of continuous functions,”Mathematical Programming 15 (1978) 330–342. ·Zbl 0387.90083 ·doi:10.1007/BF01609037 |
| [18] | L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimization (North-Holland, Amsterdam, 1975). ·Zbl 0309.90052 |
| [19] | L.C.W. Dixon, J. Gomulka and G.P. Szegö, ”Towards global optimization,” in: Dixon and Szegö (1975) pp. 29–54. ·Zbl 0309.90052 |
| [20] | L.C.W. Dixon and G.P. Szegö, eds.,Towards Global Optimization 2 (North-Holland, Amsterdam, 1978a). ·Zbl 0385.00011 |
| [21] | L.C.W. Dixon and G.P. Szegö, ”The global optimization problem” (1978b), in: Dixon and Szegö (1978a) pp. 1–15. |
| [22] | P. Erdös and J. Spencer,Probabilistic Methods in Combinatorics (Academic Press, London, 1979). |
| [23] | J.K. Hartman, ”Some experiments in global optimization,”Naval Research Logistics Quarterly 20 (1973) 569–576. ·Zbl 0265.90048 ·doi:10.1002/nav.3800200316 |
| [24] | V.V. Ivanov, ”On optimal algorithms of minimization in the class of functions with the Lipschitz condition,”Information Processing 2 (1972) 1324–1327. |
| [25] | E. Parzen, ”On estimation of a probability density function and mode,”Annals of Mathematical Statistics 33 (1962) 1065–1076. ·Zbl 0116.11302 ·doi:10.1214/aoms/1177704472 |
| [26] | 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 |
| [27] | A.H.G. Rinnooy Kan and G.T. Timmer, ”Stochastic global optimization methods. Part II: Multi level methods,”Mathematical Programming 38 (1987) 57–78 (this issue). ·Zbl 0634.90067 |
| [28] | R.Y. Rubinstein,Simulation and the Monte Carlo Method (John Wiley & Sons, New York, 1981). ·Zbl 0529.68076 |
| [29] | A.J. Ruygrok, ”Mode Analysis in globaal optimaliseren,” Master Thesis, Erasmus University Rotterdam (in Dutch) (1982). |
| [30] | 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). |
| [31] | I.M. Sobol, ”On an estimate of the accuracy of a simple multidimensional search,”Soviet Math. Dokl. 26 (1982) 398–401. ·Zbl 0534.41013 |
| [32] | F.J. Solis and R.J.E. Wets, ”Minimization by random search techniques,”Mathematics of Operations Research 6 (1981) 19–30. ·Zbl 0502.90070 ·doi:10.1287/moor.6.1.19 |
| [33] | L. Spircu, ”Cluster analysis in global optimization,”Economic Computation and Economic Cybernetic Studies and Research 13 (1979) 43–50. ·Zbl 0437.90077 |
| [34] | A.G. Sukharev, ”Optimal strategies of the search for an extremum,”Computational Mathematics and Mathematical Physics 11 (1971) 119–137. ·Zbl 0255.90059 ·doi:10.1016/0041-5553(71)90008-5 |
| [35] | 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)pp. 394–398. |
| [36] | A.A. Törn, ”A search clustering approach to global optimization” (1978), in: Dixon and Szegö (1978a) pp. 49–62. |
| [37] | D. Wishart, ”Mode Analysis: A generalization of nearest neighbour which reduces chaining effects,” in: A.J. Cole, ed.,Numerical Taxonomy, (Academic Press, New York, 1969). |
| [38] | P. Wolfe, ”Convergence conditions for ascent methods,”Siam Review 11 (1969) 226–235. ·Zbl 0177.20603 ·doi:10.1137/1011036 |
| [39] | P. Wolfe, ”Convergence conditions for ascent methods II: some corrections,”Siam Review 13 (1971) 185–188. ·Zbl 0216.26901 ·doi:10.1137/1013035 |
| [40] | R. Zielinski, ”A stochastic estimate of the structure of multi-extremal problems,”Mathematical Programming 21 (1981) 348–356. ·Zbl 0476.90086 ·doi:10.1007/BF01584254 |
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.
