Optimization of black-box problems using Smolyak grids and polynomial approximations. (English) Zbl 1405.90107
Summary: A surrogate-based optimization method is presented, which aims to locate the global optimum of box-constrained problems using input-output data. The method starts with a global search of the \(n\)-dimensional space, using a Smolyak (sparse) grid which is constructed using Chebyshev extrema in the one-dimensional space. The collected samples are used to fit polynomial interpolants, which are used as surrogates towards the search for the global optimum. The proposed algorithm adaptively refines the grid by collecting new points in promising regions, and iteratively refines the search space around the incumbent sample until the search domain reaches a minimum hyper-volume and convergence has been attained. The algorithm is tested on a large set of benchmark problems with up to thirty dimensions and its performance is compared to a recent algorithm for global optimization of grey-box problems using quadratic, kriging and radial basis functions. It is shown that the proposed algorithm has a consistently reliable performance for the vast majority of test problems, and this is attributed to the use of Chebyshev-based sparse grids and polynomial interpolants, which have not gained significant attention in surrogate-based optimization thus far.
MSC:
| 90C26 | Nonconvex programming, global optimization |
Keywords:
surrogate-based optimization; black-box optimization; Smolyak grids; sparse grids; Chebyshev; polynomial interpolationReferences:
| [1] | Kolda, TG; Lewis, RM; Torczon, V, Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45, 385-482, (2003) · Zbl 1059.90146 · doi:10.1137/S003614450242889 |
| [2] | Conn, AR; Digabel, S, Use of quadratic models with mesh-adaptive direct search for constrained black box optimization, Optim. Methods Softw., 28, 139-158, (2013) · Zbl 1270.90073 · doi:10.1080/10556788.2011.623162 |
| [3] | Davis, E; Ierapetritou, M, A Kriging-based approach to MINLP containing black-box models and noise, Ind. Eng. Chem. Res., 47, 6101-6125, (2008) · doi:10.1021/ie800028a |
| [4] | Jones, DR; Schonlau, M; Welch, WJ, Efficient global optimization of expensive black-box functions, J. Glob. Optim., 13, 455-492, (1998) · Zbl 0917.90270 · doi:10.1023/A:1008306431147 |
| [5] | Regis, RG, Constrained optimization by radial basis function interpolation for high-dimensional expensive black-box problems with infeasible initial points, Eng. Optim., 46, 218-243, (2014) · doi:10.1080/0305215X.2013.765000 |
| [6] | Audet, C; Dennis, JE, A progressive barrier for derivative-free nonlinear programming, SIAM J. Optim., 20, 445-472, (2009) · Zbl 1187.90266 · doi:10.1137/070692662 |
| [7] | Boukouvala, F; Ierapetritou, MG, Derivative-free optimization for expensive constrained problems using a novel expected improvement objective function, AIChE J., 60, 2462-2474, (2014) · doi:10.1002/aic.14442 |
| [8] | Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. SIAM, Philadelphia (2009) · Zbl 1163.49001 · doi:10.1137/1.9780898718768 |
| [9] | Echebest, N; Schuverdt, ML; Vignau, RP, A derivative-free method for solving box-constrained underdetermined nonlinear systems of equations, Appl. Math. Comput., 219, 3198-3208, (2012) · Zbl 1309.65055 |
| [10] | Thi, HA; Vaz, AIF; Vicente, LN, Optimizing radial basis functions by d.c. programming and its use in direct search for global derivative-free optimization, Top, 20, 190-214, (2012) · Zbl 1267.90110 · doi:10.1007/s11750-011-0193-9 |
| [11] | Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 1247-1293, (2013) · Zbl 1272.90116 · doi:10.1007/s10898-012-9951-y |
| [12] | Boukouvala, F; Floudas, CA, ARGONAUT: algorithms for global optimization of constrained grey-box computational problems, Optim. Lett., 11, 895-913, (2017) · Zbl 1373.90113 · doi:10.1007/s11590-016-1028-2 |
| [13] | Eason, JP; Biegler, LT, A trust region filter method for Glass box/black box optimization, AIChE J., 62, 3124-3136, (2016) · doi:10.1002/aic.15325 |
| [14] | Amaran, S; etal., Simulation optimization: a review of algorithms and applications, 4OR, 12, 301-333, (2014) · Zbl 1317.90002 · doi:10.1007/s10288-014-0275-2 |
| [15] | Amaran, S; etal., Simulation optimization: a review of algorithms and applications, Ann. Oper. Res., 240, 351-380, (2016) · Zbl 1342.90113 · doi:10.1007/s10479-015-2019-x |
| [16] | Cozad, A; Sahinidis, NV; Miller, DC, Learning surrogate models for simulation-based optimization, AIChE J., 60, 2211-2227, (2014) · doi:10.1002/aic.14418 |
| [17] | Jakobsson, S; etal., A method for simulation based optimization using radial basis functions, Optim. Eng., 11, 501-532, (2010) · Zbl 1243.65068 · doi:10.1007/s11081-009-9087-1 |
| [18] | Quan, N; etal., Simulation optimization via Kriging: a sequential search using expected improvement with computing budget constraints, IIE Trans., 45, 763-780, (2013) · doi:10.1080/0740817X.2012.706377 |
| [19] | Das, S; Suganthan, PN, Differential evolution: a survey of the state-of-the-art, IEEE Trans. Evol. Comput., 15, 4-31, (2011) · doi:10.1109/TEVC.2010.2059031 |
| [20] | Egea, JA; Martí, R; Banga, JR, An evolutionary method for complex-process optimization, Comput. Oper. Res., 37, 315-324, (2010) · Zbl 1175.90427 · doi:10.1016/j.cor.2009.05.003 |
| [21] | Ong, YS; Nair, PB; Keane, AJ, Evolutionary optimization of computationally expensive problems via surrogate modeling, Aiaa J., 41, 687-696, (2003) · doi:10.2514/2.1999 |
| [22] | Boukouvala, F; Misener, R; Floudas, CA, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Eur. J. Oper. Res., 252, 701-727, (2016) · Zbl 1346.90677 · doi:10.1016/j.ejor.2015.12.018 |
| [23] | Hooke, R; Jeeves, TA, Direct search solution of numerical and statistical problems, J. ACM, 8, 212-229, (1961) · Zbl 0111.12501 · doi:10.1145/321062.321069 |
| [24] | Nedler, JA; Mead, R, A simplex method for function minimization, Comput. J., 7, 308-313, (1965) · Zbl 0229.65053 · doi:10.1093/comjnl/7.4.308 |
| [25] | Booker, AJ; etal., A rigorous framework for optimization of expensive functions by surrogates, Struct. Multidiscip. Optim., 17, 1-13, (1999) · doi:10.1007/BF01197708 |
| [26] | Boukouvala, F; Ierapetritou, MG, Surrogate-based optimization of expensive flowsheet modeling for continuous pharmaceutical manufacturing, J. Pharm. Innov., 8, 131-145, (2013) · doi:10.1007/s12247-013-9154-1 |
| [27] | Caballero, JA; Grossmann, IE, An algorithm for the use of surrogate models in modular flowsheet optimization, AIChE J., 54, 2633-2650, (2008) · doi:10.1002/aic.11579 |
| [28] | Ciaurri, DE; Mukerji, T; Durlofsky, LJ; Yang, X-S (ed.); Koziel, S (ed.), Derivative-free optimization for oil field operations, 19-55, (2011), Berlin · doi:10.1007/978-3-642-20986-4_2 |
| [29] | Egea, JA; etal., Scatter search for chemical and bio-process optimization, J. Glob. Optim., 37, 481-503, (2007) · Zbl 1108.92001 · doi:10.1007/s10898-006-9075-3 |
| [30] | Torn, A., Zilinskas, A.: Global Optimization. Springer, New York (1989) · Zbl 0752.90075 · doi:10.1007/3-540-50871-6 |
| [31] | Jones, DR, A taxonomy of global optimization methods based on response surfaces, J. Glob. Optim., 21, 345-383, (2001) · Zbl 1172.90492 · doi:10.1023/A:1012771025575 |
| [32] | Powell, M.J.D.: A direct search optimization method that models the objective and constraint functions by linear interpolation. In: Gomez, S., Hennart, J.-P. (eds.) Advances in Optimization and Numerical Analysis, p. 51-67. Springer, Dordrecht (1994) · Zbl 0826.90108 |
| [33] | Powell, M.J.: The BOBYQA Algorithm for Bound Constrained Optimization Without Derivatives. Cambridge NA Report NA2009/06. University of Cambridge, Cambridge (2009) |
| [34] | Wilson, ZT; Sahinidis, NV, The ALAMO approach to machine learning, Comput. Chem. Eng., 106, 785-795, (2017) · doi:10.1016/j.compchemeng.2017.02.010 |
| [35] | Davis, E; Ierapetritou, M, A Kriging based method for the solution of mixed-integer nonlinear programs containing black-box functions, J. Glob. Optim., 43, 191-205, (2009) · Zbl 1179.90238 · doi:10.1007/s10898-007-9217-2 |
| [36] | Palmer, K; Realff, M, Optimization and validation of steady-state flowsheet simulation metamodels, Chem. Eng. Res. Des., 80, 773-782, (2002) · doi:10.1205/026387602320776849 |
| [37] | Boukouvala, F; Hasan, MF; Floudas, CA, Global optimization of general constrained grey-box models: new method and its application to constrained PDEs for pressure swing adsorption, J. Global Optim., 67, 3-42, (2017) · Zbl 1359.90101 · doi:10.1007/s10898-015-0376-2 |
| [38] | Gutmann, H-M, A radial basis function method for global optimization, J. Glob. Optim., 19, 201-227, (2001) · Zbl 0972.90055 · doi:10.1023/A:1011255519438 |
| [39] | Muller, J; Shoemaker, CA; Piche, 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 |
| [40] | Regis, RG; Shoemaker, CA, A quasi-multistart framework for global optimization of expensive functions using response surface models, J. Glob. Optim., 56, 1719-1753, (2013) · Zbl 1275.90068 · doi:10.1007/s10898-012-9940-1 |
| [41] | Eason, J; Cremaschi, S, Adaptive sequential sampling for surrogate model generation with artificial neural networks, Comput. Chem. Eng., 68, 220-232, (2014) · doi:10.1016/j.compchemeng.2014.05.021 |
| [42] | Fahmi, I; Cremaschi, S, Process synthesis of biodiesel production plant using artificial neural networks as the surrogate models, Comput. Chem. Eng., 46, 105-123, (2012) · doi:10.1016/j.compchemeng.2012.06.006 |
| [43] | Henao, CA; Maravelias, CT, Surrogate-based process synthesis, Comput. Aided Chem. Eng., 28, 1129-1134, (2010) · doi:10.1016/S1570-7946(10)28189-0 |
| [44] | Martelli, E; Amaldi, E, PGS-COM: a hybrid method for constrained non-smooth black-box optimization problems: brief review, novel algorithm and comparative evaluation, Comput. Chem. Eng., 63, 108-139, (2014) · doi:10.1016/j.compchemeng.2013.12.014 |
| [45] | Novak, E; etal., Smolyak/sparse grid algorithms, Tractability Multivar. Probl. Std. Inf. Funct., 12, 320-397, (2010) |
| [46] | Plaskota, L; Wasilkowski, GW, Smolyak’s algorithm for integration and L-1-approximation of multivariate functions with bounded mixed derivatives of second order, Numer. Algorithms, 36, 229-246, (2004) · Zbl 1069.41022 · doi:10.1023/B:NUMA.0000040060.56819.a7 |
| [47] | Bungartz, HJ; Dirnstorfer, S, Multivariate quadrature on adaptive sparse grids, Computing, 71, 89-114, (2003) · Zbl 1031.65037 · doi:10.1007/s00607-003-0016-4 |
| [48] | Bungartz, H.J., Dirnstorfer, S.: Higher order quadrature on sparse grids. In: Computational Science—Iccs 2004. In: Bubak, M., et al. (Ed.) Proceedings, p. 394-401 (2004) · Zbl 1107.65023 |
| [49] | Bungartz, H.-J., Pfluger, D., Zimmer, S.: Adaptive sparse grid techniques for data mining. Springer, Berlin (2008) · doi:10.1007/978-3-540-79409-7_9 |
| [50] | Harding, B.: Adaptive Sparse Grids and Extrapolation Techniques. In: Garcke, J., Pfluger, D. (eds.) Sparse Grids and Applications—Stuttgart 2014. Lecture Notes in Computational Science and Engineering, vol 109. Springer, Berlin (2016) · Zbl 1338.65039 |
| [51] | Jiang, Y; Xu, YS, B-spline quasi-interpolation on sparse grids, J. Complex., 27, 466-488, (2011) · Zbl 1221.65034 · doi:10.1016/j.jco.2011.03.003 |
| [52] | Pfluger, D; Peherstorfer, B; Bungartz, HJ, Spatially adaptive sparse grids for high-dimensional data-driven problems, J. Complex., 26, 508-522, (2010) · Zbl 1200.65100 · doi:10.1016/j.jco.2010.04.001 |
| [53] | Sickel, W; Ullrich, T, Spline interpolation on sparse grids, Appl. Anal., 90, 337-383, (2011) · Zbl 1219.41012 · doi:10.1080/00036811.2010.495336 |
| [54] | Zenger, C.: Sparse grids. In: Hackbusch, W. (ed.) Parallel algorithms for partial differential equations. Proceedings of the Sixth GAMM Seminar. Notes on numerical fluid mechanics. Braunschweig, Verlag Vieweg, vol 31 (1991) · Zbl 0763.65091 |
| [55] | Novak, E; Ritter, K; Floudas, CA (ed.); Pardalos, PM (ed.), Global optimization using hyperbolic cross points, (1996), Boston |
| [56] | Smolyak, S.A.: Quadrature and interpolation formulas for tensor products of certain classes of functions. In: Dokl. Akad. Nauk SSSR (1963) · Zbl 0202.39901 |
| [57] | Gerstner, T; Griebel, M, Numerical integration using sparse grids, Numer. Algorithms, 18, 209-232, (1998) · Zbl 0921.65022 · doi:10.1023/A:1019129717644 |
| [58] | Dung, D, Sampling and cubature on sparse grids based on a B-spline quasi-interpolation, Found. Comput. Math., 16, 1193-1240, (2016) · Zbl 1359.41001 · doi:10.1007/s10208-015-9274-8 |
| [59] | Tang, JJ; etal., Dimension-adaptive sparse grid interpolation for uncertainty quantification in modern power systems: probabilistic power flow, IEEE Trans. Power Syst., 31, 907-919, (2016) · doi:10.1109/TPWRS.2015.2404841 |
| [60] | Peherstorfer, B; etal., Selected recent applications of sparse grids, Numer. Math. Theory Methods Appl., 8, 47-77, (2015) · Zbl 1340.65213 · doi:10.4208/nmtma.2015.w05si |
| [61] | Gajda, P, Smolyak’s algorithm for weighted L-1-approximation of multivariate functions with bounded rth mixed derivatives over R-d, Numer. Algorithms, 40, 401-414, (2005) · Zbl 1086.65006 · doi:10.1007/s11075-005-0411-3 |
| [62] | Xu, GQ, On weak tractability of the Smolyak algorithm for approximation problems, J. Approx. Theory, 192, 347-361, (2015) · Zbl 1310.41027 · doi:10.1016/j.jat.2014.10.016 |
| [63] | Wasilkowski, GW; Wozniakowski, H, Explicit cost bounds of algorithms for multivariate tensor product problems, J. Complex., 11, 1-56, (1995) · Zbl 0819.65082 · doi:10.1006/jcom.1995.1001 |
| [64] | Valentin, J., Pfluger, D.: Hierarchical gradient-based optimization with b-splines on sparse grids. In: Garcke, J., Pfluger, D. (Eds.) Sparse Grids and Applications—Stuttgart 2014. Lecture Notes in Computational Science and Engineering, vol 109. Springer, Cham (2016) · Zbl 1338.65165 |
| [65] | Grimstad, B; Sandnes, A, Global optimization with spline constraints: a new branch-and-bound method based on B-splines, J. Glob. Optim., 65, 401-439, (2016) · Zbl 1372.90074 · doi:10.1007/s10898-015-0358-4 |
| [66] | Hulsmann, M; Reith, D, Spagrow-A derivative-free optimization scheme for intermolecular force field parameters based on sparse grid methods, Entropy, 15, 3640-3687, (2013) · Zbl 1337.81138 · doi:10.3390/e15093640 |
| [67] | Sankaran, S, Stochastic optimization using a sparse grid collocation scheme, Probab. Eng. Mech., 24, 382-396, (2009) · doi:10.1016/j.probengmech.2008.11.002 |
| [68] | Chen, P; Quarteroni, A, A new algorithm for high-dimensional uncertainty quantification based on dimension-adaptive sparse grid approximation and reduced basis methods, J. Comput. Phys., 298, 176-193, (2015) · Zbl 1349.65683 · doi:10.1016/j.jcp.2015.06.006 |
| [69] | Pronzato, L; Müller, WG, Design of computer experiments: space filling and beyond, Stat. Comput., 22, 681-701, (2012) · Zbl 1252.62080 · doi:10.1007/s11222-011-9242-3 |
| [70] | McKay, MD; Beckman, RJ; Conover, WJ, A comparison of three methods for selecting values of input variables in the analysis of output from a computer code, Technometrics, 21, 239-245, (1979) · Zbl 0415.62011 |
| [71] | Davis, E; Ierapetritou, M, A centroid-based sampling strategy for Kriging global modeling and optimization, AIChE J., 56, 220-240, (2010) |
| [72] | Owen, AB, Orthogonal arrays for computer experiments, integration and visualization, Stat. Sin., 2, 439-452, (1992) · Zbl 0822.62064 |
| [73] | Garud, SS; Karimi, IA; Kraft, M, Smart sampling algorithm for surrogate model development, Comput. Chem. Eng., 96, 103-114, (2017) · doi:10.1016/j.compchemeng.2016.10.006 |
| [74] | Fornberg, B; Zuev, J, The Runge phenomenon and spatially variable shape parameters in RBF interpolation, Comput. Math Appl., 54, 379-398, (2007) · Zbl 1128.41001 · doi:10.1016/j.camwa.2007.01.028 |
| [75] | Runge, C, Über empirische funktionen und die interpolation zwischen äquidistanten ordinaten, Zeitschrift für Mathematik und Physik, 46, 20, (1901) · JFM 32.0272.02 |
| [76] | Xiang, S; Chen, X; Wang, H, Error bounds for approximation in Chebyshev points, Numer. Math., 116, 463-491, (2010) · Zbl 1201.65040 · doi:10.1007/s00211-010-0309-4 |
| [77] | Barthelmann, V; Novak, E; Ritter, K, High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math., 12, 273-288, (2000) · Zbl 0944.41001 · doi:10.1023/A:1018977404843 |
| [78] | Davis, P.J., Rabinowitz, P.: Methods of Numerical Integration. Dover Publications (2007) · Zbl 1139.65016 |
| [79] | Judd, KL; etal., Smolyak method for solving dynamic economic models: Lagrange interpolation, anisotropic grid and adaptive domain, J. Econ. Dyn. Control, 44, 92-123, (2014) · Zbl 1402.91368 · doi:10.1016/j.jedc.2014.03.003 |
| [80] | Trefethen, N, Six myths of polynomial interpolation and quadrature, Math. Today, 47, 184-188, (2011) |
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.
