GOSAC: global optimization with surrogate approximation of constraints. (English) Zbl 1373.90118
Summary: We introduce GOSAC, a global optimization algorithm for problems with computationally expensive black-box constraints and computationally cheap objective functions. The variables may be continuous, integer, or mixed-integer. GOSAC uses a two-phase optimization approach. The first phase aims at finding a feasible point by solving a multi-objective optimization problem in which the constraints are minimized simultaneously. The second phase aims at improving the feasible solution. In both phases, we use cubic radial basis function surrogate models to approximate the computationally expensive constraints. We iteratively select sample points by minimizing the computationally cheap objective function subject to the constraint function approximations. We assess GOSAC’s efficiency on computationally cheap test problems with integer, mixed-integer, and continuous variables and two environmental applications. We compare GOSAC to NOMAD and a genetic algorithm (GA). The results of the numerical experiments show that for a given budget of allowed expensive constraint evaluations, GOSAC finds better feasible solutions more efficiently than NOMAD and GA for most benchmark problems and both applications. GOSAC finds feasible solutions with a higher probability than NOMAD and GOSAC.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C30 | Nonlinear programming |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
black-box optimization; computationally expensive constraints; surrogate models; radial basis functionsSoftware:
OPTI; MODFLOW-2000; MISO; SO-I; MT3DMS; MODFLOW; ORBIT; DFLGEN; MLMSRBF; AQUARS; EGO; NOMADReferences:
| [1] | Arnold, J., Srinivasan, R., Muttiah, R., Williams, J.: Large area hydrologic modeling and assessment part 1: model development. J. Am. Water Resour. Assoc. 34, 73-89 (1998) · doi:10.1111/j.1752-1688.1998.tb05961.x |
| [2] | Audet, C., Dennis Jr., J.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(1), 188-217 (2006) · Zbl 1112.90078 · doi:10.1137/040603371 |
| [3] | Audet, C., Dennis Jr., J.: A progressive barrier approach for derivative-free nonlinear programming. SIAM J. Optim. 20(1), 445-472 (2009) · Zbl 1187.90266 · doi:10.1137/070692662 |
| [4] | Basudhar, A., Dribusch, C., Lacaze, S.S.M.: Constrained efficient global optimization with support vector machines. Struct. Multidiscip. Optim. 46(2), 201-221 (2012) · Zbl 1274.90271 · doi:10.1007/s00158-011-0745-5 |
| [5] | Bertsekas, D.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982) · Zbl 0572.90067 |
| [6] | Booker, A., Dennis Jr., J., Frank, P., Serafini, D., Torczon, V., Trosset, M.: A rigorous framework for optimization of expensive functions by surrogates. Struct. Multidisc. Optim. 17, 1-13 (1999) · doi:10.1007/BF01197708 |
| [7] | Conn, A.; Scheinberg, K.; Vicente, L., No article title, Introduction to Derivative-Free Optimization. SIAM., 1, 1-12 (2009) · Zbl 1163.49001 · doi:10.1137/1.9780898718768.ch1 |
| [8] | Currie, J., Wilson, D.: Foundations of Computer-Aided Process Operations, Chap. OPTI: Lowering the Barrier Between Open Source Optimizers and the Industrial MATLAB User. Savannah, Georgia, USA (2012) |
| [9] | Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Progr. Ser. A 91(2), 239-269 (2002) · Zbl 1049.90088 · doi:10.1007/s101070100244 |
| [10] | Forrester, A., Sóbester, A., Keane, A.: Engineering Design via Surrogate Modelling: A Practical Guide. Wiley, London (2008) · doi:10.1002/9780470770801 |
| [11] | Friedman, J.: Multivariate adaptive regression splines. Ann. Stat. 19, 1-141 (1991) · Zbl 0765.62064 · doi:10.1214/aos/1176347963 |
| [12] | Goel, T., Haftka, R.T., Shyy, W., Queipo, N.V.: Ensemble of surrogates. Struct. Multidiscip. Optim. 33, 199-216 (2007) · doi:10.1007/s00158-006-0051-9 |
| [13] | Gramacy, R., Gray, G., Le Digabel, S., Lee, H., Ranjan, P., Wells, G., Wild, S.: Modeling an augmented Lagrangian for blackbox constrained optimization. Technometrics 58(1), 1-11 (2016) · doi:10.1080/00401706.2015.1014065 |
| [14] | Gutmann, H.: A radial basis function method for global optimization. J. Global Optim. 19, 201-227 (2001) · Zbl 0972.90055 · doi:10.1023/A:1011255519438 |
| [15] | Harbaugh, A., McDonald, M.: User’s documentation for MODFLOW-96: an update to the U.S. Geological Survey modular finite-difference ground-water flow model. U.S. Geological Survey Open-File Report 96-485, p. 56 (1996) · Zbl 1305.90305 |
| [16] | Jones, D., Schonlau, M., Welch, W.: Efficient global optimization of expensive black-box functions. J. Global Optim. 13, 455-492 (1998) · Zbl 0917.90270 · doi:10.1023/A:1008306431147 |
| [17] | Le Digabel, S.: Algorithm 909: NOMAD—nonlinear optimization with the MADS algorithm. ACM Trans. Math. Softw. 37, 44 (2011) · Zbl 1365.65172 · doi:10.1145/1916461.1916468 |
| [18] | Le Digabel, S., Wild, S.: A Taxonomy of Constraints in Simulation-Based Optimization (2015). ArXiv:1505.07881 · Zbl 1312.90064 |
| [19] | Liuzzi, G., Lucidi, S., Rinaldi, F.: Derivative-free methods for mixed-integer constrained optimization problems. J. Optim. Theory Appl. 164, 933-965 (2015) · Zbl 1321.90087 · doi:10.1007/s10957-014-0617-4 |
| [20] | Martin, J.D., Simpson, T.W.: Use of kriging models to approximate deterministic computer models. AIAA J. 43, 853-863 (2005) · doi:10.2514/1.8650 |
| [21] | Matheron, G.: Principles of geostatistics. Econ. Geol. 58, 1246-1266 (1963) · doi:10.2113/gsecongeo.58.8.1246 |
| [22] | Moré, J., Wild, S.: Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20(1), 172-191 (2009) · Zbl 1187.90319 · doi:10.1137/080724083 |
| [23] | Müller, J.: MISO: mixed-integer surrogate optimization framework. Optim. Eng. 17(1), 177-203 (2016) · Zbl 1364.90230 · doi:10.1007/s11081-015-9281-2 |
| [24] | Müller, J., Krityakierne, T., Shoemaker, C.: SO-MODS: Optimization for high dimensional computationally expensive multi-modal functions with surrogate search. In: 2014 IEEE Congress on Evolutionary Computation (CEC), Beijing, China (2014) |
| [25] | Müller, J., Piché, R.: Mixture surrogate models based on Dempster-Shafer theory for global optimization problems. J. Global Optim. 51, 79-104 (2011) · Zbl 1230.90155 · doi:10.1007/s10898-010-9620-y |
| [26] | Müller, J., Shoemaker, C.: Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms for computationally expensive black-box global optimization problems. J. Global Optim. 60(2), 123-144 (2014) · Zbl 1312.90064 · doi:10.1007/s10898-014-0184-0 |
| [27] | Müller, J., Shoemaker, C., Piché, R.: SO-I: a surrogate model algorithm for expensive nonlinear integer programming problems including global optimization applications. J. Global Optim. 59(4), 865-889 (2013) · Zbl 1305.90305 · doi:10.1007/s10898-013-0101-y |
| [28] | Müller, J., Shoemaker, C., Piché, R.: SO-MI: a surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems. Comput. Oper. Res. 40, 1383-1400 (2013) · Zbl 1352.90067 · doi:10.1016/j.cor.2012.08.022 |
| [29] | Myers, R., Montgomery, D.: Response Surface Methodology, Process and Product Optimization Using Designed Experiments. Wiley, Hoboken (1995) · Zbl 1161.62392 |
| [30] | Nocedal, J., Wright, S.: Numerical Optimization. Springer, Berlin (2006) · Zbl 1104.65059 |
| [31] | Parr, J.: Improvement criteria for constraint handling and multiobjective optimization. Ph.D. thesis, University of Southampton, University Road, Southampton SO17 1BJ (2013) |
| [32] | Powell, M.: The theory of radial basis function approximation in 1990. Advances in Numerical Analysis, vol. 2: Wavelets, Subdivision Algorithms and Radial Basis Functions. Oxford University Press, Oxford, pp. 105-210 (1992) · Zbl 0787.65005 |
| [33] | Regis, R.: Stochastic radial basis function algorithms for large-scale optimization involving expensive black-box objective and constraint functions. Comput. Oper. Res. 38, 837-853 (2011) · Zbl 1434.90109 · doi:10.1016/j.cor.2010.09.013 |
| [34] | Regis, R., Shoemaker, C.: A stochastic radial basis function method for the global optimization of expensive functions. INFORMS J. Comput. 19, 497-509 (2007) · Zbl 1241.90192 · doi:10.1287/ijoc.1060.0182 |
| [35] | Regis, R., Shoemaker, C.: Combining radial basis function surrogates and dynamic coordinate search in high-dimensional expensive black-box optimization. Eng. Optim. 45, 529-555 (2013) · doi:10.1080/0305215X.2012.687731 |
| [36] | Regis, R., Shoemaker, C.: A quasi-multistart framework for global optimization of expensive functions using response surface models. J. Global Optim. 56(4), 1719-1753 (2013) · Zbl 1275.90068 · doi:10.1007/s10898-012-9940-1 |
| [37] | Talgorn, B., Le Digabel, S., Kokkolaras, M.: Statistical surrogate formulations for simulation-based design optimization. J. Mech. Des. 137(2), MD-14-1128 (2015) · Zbl 1391.90683 |
| [38] | Tolson, B., Asadzadeh, M., Maier, H., Zecchin, A.: Hybrid discrete dynamically dimensioned search (HD-DDS) algorithm for water distribution system design optimization. Water Resour. Res. 45(12), W12416 (2009) · doi:10.1029/2008WR007673 |
| [39] | Tolson, B., Shoemaker, C.: Cannonsville reservoir watershed SWAT2000 model development, calibration and validation. J. Hydrol. 337, 68-86 (2007) · doi:10.1016/j.jhydrol.2007.01.017 |
| [40] | Tolson, B., Shoemaker, C.: Dynamically dimensioned search algorithm for computationally efficient watershed model calibration. Water Resour. Res. W01413(413), 16 (2007) |
| [41] | Viana, F.A.: Multiple Surrogates for Prediction and Optimization. Ph.D. thesis, University of Florida (2011) |
| [42] | Wild, S., Regis, R., Shoemaker, C.: ORBIT: optimization by radial basis function interpolation in trust-regions. SIAM J. Sci. Comput. 30, 3197-3219 (2007) · Zbl 1178.65065 · doi:10.1137/070691814 |
| [43] | Wild, S., Shoemaker, C.: Global convergence of radial basis function trust-region algorithms for derivative-free optimization. SIAM Rev. 55, 349-371 (2013) · Zbl 1270.65028 · doi:10.1137/120902434 |
| [44] | Zheng, C., Wang, P.: MT3DMS: A Modular Three-Dimensional Multispecies Transport Model. US Army Corps of Engineers (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.
