Sequential stopping rules for the Multistart algorithm in global optimisation.(English)Zbl 0635.90075
A sequential stopping rule is developed for the Multistart algorithm. A statistical model for the values of the observed local maxima of an objective function is introduced in the framework of Bayesian non- parametric statistics. A suitable a-priori distribution is proposed which is general enough and which leads to computationally manageable expressions for the a-posteriori distribution. Sequential stopping rules of the k-step look-ahead kind are then explicitly derived, and their numerical effectiveness compared.
MSC:
| 90C30 | Nonlinear programming |
| 65K05 | Numerical mathematical programming methods |
| 49M37 | Numerical methods based on nonlinear programming |
Keywords:
global optimization;Monte Carlo method;sequential stopping;Multistart algorithm;Bayesian non-parametric statistics;k-step look-aheadCite
Full Text:DOI
References:
| [1] | F. Archetti and F. Schoen, ”A survey on the global optimization problem: general theory and computational approaches,”Annals of Operations Research 1 (1984) 87–110. ·Zbl 0671.90057 ·doi:10.1007/BF01876141 |
| [2] | B. Betrò and C. Vercellis, ”Bayesian nonparametric inference and Monte Carlo optimization,” I.A.M.I. report 84.20 (Milano, 1984). ·Zbl 0632.90066 |
| [3] | B. Betrò, ”The tails of distribution functions from homogeneous processes neutral to the right,” to appear (1984). |
| [4] | C.G.E. Boender and A.H.G. Rinnooy Kan, ”Bayesian, stopping rules for multistart optimization methods,”Mathematical Programming 37 (1987) 59–80. ·Zbl 0626.90079 ·doi:10.1007/BF02591684 |
| [5] | C.G.E. Boender and R. Zieliński, ”A sequential Bayesian approach to estimating the dimension of a multinomial distribution,” preprint n. 256, Institute of Mathematics, Polish Academy of Sciences (Warsaw, 1982). ·Zbl 0663.62090 |
| [6] | M.H. De Groot, Optimal Statistical Decisions (McGraw-Hill, New York, 1970). |
| [7] | L.C.W. Dixon and G.P. Szegö (eds), Towards Global Optimisation 2 (North-Holland, Amsterdam, 1978). ·Zbl 0385.00011 |
| [8] | K. Doksum, ”Tailfree and neutral random probabilities and their posterior distributions,”Annals of Statistics 2 (1974) 183–201. ·Zbl 0277.62034 ·doi:10.1214/aos/1176342662 |
| [9] | T.S. Ferguson, ”A Bayesian analysis of some nonparametric problems,”Annals of Statistics 2 (1973) 209–230. ·Zbl 0255.62037 ·doi:10.1214/aos/1176342360 |
| [10] | T.S. Ferguson and E.G. Phadia, ”Bayesian nonparametric estimation based on censored data,”Annals of Statistics 7 (1979) 163–186. ·Zbl 0401.62031 ·doi:10.1214/aos/1176344562 |
| [11] | J.P. Gilbert and F. Mosteller, ”Recognizing the maximum of a sequence,”Journal of the American Statistical Association 61 (1966) 35–73. ·doi:10.2307/2283044 |
| [12] | R. Zieliński, ”A statistical 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.
