×

zbMATH — the first resource for mathematics

Surrogate optimization of computationally expensive black-box problems with hidden constraints. (English) Zbl 07283450
Summary: We introduce the algorithm SHEBO (surrogate optimization of problems with hidden constraints and expensive black-box objectives), an efficient optimization algorithm that employs surrogate models to solve computationally expensive black-box simulation optimization problems that have hidden constraints. Hidden constraints are encountered when the objective function evaluation does not return a value for a parameter vector. These constraints are often encountered in optimization problems in which the objective function is computed by a black-box simulation code. SHEBO uses a combination of local and global search strategies together with an evaluability prediction function and a dynamically adjusted evaluability threshold to iteratively select new sample points. We compare the performance of our algorithm with that of the mesh-based algorithms mesh adaptive direct search (MADS, NOMAD [nonlinear optimization by mesh adaptive direct search] implementation) and implicit filtering and SNOBFIT (stable noisy optimization by branch and fit), which assigns artificial function values to points that violate the hidden constraints. Our numerical experiments for a large set of test problems with 2–30 dimensions and a 31-dimensional real-world application problem arising in combustion simulation show that SHEBO is an efficient solver that outperforms the other methods for many test problems.
Supplemental material is available at https://doi.org/10.1287/ijoc.2018.0864.
MSC:
90C Mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramson M, Audet C, Dennis J Jr, Le Digabel S (2009) OrthoMADS: A deterministic MADS instance with orthogonal directions. SIAM J. Optim. 20(2):948-966.Crossref, Google Scholar · Zbl 1189.90202
[2] Audet C, Dennis J Jr (2006) Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(1):188-217.Crossref, Google Scholar · Zbl 1112.90078
[3] Audet C, Dennis J Jr (2009) A progressive barrier for derivative-free nonlinear programming. SIAM J. Optim. 20(1):445-472.Crossref, Google Scholar · Zbl 1187.90266
[4] Audet C, Béchard V, Chaouki J (2008) Spent potliner treatment process optimization using a MADS algorithm. Optim. Engrg. 9(2):143-160.Crossref, Google Scholar · Zbl 1167.92039
[5] Booker A, Dennis J Jr, Frank P, Serafini D, Torczon V, Trosset M (1999) A rigorous framework for optimization of expensive functions by surrogates. Structural Multidisciplinary Optim. 17(1):1-13.Crossref, Google Scholar
[6] Carter R, Gablonsky J, Patrick A, Kelley C, Eslinger O (2001) Algorithms for noisy problems in gas transmission pipeline optimization. Optim. Engrg. 2(2):139-157.Crossref, Google Scholar · Zbl 1079.90624
[7] Chen X, Kelley C (2016) Optimization with hidden constraints and embedded Monte Carlo computations. Optim. Engrg. 17(1):157-175.Crossref, Google Scholar · Zbl 1364.65119
[8] Choi T, Kelley C (2000) Superlinear convergence and implicit filtering. SIAM J. Optim. 10(4):1149-1162.Crossref, Google Scholar · Zbl 0994.65071
[9] Choi T, Eslinger O, Kelley C, David J, Etheridge M (2000) Optimization of automotive valve train components with implicit filtering. Optim. Engrg. 1(1):9-28.Crossref, Google Scholar · Zbl 1077.93523
[10] Davis E, Ierapetritou M (2009) Kriging based method for the solution of mixed-integer nonlinear programs containing black-box functions. J. Global Optim. 43(2-3):191-205.Crossref, Google Scholar · Zbl 1179.90238
[11] Davis SG, Joshi AV, Wang H, Egolfopoulos FN (2005) An optimized kinetic model for H2/CO combustions. Proc. Combustion Inst. 30(1):1283-1292.Crossref, Google Scholar
[12] Dong Y, Holley AT, Andac MG, Egolfopoulos FN, Davis SG, Middha P, Wang H (2005) Extinction of premixed H2/air flames: Chemical kinetics and molecular diffusion effects. Combustion Flame 142(4):374-387.Crossref, Google Scholar
[13] Finkel D, Kelley C (2009) Convergence analysis of sampling methods for perturbed Lipschitz functions. Pacific J. Optim. 5(2):339-350.Google Scholar · Zbl 1181.65084
[14] Frenklach M, Wang H, Goldenberg M, Smith G, Golden D, Bowman C, Hanson R, Gardiner W, Lissianski V (1995) GRI-Mech—An optimized detailed chemical reaction mechanism for methane combustion. Technical Report GRI-95/0058, Gas Research Institute.Google Scholar
[15] Friedman J (1991) Multivariate adaptive regression splines. Ann. Statist. 19(1):1-67.Crossref, Google Scholar · Zbl 0765.62064
[16] Glarborg P, Alzueta MU, Dam-Johansen K, Miller JA (1998) Kinetic modeling of hydrocarbon/nitric oxide interactions in a flow reactor. Combustion Flame 115(1-2):1-27.Crossref, Google Scholar
[17] Goel T, Haftka RT, Shyy W, Queipo NV (2007) Ensemble of surrogates. Structural Multidisciplinary Optim. 33(3):199-216.Crossref, Google Scholar
[18] Gratton S, Vicente L (2014) A merit function approach for direct search. SIAM J. Optim. 24(4):1980-1998.Crossref, Google Scholar · Zbl 1318.90077
[19] Grcar JF, Bell JB, Day MS (2008) The Soret effect in naturally propagating, premixed, lean, hydrogen-air flames. Proc. Combustion Inst. 32(1):1173-1180.Crossref, Google Scholar
[20] Gutmann H (2001) A radial basis function method for global optimization. J. Global Optim. 19(3):201-227.Crossref, Google Scholar · Zbl 0972.90055
[21] Hemker T (2008) Derivative free surrogate optimization for mixed-integer nonlinear black box problems in engineering. Unpublished doctoral dissertation, TU Darmstadt, Germany.Google Scholar
[22] Holmström K (2008) An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer global optimization. J. Global Optim. 9(4):311-339.Google Scholar · Zbl 1400.90226
[23] Huyer W, Neumaier A (2008) SNOBFIT—stable noisy optimization by branch and fit. ACM Trans. Math. Software 35(2):1-25.Crossref, Google Scholar
[24] Jones D (2001) A taxonomy of global optimization methods based on response surfaces. J. Global Optim. 21(4):345-383.Crossref, Google Scholar · Zbl 1172.90492
[25] Jones D, Schonlau M, Welch W (1998) Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4):455-492.Crossref, Google Scholar · Zbl 0917.90270
[26] Kelley C (2011) Implicit Filtering (SIAM, Philadelphia).Crossref, Google Scholar · Zbl 1246.68017
[27] Le Digabel S (2011) Algorithm 909: NOMAD: Nonlinear optimization with the MADS algorithm. ACM Trans. Math. Software 37(4):1-15.Crossref, Google Scholar · Zbl 1365.65172
[28] Le Digabel S, Wild S (2015) A taxonomy of constraints in simulation based optimization. arXiv:1505.07881v1.Google Scholar
[29] Lee H, Gramacy R, Linkletter C, Gray G (2011) Optimization subject to hidden constraints via statistical emulation. Pacific J. Optim. 7(3):467-478.Google Scholar · Zbl 05964910
[30] Li J, Zhao Z, Kazakov A, Dryer F (2004) An updated comprehensive kinetic model of hydrogen combustion. Internat. J. Chemical Kinetics 36(10):566-575.Crossref, Google Scholar
[31] Moré J, Wild S (2009) Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20(1):172-191.Crossref, Google Scholar · Zbl 1187.90319
[32] Müller J (2015) MISO: Mixed integer surrogate optimization framework. Optim. Engrg. 17(1):177-203.Crossref, Google Scholar · Zbl 1364.90230
[33] Müller J (2017) SOCEMO: Surrogate optimization of computationally expensive multiobjective problems. INFORMS J. Comput. 29(4):581-596.Link, Google Scholar
[34] Müller J, Piché R (2011) Mixture surrogate models based on Dempster-Shafer theory for global optimization problems. J. Global Optim. 51(1):79-104.Crossref, Google Scholar · Zbl 1230.90155
[35] Müller J, Shoemaker C (2014) 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.Crossref, Google Scholar · Zbl 1312.90064
[36] Müller J, Woodbury J (2017) GOSAC: Global optimization with surrogate approximation of constraints. J. Global Optim. 69(1):117-136.Crossref, Google Scholar · Zbl 1373.90118
[37] Müller J, Shoemaker C, Piché R (2013a) SO-I: A surrogate model algorithm for expensive nonlinear integer programming problems including global optimization applications. J. Global Optim. 59(4):865-889.Crossref, Google Scholar · Zbl 1305.90305
[38] Müller J, Shoemaker C, Piché R (2013b) SO-MI: A surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems. Comput. Oper. Res. 40(5):1383-1400.Crossref, Google Scholar · Zbl 1352.90067
[39] Myers R, Montgomery D (1995) Response Surface Methodology, Process and Product Optimization using Designed Experiments (Wiley-Interscience Publication, Hoboken, NJ).Google Scholar
[40] O’Connaire M, Curran HJ, Simmie JM, Pitz WJ, Westbrook CK (2004) A comprehensive modeling study of hydrogen oxidation. Internat. J. Chemical Kinetics 36(11):603-622.Crossref, Google Scholar
[41] Powell M (1992) The theory of radial basis function approximation in 1990. Light W, ed. Advances in Numerical Analysis, Vol. 2: Wavelets, Subdivision Algorithms and Radial Basis Functions (Oxford University Press, Oxford, UK), 105-210.Google Scholar
[42] Rashid K, Ambani S, Cetinkaya E (2013) An adaptive multiquadric radial basis function method for expensive black-box mixed-integer nonlinear constrained optimization. Engrg. Optim. 45(2):185-206.Crossref, Google Scholar
[43] Regis R (2016) Multi-objective constrained black-box optimization using radial basis function surrogates. J. Comput. Sci. 16:140-155.Crossref, Google Scholar
[44] Regis R, Shoemaker C (2005) Constrained global optimization of expensive black-box functions using radial basis functions. J. Global Optim. 31(1):153-171.Crossref, Google Scholar · Zbl 1274.90511
[45] Regis R, Shoemaker C (2007) A stochastic radial basis function method for the global optimization of expensive functions. INFORMS J. Comput. 19(4):497-509.Link, Google Scholar · Zbl 1241.90192
[46] Sacks J, Welch W, Mitchell T, Wynn H (1989) Design and analysis of computer experiments. Statist. Sci. 4(4):409-423.Crossref, Google Scholar · Zbl 0955.62619
[47] Talgorn B, Audet C, Le Digabel S, Kokkolaras M (2018) Locally weighted regression models for surrogate-assisted design optimization. Optim. Engrg. 19(1):213-238.Crossref, Google Scholar · Zbl 1391.90683
[48] Wild S, Shoemaker C (2013) Global convergence of radial basis function trust-region algorithms for derivative-free optimization. SIAM Rev. 55(2):349-371.Crossref, Google Scholar · Zbl 1270.65028
[49] Yang L,
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.