×

zbMATH — the first resource for mathematics

Deterministic global derivative-free optimization of black-box problems with bounded Hessian. (English) Zbl 1439.90077
Summary: Obtaining guaranteed lower bounds for problems with unknown algebraic form has been a major challenge in derivative-free optimization. In this work, we present a deterministic global optimization method for black-box problems where the derivatives are not available or it is computationally expensive to obtain. However, a global upper bound on the diagonal Hessian elements is known. An edge-concave underestimator [the second author, J. Glob. Optim. 71, No. 4, 735–752 (2018; Zbl 1422.90038)] can be then constructed with a vertex polyhedral solution. Evaluating this underestimator only at the vertices leads to a valid lower bound on the original black-box problem. We have implemented this lower bounding technique within a branch-and-bound framework and assessed its computational performance in a locating \(\epsilon\)-global optimal solution for several box-constrained, nonconvex black-box functions.
MSC:
90C56 Derivative-free methods and methods using generalized derivatives
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts, EH; Van Laarhoven, PJ, Statistical cooling: a general approach to combinatorial optimization problems, Philips J. Res., 40, 4, 193-226 (1985)
[2] Abraham, F.; Behr, M.; Heinkenschloss, M., Shape optimization in steady blood flow: a numerical study of non-newtonian effects, Comput. Methods Biomech. Biomed. Eng., 8, 2, 127-137 (2005)
[3] Agarwal, A.; Biegler, LT; Zitney, SE, Simulation and optimization of pressure swing adsorption systems using reduced-order modeling, Ind. Eng. Chem. Res., 48, 5, 2327-2343 (2008)
[4] Arora, A.; Bajaj, I.; Iyer, SS; Hasan, MMF, Optimal synthesis of periodic sorption enhanced reaction processes with application to hydrogen production, Comput. Chem. Eng., 115, 89-111 (2018)
[5] Arora, A.; Iyer, SS; Bajaj, I.; Hasan, MF, Optimal methanol production via sorption-enhanced reaction process, Ind. Eng. Chem. Res., 57, 42, 14143-14161 (2018)
[6] Bajaj, I.; Iyer, SS; Hasan, MF, A trust region-based two phase algorithm for constrained black-box and grey-box optimization with infeasible initial point, Comput. Chem. Eng., 116, 306-321 (2018)
[7] Barton, R.R.: Metamodeling: a state of the art review. In: Simulation Conference Proceedings, 1994. Winter, pp. 237-244. IEEE (1994)
[8] Bélisle, CJ; Romeijn, HE; Smith, RL, Hit-and-run algorithms for generating multivariate distributions, Math. Oper. Res., 18, 2, 255-266 (1993) · Zbl 0771.60052
[9] Bethke, A.D.: Genetic algorithms as function optimizers. Ph.D. thesis, Department of Computer and Communication Sciences, University of Michigan, Ann Arbor (1978)
[10] 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, 3, 701-727 (2016) · Zbl 1346.90677
[11] Conn, AR; Scheinberg, K.; Vicente, LN, Introduction to Derivative-Free Optimization (2009), Philadelphia: Siam, Philadelphia
[12] Eberhart, R., Kennedy, J.: A new optimizer using particle swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995. MHS’95., pp. 39-43. IEEE (1995)
[13] Gutmann, HM, A radial basis function method for global optimization, J. Glob. Optim., 19, 3, 201-227 (2001) · Zbl 0972.90055
[14] Guzman, YA; Hasan, MF; Floudas, CA, Performance of convex underestimators in a branch-and-bound framework, Optim. Lett., 10, 2, 283-308 (2016) · Zbl 1343.90068
[15] Hansen, N.: The CMA evolution strategy: a tutorial (2016). arXiv preprint arXiv:1604.00772
[16] Hasan, MMF, An edge-concave underestimator for the global optimization of twice-differentiable nonconvex problems, J. Glob. Optim., 71, 4, 735-752 (2018) · Zbl 1422.90038
[17] Hasan, MMF; First, EL; Floudas, CA, Cost-effective \(CO_2\) capture based on in silico screening of zeolites and process optimization, Phys. Chem. Chem. Phys., 15, 40, 17601-17618 (2013)
[18] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches (2013), Berlin: Springer Science & Business Media, Berlin
[19] Huyer, W.; Neumaier, A., Global optimization by multilevel coordinate search, J. Glob. Optim., 14, 4, 331-355 (1999) · Zbl 0956.90045
[20] Huyer, W.; Neumaier, A., SNOBFIT-stable noisy optimization by branch and fit, ACM Trans. Math. Softw. (TOMS), 35, 2, 9 (2008)
[21] Iyer, SS; Bajaj, I.; Balasubramanian, P.; Hasan, MMF, Integrated carbon capture and conversion to produce syngas: novel process design, intensification, and optimization, Ind. Eng. Chem. Res., 56, 30, 8622-8648 (2017)
[22] Iyer, SS; Demirel, SE; Hasan, MMF, Combined natural gas separation and storage based on in silico material screening and process optimization, Ind. Eng. Chem. Res., 57, 16727-16750 (2018)
[23] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the lipschitz constant, J. Optim. Theory Appl., 79, 1, 157-181 (1993) · Zbl 0796.49032
[24] Jones, DR; Schonlau, M.; Welch, WJ, Efficient global optimization of expensive black-box functions, J. Glob. optim., 13, 4, 455-492 (1998) · Zbl 0917.90270
[25] Larsson, AC; Einvall, J.; Andersson, A.; Sanati, M., Targeting by comparison with laboratory experiments the scr catalyst deactivation process by potassium and zinc salts in a large-scale biomass combustion boiler, Energy Fuels, 20, 4, 1398-1405 (2006)
[26] Lima, R.; François, G.; Srinivasan, B.; Salcedo, R., Dynamic optimization of batch emulsion polymerization using msimpsa, a simulated-annealing-based algorithm, Ind. Eng. Chem. Res., 43, 24, 7796-7806 (2004)
[27] Misener, R.; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 2-3, 503-526 (2014) · Zbl 1301.90063
[28] Papamichail, I.; Adjiman, CS, A rigorous global optimization algorithm for problems with ordinary differential equations, J. Glob. Optim., 24, 1, 1-33 (2002) · Zbl 1026.90071
[29] Pintér, JD, Global Optimization in Action: Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications (2013), Berlin: Springer Science & Business Media, Berlin
[30] Powell, M.J.D.: The BOBYQA algorithm for bound constrained optimization without derivatives. Cambridge NA Report NA2009/06, University of Cambridge, Cambridge (2009)
[31] Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 3, 1247-1293 (2013) · Zbl 1272.90116
[32] Sacks, J.; Welch, WJ; Mitchell, TJ; Wynn, HP, Design and analysis of computer experiments, Stat. Sci., 4, 409-423 (1989) · Zbl 0955.62619
[33] Shubert, BO, A sequential method seeking the global maximum of a function, SIAM J. Numer. Anal., 9, 3, 379-388 (1972) · Zbl 0251.65052
[34] Tardella, Fabio, On the existence of polyhedral convex envelopes, Nonconvex Optimization and Its Applications, 563-573 (2004), Boston, MA: Springer US, Boston, MA · Zbl 1176.90473
[35] Tawarmalani, M.; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Programm., 99, 3, 563-591 (2004) · Zbl 1062.90041
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.