×

zbMATH — the first resource for mathematics

An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer constrained global optimization. (English) Zbl 1400.90226
Summary: Response surface methods based on kriging and radial basis function (RBF) interpolation have been successfully applied to solve expensive, i.e. computationally costly, global black-box nonconvex optimization problems. In this paper we describe extensions of these methods to handle linear, nonlinear, and integer constraints. In particular, algorithms for standard RBF and the new adaptive RBF (ARBF) are described. Note, however, while the objective function may be expensive, we assume that any nonlinear constraints are either inexpensive or are incorporated into the objective function via penalty terms. Test results are presented on standard test problems, both nonconvex problems with linear and nonlinear constraints, and mixed-integer nonlinear problems (MINLP). Solvers in the TOMLAB Optimization Environment (http://tomopt.com/tomlab/) have been compared, specifically the three deterministic derivative-free solvers rbfSolve, ARBFMIP and EGO with three derivative-based mixed-integer nonlinear solvers, OQNLP, MINLPBB and MISQP, as well as the GENO solver implementing a stochastic genetic algorithm. Results show that the deterministic derivative-free methods compare well with the derivative-based ones, but the stochastic genetic algorithm solver is several orders of magnitude too slow for practical use. When the objective function for the test problems is costly to evaluate, the performance of the ARBF algorithm proves to be superior.

MSC:
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C56 Derivative-free methods and methods using generalized derivatives
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
Software:
EGO; MISQP; NLPLIB; OPERA; TOMLAB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bakr MH, Bandler JW, Madsen K, Sondergaard J (2000) Review of the space mapping approach to engineering optimization and modeling. Optim Eng 1(3):241–276 · Zbl 0992.90088 · doi:10.1023/A:1010000106286
[2] Björkman M, Holmström K (2000) Global optimization of costly nonconvex functions using radial basis functions. Optim Eng 1(4):373–397 · Zbl 1035.90061 · doi:10.1023/A:1011584207202
[3] Gutmann H-M (1999) A radial basis function method for global optimization. Technical Report DAMTP 1999/NA22, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England · Zbl 0972.90055
[4] Gutmann H-M (2001a) A radial basis function method for global optimization. J Glob Optim 19:201–227 · Zbl 0972.90055 · doi:10.1023/A:1011255519438
[5] Gutmann H-M (2001b) Radial basis function methods for global optimization. Doctoral thesis, Department of Numerical Analysis, Cambridge University, Cambridge, UK · Zbl 0972.90055
[6] Holmström K (1999) The TOMLAB optimization environment in Matlab. Adv Model Optim 1(1):47–69 · Zbl 1115.90404
[7] Holmström K (2007) An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization. J Glob Optim. doi: 10.1007/s10898-007-9256-8
[8] Holmström K, Edvall MM (2004) The TOMLAB optimization environment. In: Kallrath LGJ (ed) Modeling languages in mathematical optimization. Boston
[9] Jones DR (2002) A taxonomy of global optimization methods based on response surfaces. J Glob Optim 21:345–383 · Zbl 1172.90492 · doi:10.1023/A:1012771025575
[10] Jones DR, Schonlau M, Welch WJ (1998) Efficient global optimization of expensive black-box functions. J Glob Optim 13:455–492 · Zbl 0917.90270 · doi:10.1023/A:1008306431147
[11] McKay M, Beckman R, Conover W (1979) A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21:239–246 · Zbl 0415.62011 · doi:10.2307/1268522
[12] Powell MJD (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, Oxford, pp 105–210
[13] Powell MJD (1999) Recent research at Cambridge on radial basis functions. In: Buhmann MD, Felten M, Mache D, Müller MW (eds) New developments in approximation theory. Birkhäuser, Basel, pp 215–232 · Zbl 0958.41501
[14] Regis RG, Shoemaker CA (2005) Constrained global optimization of expensive black box functions using radial basis functions. J Glob Optim 31(1):153–171 · Zbl 1274.90511 · doi:10.1007/s10898-004-0570-0
[15] Regis RG, Shoemaker CA (2007) Improved strategies for radial basis function methods for global optimization. J Glob Optim 37(1):113–135 · Zbl 1149.90120 · doi:10.1007/s10898-006-9040-1
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.