×

Parallel radial basis function methods for the global optimization of expensive functions. (English) Zbl 1178.90279

Summary: We introduce a master-worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by H.-M. Gutmann [J. Glob. Optim. 19, No. 3, 201–227 (2001; Zbl 0972.90055)] (Gutmann-RBF) and the RBF method by R. G. Regis and C. A. Shoemaker [J. Glob. Optim. 31, No. 1, 153–171 (2005; Zbl 1274.90511)] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors.

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barr, R. S.; Hickman, B. L., Reporting computational experiments with parallel algorithms: Issues, measures, and experts’ opinions, ORSA Journal on Computing, 5, 1, 2-18 (1993) · Zbl 0775.65029
[2] Björkman, M.; Holmström, K., Global optimization of costly nonconvex functions using radial basis functions, Optimization and Engineering, 1, 4, 373-397 (2000) · Zbl 1035.90061
[3] Booker, A. J.; Dennis, J. E.; Frank, P. D.; Serafini, D. B.; Torczon, V.; Trosset, M. W., A rigorous framework for optimization of expensive functions by surrogates, Structural Optimization, 17, 1, 1-13 (1999)
[4] Box, G. E.P.; Draper, N. R., Empirical Model-Building and Response Surfaces (1987), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York · Zbl 0482.62065
[5] Branin, F. H., Widely convergent methods for finding multiple solutions of simultaneous nonlinear equations, IBM Journal of Research Developments, 16, 504-522 (1972) · Zbl 0271.65034
[6] Brekelmans, R.; Driessen, L.; Hamers, H.; den Hertog, D., Constrained optimization involving expensive function evaluations: A sequential approach, European Journal of Operational Research, 160, 121-138 (2005) · Zbl 1067.90151
[7] Buhmann, M. D., Radial Basis Functions (2003), Cambridge University Press: Cambridge University Press U.K · Zbl 1004.65015
[8] Byrd, R. H.; Dert, C. L.; Rinnooy Kan, A. H.G.; Schnabel, R. B., Concurrent stochastic methods for global optimization, Mathematical Programming, 46, 1-29 (1990) · Zbl 0693.90081
[9] Cantu-Paz, E., Efficient and Accurate Parallel Genetic Algorithms (2000), Kluwer: Kluwer Boston · Zbl 0963.68164
[10] Conn, A. R.; Scheinberg, K.; Toint, Ph. L., Recent progress in unconstrained nonlinear optimization without derivatives, Mathematical Programming, 79, 3, 397-414 (1997) · Zbl 0887.90154
[11] Cressie, N., Statistics for Spatial Data (1993), John Wiley: John Wiley New York
[12] Dixon, L. C.W.; Jha, M., Parallel algorithms for global optimization, Journal of Optimization Theory and Applications, 79, 2, 385-395 (1993) · Zbl 0797.90090
[13] Dixon, L. C.W.; Szegö, G., The global optimization problem: An introduction, (Dixon, L. C.W.; Szegö, G., Towards Global Optimization 2 (1978), North-Holland: North-Holland Amsterdam), 1-15
[14] El-Beltagy, M. A.; Nair, P. B.; Keane, A. J., Metamodelling techniques for evolutionary optimization of computationally expensive problems: Promises and limitations, (Banshaf, W.; Daida, J.; Eiben, A. E.; Garzon, M. H.; Honavar, V.; Jakiela, M.; Smith, R. E., Proceedings of the Genetic and Evolutionary Computation Conference (GECCO99) (1999), Morgan Kaufman), 196-203
[15] Friedman, J., Multivariate adaptive regression splines, Annals of Statistics, 19, 1, 1-141 (1991) · Zbl 0765.62064
[16] Gilmore, P.; Kelley, C. T., An implicit filtering algorithm for optimization of functions with many local minima, SIAM Journal on Optimization, 5, 269-285 (1995) · Zbl 0828.65064
[17] Giunta, A. A.; Balabanov, V.; Haim, D.; Grossman, B.; Mason, W. H.; Watson, L. T.; Haftka, R. T., Aircraft multidisciplinary design optimisation using design of experiments theory and response surface modelling, Aeronautical Journal, 101, 1008, 347-356 (1997)
[18] Gutmann, H. M., A radial basis function method for global optimization, Journal of Global Optimization, 19, 3, 201-227 (2001) · Zbl 0972.90055
[19] Gutmann, H.M., 2001b. Radial basis function methods for global optimization. Ph.D. Thesis, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, UK.; Gutmann, H.M., 2001b. Radial basis function methods for global optimization. Ph.D. Thesis, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, UK. · Zbl 0972.90055
[20] Horst, R.; Pardalos, P. M.; Thoai, N. V., Introduction to Global Optimization (2000), Kluwer: Kluwer Dordrecht · Zbl 0966.90073
[21] Jones, D.R., 1996. Global optimization with response surfaces. Presented at the Fifth SIAM Conference on Optimization, Victoria, Canada.; Jones, D.R., 1996. Global optimization with response surfaces. Presented at the Fifth SIAM Conference on Optimization, Victoria, Canada.
[22] Jones, D. R.; Schonlau, M.; Welch, W. J., Efficient global optimization of expensive black-box functions, Journal of Global Optimization, 13, 4, 455-492 (1998) · Zbl 0917.90270
[23] Kaufman, M.; Balabanov, V.; Burgee, S. L.; Giunta, A. A.; Grossman, B.; Haftka, R. T.; Mason, W. H.; Watson, L. T., Variable-complexity response surface approximations for wing structural weight in HSCT design, Computational Mechanics, 18, 2, 112-126 (1996) · Zbl 0878.73048
[24] Kelley, C. T., Iterative Methods for Optimization (1999), SIAM: SIAM Philadelphia · Zbl 0934.90082
[25] Koehler, J.R., Owen, A.B., 1996. Computer experiments. In: Ghosh, S., Rao, C.R. (Eds.), Handbook of Statistics, vol. 13: Design and Analysis of Computer Experiments, North-Holland, Amsterdam, pp. 261-308.; Koehler, J.R., Owen, A.B., 1996. Computer experiments. In: Ghosh, S., Rao, C.R. (Eds.), Handbook of Statistics, vol. 13: Design and Analysis of Computer Experiments, North-Holland, Amsterdam, pp. 261-308. · Zbl 0919.62089
[26] Lai, T. H.; Sahni, S., Anomalies in parallel branch-and-bound algorithms, Communications of the Association for Computing Machinery, 27, 594-602 (1984) · Zbl 0587.68032
[27] Locatelli, M., Bayesian algorithms for one-dimensional global optimization, Journal of Global Optimization, 10, 57-76 (1997) · Zbl 0871.90087
[28] Marazzi, M.; Nocedal, J., Wedge trust region methods for derivative free optimization, Mathematical Programming, Series A, 91, 289-305 (2002) · Zbl 1049.90134
[29] Minsker, B. S.; Shoemaker, C. A., Dynamic optimal control of in-situ bioremediation of groundwater, Journal of Water Resources Planning and Management, 124, 3, 149-161 (1998)
[30] Myers, R. H.; Montgomery, D. C., Response Surface Methodology: Process and Product Optimization Using Designed Experiments (1995), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York · Zbl 1161.62392
[31] Nocedal, J.; Wright, S. J., Numerical Optimization (1999), Springer: Springer New York · Zbl 0930.65067
[32] Powell, M.J.D., 1992. The theory of radial basis function approximation in 1990. In: Light, W. (Ed.), Advances in Numerical Analysis, vol. 2: Wavelets, Subdivision Algorithms and Radial Basis Functions, Oxford University Press, pp. 105-210.; Powell, M.J.D., 1992. The theory of radial basis function approximation in 1990. In: Light, W. (Ed.), Advances in Numerical Analysis, vol. 2: Wavelets, Subdivision Algorithms and Radial Basis Functions, Oxford University Press, pp. 105-210. · Zbl 0787.65005
[33] Powell, M. J.D., Recent research at Cambridge on radial basis functions, (Müller, M.; Buhmann, M.; Mache, D.; Felten, M., New Developments in Approximation Theory, International Series of Numerical Mathematics, vol. 132 (1999), Birkhauser Verlag: Birkhauser Verlag Basel), 215-232 · Zbl 0958.41501
[34] Powell, M. J.D., UOBYQA: Unconstrained optimization by quadratic approximation, Mathematical Programming, 92, 555-582 (2002) · Zbl 1014.65050
[35] Powell, M. J.D., On trust region methods for unconstrained minimization without derivatives, Mathematical Programming, 97, 605-623 (2003) · Zbl 1106.90382
[36] Regis, R. G.; Shoemaker, C. A., Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization, 31, 153-171 (2005) · Zbl 1274.90511
[37] Regis, R.G., Shoemaker, C.A., 2006. Improved strategies for radial basis function methods for global optimization. Journal of Global Optimization. doi:10.1007/s10898-006-9040-1; Regis, R.G., Shoemaker, C.A., 2006. Improved strategies for radial basis function methods for global optimization. Journal of Global Optimization. doi:10.1007/s10898-006-9040-1 · Zbl 1149.90120
[38] Sacks, J.; Welch, W. J.; Mitchell, T. J.; Wynn, H. P., Design and analysis of computer experiments, Statistical Science, 4, 4, 409-435 (1989) · Zbl 0955.62619
[39] Schnabel, R. B., A view of the limitations, opportunities, and challenges in parallel nonlinear optimization, Parallel Computing, 21, 875-905 (1995) · Zbl 0875.68172
[40] Schoen, F., A wide class of test functions for global optimization, Journal of Global Optimization, 3, 133-137 (1993) · Zbl 0772.90072
[41] Shoemaker, C. A.; Willis, M.; Zhang, W.; Gossett, J., Model analysis of reductive dechlorination with data from Cape Canaveral field site, (Magar, V.; Vogel, T.; Aelion, C.; Leeson, A., Innovative Methods in Support of Bioremediation (2001), Battelle Press: Battelle Press Columbus, OH), 125-131
[42] Sóbester, A.; Leary, S.; Keane, A. J., A parallel updating scheme for approximating and optimizing high fidelity computer simulations, Structural and Multidisciplinary Optimization, 27, 371-383 (2004)
[43] Storn, R.; Price, K., Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11, 341-359 (1997) · Zbl 0888.90135
[44] Taylor, S., Modeling enhanced in-situ biodegradation in groundwater: model response to biological parameter uncertainty, (Proceedings of the 1993 Groundwater Modeling Conference, International Groundwater Modeling Center, 51 (1993), Golden: Golden Colorado), (4-51)-(4-60)
[45] The Mathworks, Inc., 2004. Optimization Toolbox for Use with MATLAB: User’s Guide, Version 3, Natick, MA.; The Mathworks, Inc., 2004. Optimization Toolbox for Use with MATLAB: User’s Guide, Version 3, Natick, MA.
[46] Torczon, V., On the convergence of pattern search algorithms, SIAM Journal on Optimization, 7, 1, 1-25 (1997) · Zbl 0884.65053
[47] Törn, A.; Žilinskas, A., Global Optimization, Lecture Notes in Computer Science, vol. 350 (1989), Springer Verlag: Springer Verlag Berlin · Zbl 0752.90075
[48] Vanden Berghen, F.; Bersini, H., CONDOR, a new parallel, constrained extension of Powell’s UOBYQA algorithm: Experimental results and comparison with the DFO algorithm, Journal of Computational and Applied Mathematics, 181, 157-175 (2005) · Zbl 1072.65088
[49] Ye, K. Q.; Li, W.; Sudjianto, A., Algorithmic construction of optimal symmetric latin hypercube designs, Journal of Statistical Planning and Inference, 90, 145-159 (2000) · Zbl 1109.62329
[50] Yoon, J.-H., 1997. Optimal design of groundwater in situ bioremediation using evolutionary algorithms. Ph.D. Thesis, School of Civil and Environmental Engineering, Cornell University, Ithaca, NY.; Yoon, J.-H., 1997. Optimal design of groundwater in situ bioremediation using evolutionary algorithms. Ph.D. Thesis, School of Civil and Environmental Engineering, Cornell University, Ithaca, NY.
[51] Yoon, J.-H.; Shoemaker, C. A., Comparison of optimization methods for ground-water bioremediation, Journal of Water Resources Planning and Management, 125, 54-63 (1999)
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.