A quasi-multistart framework for global optimization of expensive functions using response surface models. (English) Zbl 1275.90068
Summary: We present the AQUARS (a QUAsi-multistart response surface) framework for finding the global minimum of a computationally expensive black-box function subject to bound constraints. In a traditional multistart approach, the local search method is blind to the trajectories of the previous local searches. Hence, the algorithm might find the same local minima even if the searches are initiated from points that are far apart. In contrast, AQUARS is a novel approach that locates the promising local minima of the objective function by performing local searches near the local minima of a response surface (RS) model of the objective function. It ignores neighborhoods of fully explored local minima of the RS model and it bounces between the best partially explored local minimum and the least explored local minimum of the RS model. We implement two AQUARS algorithms that use a radial basis function model and compare them with alternative global optimization methods on an 8-dimensional watershed model calibration problem and on 18 test problems. The alternatives include EGO, GLOBALm, MLMSRBF [R. G. Regis and C. A. Shoemaker, INFORMS J. Comput. 19, No. 4, 497–509 (2007; Zbl 1241.90192)], CGRBF-Restart [R. G. Regis and C. A. Shoemaker, J. Glob. Optim. 37, No. 1, 113–135 (2007; Zbl 1149.90120)], and multilevel single linkage (MLSL) coupled with two types of local solvers: SQP and mesh adaptive direct search (MADS) combined with kriging. The results show that the AQUARS methods generally use fewer function evaluations to identify the global minimum or to reach a target value compared to the alternatives. In particular, they are much better than EGO and MLSL coupled to MADS with kriging on the watershed calibration problem and on 15 of the test problems.
MSC:
| 90C26 | Nonconvex programming, global optimization |
Keywords:
global optimization; multistart; response surface model; surrogate model; function approximation; radial basis function; expensive function; black-box function; watershed calibrationSoftware:
Boosters; AQUARS; Optimization Toolbox; MLMSRBF; EGO; Matlab; UOBYQA; SURROGATES; NOMADm; DACE; NEWUOA; Scatter SearchReferences:
| [1] | Abramson, M.A.: NOMADm Version 4.6 User’s Guide. Unpublished manuscript (2007) · Zbl 1180.90253 |
| [2] | Abramson M.A., Audet C.: Convergence of mesh adaptive direct search to second-order stationary points. SIAM J. Optim. 17(2), 606-619 (2006) · Zbl 1174.90877 · doi:10.1137/050638382 |
| [3] | Aleman D.M., Romeijn H.E., Dempsey J.F.: A response surface approach to beam orientation optimization in intensity modulated radiation therapy treatment planning. INFORMS J. Comput. 21, 62-76 (2009) · doi:10.1287/ijoc.1080.0279 |
| [4] | Audet C., Dennis J.E. Jr.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(2), 188-217 (2006) · Zbl 1112.90078 · doi:10.1137/040603371 |
| [5] | Björkman M., Holmström K.: Global optimization of costly nonconvex functions using radial basis functions. Optim. Eng. 1, 373-397 (2000) · Zbl 1035.90061 · doi:10.1023/A:1011584207202 |
| [6] | Boender C.G.E., Rinnooy Kan A.H.G., Timmer G.T., Stougie L.: A stochastic method for global optimization. Math. Program. 22, 125-140 (1982) · Zbl 0525.90076 · doi:10.1007/BF01581033 |
| [7] | 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. Struct. Optim. 17(1), 1-13 (1999) · doi:10.1007/BF01197708 |
| [8] | Buhmann M.D.: Radial Basis Functions. Cambridge University Press, Cambridge (2003) · Zbl 1038.41001 · doi:10.1017/CBO9780511543241 |
| [9] | Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS-SIAM Series on Optimization (2000) · Zbl 0958.65071 |
| [10] | Conn A.R., Scheinberg K., Vicente L.N.: Introduction to Derivative-Free Optimization. SIAM, Philadelphia (2009) · Zbl 1163.49001 · doi:10.1137/1.9780898718768 |
| [11] | Cressie N.: Statistics for Spatial Data. Wiley, New York (1993) · Zbl 0799.62002 |
| [12] | Csendes T.: Nonlinear parameter estimation by global optimization—efficiency and reliability. Acta Cybern. 8, 361-370 (1988) · Zbl 0654.90074 |
| [13] | Dixon, L. C.W.; Szegö, G.; Dixon, L. C.W. (ed.); Szegö, G. (ed.), The global optimization problem: an introduction, 1-15 (1978), Amsterdam · Zbl 0385.00011 |
| [14] | Egea J.A., Vazquez E., Banga J.R., Marti R.: Improved scatter search for the global optimization of computationally expensive dynamic models. J. Global Optim. 43(2-3), 175-190 (2009) · Zbl 1179.90307 · doi:10.1007/s10898-007-9172-y |
| [15] | Forrester A.I.J., Sobester A., Keane A.J.: Engineering Design via Surrogate Modelling a Practical Guide. Wiley, New York (2008) · doi:10.1002/9780470770801 |
| [16] | 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. Aeronaut. J. 101(1008), 347-356 (1997) |
| [17] | Glover, F.: A template for scatter search and path relinking. In: Hao, J.-K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.) Artificial Evolution, Lecture Notes in Computer Science, vol. 1363, pp. 13-54. Springer, Berlin (1998) |
| [18] | Gutmann H.-M.: A radial basis function method for global optimization. J. Global Optim. 19(3), 201-227 (2001) · Zbl 0972.90055 · doi:10.1023/A:1011255519438 |
| [19] | Holmström K.: An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization. J. Global Optim. 41(3), 447-464 (2008) · Zbl 1152.90609 · doi:10.1007/s10898-007-9256-8 |
| [20] | Huang D., Allen T.T., Notz W.I., Zeng N.: Global optimization of stochastic black-box systems via sequential kriging meta-models. J. Global Optim. 34(3), 441-466 (2006) · Zbl 1098.90097 · doi:10.1007/s10898-005-2454-3 |
| [21] | Jakobsson S., Patriksson M., Rudholm J., Wojciechowski A.: A method for simulation based optimization using radial basis functions. Optim. Eng. 11(4), 501-532 (2009) · Zbl 1243.65068 · doi:10.1007/s11081-009-9087-1 |
| [22] | Jones D.R., Schonlau M., Welch W.J.: Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4), 455-492 (1998) · Zbl 0917.90270 · doi:10.1023/A:1008306431147 |
| [23] | Kleijnen J.P.C.: Design and Analysis of Simulation Experiments. Springer, Berlin (2008) · Zbl 1269.62067 |
| [24] | Kleijnen J.P.C.: Kriging metamodeling in simulation: a review. Eur. J. Oper. Res. 192(3), 707-716 (2009) · Zbl 1157.90544 · doi:10.1016/j.ejor.2007.10.013 |
| [25] | Kolda T.G., Lewis R.M., Torczon V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45(3), 385-482 (2003) · Zbl 1059.90146 · doi:10.1137/S003614450242889 |
| [26] | Laguna M., Marti R.: Scatter Search: Methodology and Implementations in C. Kluwer, Boston (2003) · Zbl 1055.68103 · doi:10.1007/978-1-4615-0337-8 |
| [27] | Lasdon L., Duarte A., Glover F., Laguna M., Marti R.: Adaptive memory programming for constrained global optimization. Comput. Oper. Res. 37(8), 1500-1509 (2010) · Zbl 1183.90459 · doi:10.1016/j.cor.2009.11.006 |
| [28] | Lophaven, S.N., Nielsen, H.B., Søndergaard, J.: DACE: A Matlab Kriging Toolbox, Version 2.0. Technical Report IMM-TR-2002-12, Informatics and Mathematical Modelling, Technical University of Denmark, DK-2800 Kgs. Lyngby(2002) · Zbl 1152.90609 |
| [29] | Marsden A.L., Wang M., Dennis J.E. Jr., Moin P.: Optimal aeroacoustic shape design using the surrogate management framework. Optim. Eng. 5(2), 235-262 (2004) · Zbl 1116.90417 · doi:10.1023/B:OPTE.0000033376.89159.65 |
| [30] | Myers R.H., Montgomery D.C.: Response Surface Methodology: Process and Product Optimization Using Designed Experiments. Wiley, New York (1995) · Zbl 1161.62392 |
| [31] | Nocedal J., Wright S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067 · doi:10.1007/b98874 |
| [32] | Oeuvray R., Bierlaire M.: BOOSTERS: a derivative-free algorithm based on radial basis functions. Int. J. Model. Simul. 29(1), 26-36 (2009) |
| [33] | Oeuvray, R.: Trust-Region Methods Based on Radial Basis Functions With Application To Biomedical Imaging. Ph.D. thesis, École Polytechnique Fédérale de Lausanne (EPFL), Lausanne (2005) |
| [34] | Powell, M. J.D.; Light, W. (ed.), The theory of radial basis function approximation in 1990, 105-210 (1992), Oxford · Zbl 0787.65005 |
| [35] | Powell M.J.D.: UOBYQA: unconstrained optimization by quadratic approximation. Math. Program. 92, 555-582 (2002) · Zbl 1014.65050 · doi:10.1007/s101070100290 |
| [36] | Powell, M. J.D.; Di Pillo, G. (ed.); Roma, M. (ed.), The NEWUOA software for unconstrained optimization without derivatives, 255-297 (2006), USA · Zbl 1108.90005 · doi:10.1007/0-387-30065-1_16 |
| [37] | Regis R.G., Shoemaker C.A.: A stochastic radial basis function method for the global optimization of expensive functions. INFORMS J. Comput. 19(4), 497-509 (2007) · Zbl 1241.90192 · doi:10.1287/ijoc.1060.0182 |
| [38] | Regis R.G., Shoemaker C.A.: Improved strategies for radial basis function methods for global optimization. J. Global Optim. 37(1), 113-135 (2007) · Zbl 1149.90120 · doi:10.1007/s10898-006-9040-1 |
| [39] | Rinnooy Kan A.H.G., Timmer G.T.: Stochastic global optimization methods, part II: multi level methods. Math. Program. 39, 57-78 (1987) · Zbl 0634.90067 · doi:10.1007/BF02592071 |
| [40] | Sacks J., Welch W.J., Mitchell T.J., Wynn H.P.: Design and analysis of computer experiments. Stat. Sci. 4, 409-435 (1989) · Zbl 0955.62619 · doi:10.1214/ss/1177012413 |
| [41] | Schoen F.: A wide class of test functions for global optimization. J. Global Optim. 3, 133-137 (1993) · Zbl 0772.90072 · doi:10.1007/BF01096734 |
| [42] | Sendin J.O.H, Banga J.R., Csendes T.: Extensions of a multistart clustering algorithm for constrained global optimization problems. Ind. Eng. Chem. Res. 48(6), 3014-3023 (2009) · doi:10.1021/ie800319m |
| [43] | Shoemaker C.A., Regis R.G., Fleming R.C.: Watershed calibration using multistart local optimization and evolutionary optimization with radial basis function approximation. Hydrol. Sci. J. 52(3), 450-465 (2007) · doi:10.1623/hysj.52.3.450 |
| [44] | Simpson T.W., Mauery T.M., Korte J.J., Mistree F.: Kriging metamodels for global approximation in simulation-based multidisciplinary design optimization. AIAA J. 39(12), 2233-2241 (2001) · doi:10.2514/2.1234 |
| [45] | The Mathworks, Inc.: Matlab Optimization Toolbox: User’s Guide, Version 4. Natick, MA (2009) · Zbl 1174.90877 |
| [46] | Ugray Z., Lasdon L., Plummer J., Glover F., Kelley J., Marti R.: Scatter search and local NLP solvers: a multistart framework for global optimization. INFORMS J. Comput. 19(3), 328-340 (2007) · Zbl 1241.90093 · doi:10.1287/ijoc.1060.0175 |
| [47] | Viana, F.A.C.: SURROGATES Toolbox User’s Guide, Version 2.1, http://sites.google.com/site/felipeacviana/surrogatestoolbox (2010) |
| [48] | Villemonteix J., Vazquez E., Walter E.: An informational approach to the global optimization of expensive-to-evaluate functions. J. Global Optim. 44(4), 509-534 (2009) · Zbl 1180.90253 · doi:10.1007/s10898-008-9354-2 |
| [49] | Ye K.Q., Li W., Sudjianto A.: Algorithmic construction of optimal symmetric latin hypercube designs. J. Stat. Plan. Inference 90, 145-159 (2000) · Zbl 1109.62329 · doi:10.1016/S0378-3758(00)00105-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. 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.
