×

zbMATH — the first resource for mathematics

Convergence properties of the expected improvement algorithm with fixed mean and covariance functions. (English) Zbl 1419.62200
Summary: This paper deals with the convergence of the expected improvement algorithm, a popular global optimization algorithm based on a Gaussian process model of the function to be optimized. The first result is that under some mild hypotheses on the covariance function \(k\) of the Gaussian process, the expected improvement algorithm produces a dense sequence of evaluation points in the search domain, when the function to be optimized is in the reproducing kernel Hilbert space generated by \(k\). The second result states that the density property also holds for \(P\)-almost all continuous functions, where \(P\) is the (prior) probability distribution induced by the Gaussian process.

MSC:
62L05 Sequential statistical design
62F15 Bayesian inference
90C30 Nonlinear programming
Software:
EGO; SPACE
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aronszajn, N., Theory of reproducing kernels, Trans. amer. math. soc., 68, 337-404, (1950) · Zbl 0037.20701
[2] Bogachev, V.I., Gaussian measures. mathematical surveys and monographs, vol. 62, (1998), American Mathematical Society Providence, RI
[3] Chilès, J.-P.; Delfiner, P., Geostatistics: modeling spatial uncertainty, (1999), Wiley New York · Zbl 0922.62098
[4] Currin, C.; Mitchell, T.; Morris, M.; Ylvisaker, D., Bayesian prediction of deterministic functions, with applications to the design and analysis of computer experiments, J. amer. statist. assoc., 953-963, (1991)
[5] Forrester, A.; Sóbester, A.; Keane, A., Engineering design via surrogate modelling, (2008), Wiley Chichester
[6] Huang, D.; Allen, T.; Notz, W.; Zeng, N., Global optimization of stochastic black-box systems via sequential Kriging meta-models, J. global optim., 34, 441-466, (2006) · Zbl 1098.90097
[7] Jones, D., A taxonomy of global optimization methods based on response surfaces, J. global optim., 21, 345-383, (2001) · Zbl 1172.90492
[8] Jones, D.R.; Schonlau, M.; Welch, W.J., Efficient global optimization of expensive black-box functions, J. global optim., 13, 455-492, (1998) · Zbl 0917.90270
[9] Locatelli, M., Bayesian algorithms for one-dimensional global optimization, J. global optim., 10, 57-76, (1997) · Zbl 0871.90087
[10] Lukic, M.N.; Beder, J.H., Stochastic processes with sample paths in reproducing kernel Hilbert spaces, Trans. amer. math. soc., 353, 10, 3945-3969, (2001) · Zbl 0973.60036
[11] Mockus, J., Bayesian approach to global optimization: theory and applications, (1989), Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 0693.49001
[12] Mockus, J.; Tiesis, V.; Zilinskas, A., The application of Bayesian methods for seeking the extremum, (), 117-129 · Zbl 0394.90090
[13] Molchanov, I.S., Theory of random sets, (2005), Springer London · Zbl 0936.60006
[14] Sacks, J.; Welch, W.J.; Mitchell, T.J.; Wynn, H.P., Design and analysis of computer experiments, Statist. sci., 4, 4, 409-435, (1989) · Zbl 0955.62619
[15] Schonlau, M., 1997. Computer experiments and global optimization. Ph.D. Thesis, University of Waterloo, Waterloo, Ontario, Canada.
[16] Schonlau, M., Welch, W.J., 1996. Global optimization with nonparametric function fitting. In: Proceedings of the ASA, Section on Physical and Engineering Sciences. Amer. Statist. Assoc., pp. 183-186.
[17] Schonlau, M., Welch, W.J., Jones, D.R., 1997. A data analytic approach to Bayesian global optimization. In: Proceedings of the ASA, Section on Physical and Engineering Sciences, Amer. Statist. Assoc., pp. 186-191.
[18] Stein, M.L., Interpolation of spatial data: some theory for Kriging, (1999), Springer New York · Zbl 0924.62100
[19] Steinwart, I., On the influence of the kernel on the consistency of support vector machines, J. Mach. learn. res., 2, 67-93, (2001) · Zbl 1009.68143
[20] Törn, A.; Zilinskas, A., Global optimization, (1989), Springer Berlin · Zbl 0752.90075
[21] Vazquez, E., Bect, J., 2010. Pointwise consistency of the kriging predictor with known mean and covariance functions. In: Giovagnoli, A., Atkinson, A.C., Torsney, B. (Eds.), mODa 9—Advances in Model-Oriented Design and Analysis, Proceedings of Ninth International Workshop in Model-Oriented Design and Analysis, Springer, Bertinoro, Italy · Zbl 1419.62200
[22] Williams, D., Probability with martingales, (1991), Cambridge University Press Cambridge · Zbl 0722.60001
[23] Zilinskas, A., A review of statistical models for global optimization, J. global optim., 2, 145-153, (1992) · Zbl 0768.90071
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.