×

Deterministic global optimization with Gaussian processes embedded. (English) Zbl 1476.90270

Summary: Gaussian processes (Kriging) are interpolating data-driven models that are frequently applied in various disciplines. Often, Gaussian processes are trained on datasets and are subsequently embedded as surrogate models in optimization problems. These optimization problems are nonconvex and global optimization is desired. However, previous literature observed computational burdens limiting deterministic global optimization to Gaussian processes trained on few data points. We propose a reduced-space formulation for deterministic global optimization with trained Gaussian processes embedded. For optimization, the branch-and-bound solver branches only on the free variables and McCormick relaxations are propagated through explicit Gaussian process models. The approach also leads to significantly smaller and computationally cheaper subproblems for lower and upper bounding. To further accelerate convergence, we derive envelopes of common covariance functions for GPs and tight relaxations of acquisition functions used in Bayesian optimization including expected improvement, probability of improvement, and lower confidence bound. In total, we reduce computational time by orders of magnitude compared to state-of-the-art methods, thus overcoming previous computational burdens. We demonstrate the performance and scaling of the proposed method and apply it to Bayesian optimization with global optimization of the acquisition function and chance-constrained programming. The Gaussian process models, acquisition functions, and training scripts are available open-source within the “MeLOn – MachineLearning Models for Optimization” toolbox (https://git.rwth-aachen.de/avt.svt/public/MeLOn).

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C90 Applications of mathematical programming
68T01 General topics in artificial intelligence
60-04 Software, source code, etc. for problems pertaining to probability theory
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Amar, Y.; Schweidtmann, AM; Deutsch, P.; Cao, L.; Lapkin, A., Machine learning and molecular descriptors enable rational solvent selection in asymmetric catalysis, Chem. Sci., 10, 27, 6697-6706 (2019)
[2] Androulakis, IP; Maranas, CD; Floudas, CA, \( \alpha\) BB: a global optimization method for general constrained nonconvex problems, J. Glob. Optim., 7, 4, 337-363 (1995) · Zbl 0846.90087
[3] Bendtsen, C., Stauning, O.: Fadbad++ (version 2.1): a flexible C++ package for automatic differentiation (2012)
[4] Bongartz, D.: Deterministic global flowsheet optimization for the design of energy conversion processes. Ph.D. Thesis, RWTH Aachen University (2020). doi:10.18154/RWTH-2020-06052
[5] Bongartz, D.; Mitsos, A., Deterministic global optimization of process flowsheets in a reduced space using McCormick relaxations, J. Glob. Optim., 20, 9, 419 (2017) · Zbl 1386.90112
[6] Bongartz, D.; Mitsos, A., Deterministic global flowsheet optimization: between equation-oriented and sequential-modular methods, AIChE J., 65, 3, 1022-1034 (2019)
[7] Bongartz, D., Najman, J., Sass, S., Mitsos, A.: MAiNGO: McCormick-based Algorithm for mixed integer Nonlinear Global Optimization. Technical report, Process Systems Engineering (AVT.SVT), RWTH Aachen University (2018). http://permalink.avt.rwth-aachen.de/?id=729717
[8] Bonilla, E.V., Chai, K.M., Williams, C.: Multi-task Gaussian process prediction. In: Advances in neural information processing systems, pp. 153-160 (2008)
[9] Boukouvala, F.; Floudas, CA, Argonaut: algorithms for global optimization of constrained grey-box computational problems, Optim. Lett., 11, 5, 895-913 (2017) · Zbl 1373.90113
[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] Bradford, E., Imsland, L., Zhang, D., Chanona, E.A.d.R.: Stochastic data-driven model predictive control using Gaussian processes. arXiv:1908.01786 (2019)
[12] Bradford, E.; Schweidtmann, AM; Lapkin, A., Efficient multiobjective optimization employing Gaussian processes, spectral sampling and a genetic algorithm, J. Glob. Optim., 71, 2, 407-438 (2018) · Zbl 1406.90095
[13] Bradford, E.; Schweidtmann, AM; Zhang, D.; Jing, K.; del Rio-Chanona, EA, Dynamic modeling and optimization of sustainable algal production with uncertainty using multivariate Gaussian processes, Comput. Chem. Eng., 118, 143-158 (2018)
[14] Caballero, JA; Grossmann, IE, An algorithm for the use of surrogate models in modular flowsheet optimization, AIChE J., 54, 10, 2633-2650 (2008)
[15] Caballero, J.A., Grossmann, I.E.: Rigorous flowsheet optimization using process simulators and surrogate models. In: Computer Aided Chemical Engineering, vol. 25, pp. 551-556. Elsevier (2008)
[16] Chachuat, B.; Houska, B.; Paulen, R.; Peric, N.; Rajyaguru, J.; Villanueva, ME, Set-theoretic approaches in analysis, estimation and control of nonlinear systems, IFAC-PapersOnLine, 48, 8, 981-995 (2015)
[17] Chapelle, O., Li, L.: An empirical evaluation of Thompson sampling. In: J. Shawe-Taylor, R.S. Zemel, P.L. Bartlett, F. Pereira, K.Q. Weinberger (eds.) Advances in Neural Information Processing Systems 24, pp. 2249-2257. Curran Associates, Inc. (2011). http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling.pdf
[18] Charnes, A.; Cooper, WW, Chance-constrained programming, Manag. Sci., 6, 1, 73-79 (1959) · Zbl 0995.90600
[19] CLP, C.O.: Linear programming solver: an open source code for solving linear programming problems (2011). doi:10.5281/zenodo.3748677
[20] Cozad, A.; Sahinidis, NV; Miller, DC, Learning surrogate models for simulation-based optimization, AIChE J., 60, 6, 2211-2227 (2014)
[21] Damianou, A., Lawrence, N.: Deep Gaussian processes. In: Artificial Intelligence and Statistics, pp. 207-215 (2013)
[22] Davis, E.; Ierapetritou, M., A Kriging method for the solution of nonlinear programs with black-box functions, AIChE J., 53, 8, 2001-2012 (2007)
[23] Davis, E.; Ierapetritou, M., A kriging-based approach to MINLP containing black-box models and noise, Ind. Eng. Chem. Res., 47, 16, 6101-6125 (2008)
[24] Davis, E.; Ierapetritou, M., A centroid-based sampling strategy for Kriging global modeling and optimization, AIChE J., 56, 1, 220-240 (2010)
[25] Del Rio-Chanona, EA; Cong, X.; Bradford, E.; Zhang, D.; Jing, K., Review of advanced physical and data-driven models for dynamic bioprocess simulation: case study of algae-bacteria consortium wastewater treatment, Biotechnol. Bioeng., 116, 2, 342-353 (2019)
[26] Djelassi, H., Mitsos, A.: libALE—a library for algebraic logical expression trees (2019). https://git.rwth-aachen.de/avt.svt/public/libale. Accessed 8 Nov 2019
[27] Eason, JP; Biegler, LT, A trust region filter method for glass box/black box optimization, AIChE J., 62, 9, 3124-3136 (2016)
[28] Epperly, TGW; Pistikopoulos, EN, A reduced space branch and bound algorithm for global optimization, J. Glob. Optim., 11, 3, 287-311 (1997) · Zbl 1040.90567
[29] Freier, L.; Hemmerich, J.; Schöler, K.; Wiechert, W.; Oldiges, M.; von Lieres, E., Framework for Kriging-based iterative experimental analysis and design: optimization of secretory protein production in corynebacterium glutamicum, Eng. Life Sci., 16, 6, 538-549 (2016)
[30] Gill, PE; Murray, W.; Saunders, MA, SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM Rev., 47, 1, 99-131 (2005) · Zbl 1210.90176
[31] Glassey, J., Von Stosch, M.: Hybrid Modeling in Process Industries. CRC Press (2018)
[32] Gleixner, AM; Berthold, T.; Müller, B.; Weltge, S., Three enhancements for optimization-based bound tightening, J. Glob. Optim., 67, 4, 731-757 (2017) · Zbl 1369.90106
[33] Hasan, M.F., Baliban, R.C., Elia, J.A., Floudas, C.A.: Modeling, simulation, and optimization of postcombustion \(CO_2\) capture for variable feed concentration and flow rate. 2. pressure swing adsorption and vacuum swing adsorption processes. Ind. Eng. Chem. Res. 51(48), 15665-15682 (2012). doi:10.1021/ie301572n
[34] Helmdach, D.; Yaseneva, P.; Heer, PK; Schweidtmann, AM; Lapkin, AA, A multiobjective optimization including results of life cycle assessment in developing biorenewables-based processes, ChemSusChem, 10, 18, 3632-3643 (2017)
[35] Hofschuster, W., Krämer, W.: FILIB++ interval library (version 3.0.2) (1998) · Zbl 1365.65140
[36] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 3 edn. Springer, Berlin (1996). doi:10.1007/978-3-662-03199-5 · Zbl 0867.90105
[37] Hüllen, G., Zhai, J., Kim, S.H., Sinha, A., Realff, M.J., Boukouvala, F.: managing uncertainty in data-driven simulation-based optimization. Comput. Chem. Eng. (2019). doi:10.1016/j.compchemeng.2019.106519
[38] International Business Machies: IBM ilog CPLEX (version 12.1) (2009)
[39] Johnson, S.G.: The NLopt nonlinear-optimization package (version 2.4.2) (2016)
[40] 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
[41] Kahrs, O.; Marquardt, W., The validity domain of hybrid models and its application in process optimization, Chem. Eng. Process. Process Intensif., 46, 11, 1054-1066 (2007)
[42] Keßler, T.; Kunde, C.; McBride, K.; Mertens, N.; Michaels, D.; Sundmacher, K.; Kienle, A., Global optimization of distillation columns using explicit and implicit surrogate models, Chem. Eng. Sci., 197, 235-245 (2019)
[43] Keßler, T.; Kunde, C.; Mertens, N.; Michaels, D.; Kienle, A., Global optimization of distillation columns using surrogate models, SN Appl. Sci., 1, 1, 11 (2019)
[44] Kim, J., Choi, S.: On local optimizers of acquisition functions in Bayesian optimization. arXiv:1901.08350 (2019)
[45] Kraft, D., Algorithm 733: TOMP-fortran modules for optimal control calculations, ACM Trans. Math. Softw. (TOMS), 20, 3, 262-281 (1994) · Zbl 0888.65079
[46] Krige, DG, A statistical approach to some basic mine valuation problems on the witwatersrand, J. South. Afr. Inst. Min. Metall., 52, 6, 119-139 (1951)
[47] Liberti, L., Cafieri, S., Tarissan, F.: Reformulations in mathematical programming: a computational approach. In: A. Abraham, A. Hassanien, P. Siarry, A. Engelbrecht (eds.) Foundations of Computational Intelligence Volume 3. Studies in Computational Intelligence, vol. 203, pp. 153-234. Springer, Berlin (2009)
[48] Lin, Z.; Wang, J.; Nikolakis, V.; Ierapetritou, M., Process flowsheet optimization of chemicals production from biomass derived glucose solutions, Comput. Chem. Eng., 102, 258-267 (2017)
[49] Locatelli, M.; Schoen, F., Global Optimization: Theory, Algorithms, and Applications. MOS-SIAM Series on Optimization (2013), Philadelphia: Mathematical Programming Society, Philadelphia
[50] Maher, S.J., Fischer, T., Gally, T., Gamrath, G., Gleixner, A., Gottwald, R.L., Hendel, G., Koch, T., Lübbecke, M.E., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Weninger, D., Witt, J.T., Witzig, J.: The SCIP optimization suite (version 4.0)
[51] McBride, K.; Kaiser, NM; Sundmacher, K., Integrated reaction-extraction process for the hydroformylation of long-chain alkenes with a homogeneous catalyst, Comput. Chem. Eng., 105, 212-223 (2017)
[52] McBride, K.; Sundmacher, K., Overview of surrogate modeling in chemical process engineering, Chem. Ingenieur Tech., 91, 3, 228-239 (2019)
[53] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 1, 147-175 (1976) · Zbl 0349.90100
[54] Mehrian, M.; Guyot, Y.; Papantoniou, I.; Olofsson, S.; Sonnaert, M.; Misener, R.; Geris, L., Maximizing neotissue growth kinetics in a perfusion bioreactor: an in silico strategy using model reduction and Bayesian optimization, Biotechnol. Bioeng., 115, 3, 617-629 (2018)
[55] Menne, D.; Kamp, J.; Wong, JE; Wessling, M., Precise tuning of salt retention of backwashable polyelectrolyte multilayer hollow fiber nanofiltration membranes, J. Membr. Sci., 499, 396-405 (2016)
[56] Meyer, CA; Floudas, CA, Convex envelopes for edge-concave functions, Math. Program., 103, 2, 207-224 (2005) · Zbl 1099.90045
[57] Misener, R.; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 2, 503-526 (2014) · Zbl 1301.90063
[58] Mitsos, A.; Chachuat, B.; Barton, PI, McCormick-based relaxations of algorithms, SIAM J. Optim., 20, 2, 573-601 (2009) · Zbl 1192.65083
[59] Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., Riedmiller, M.: Playing atari with deep reinforcement learning. arXiv:1312.5602 (2013)
[60] Mogk, G., Mrziglod, T., Schuppert, A.: Application of hybrid models in chemical industry. In: Computer Aided Chemical Engineering, vol. 10, pp. 931-936. Elsevier (2002). doi:10.1016/S1570-7946(02)80183-3
[61] Najman, J.; Bongartz, D.; Mitsos, A., Convex relaxations of componentwise convex functions, Comput. Chem. Eng., 130, 106527 (2019)
[62] Najman, J., Mitsos, A.: On tightness and anchoring of McCormick and other relaxations. J. Glob. Optim. (2017). doi:10.1007/s10898-017-0598-6 · Zbl 1425.49014
[63] Quirante, N.; Javaloyes, J.; Caballero, JA, Rigorous design of distillation columns using surrogate models based on Kriging interpolation, AIChE J., 61, 7, 2169-2187 (2015)
[64] Quirante, N., Javaloyes, J., Ruiz-Femenia, R., Caballero, J.A.: Optimization of chemical processes using surrogate models based on a Kriging interpolation. In: Computer Aided Chemical Engineering, vol. 37, pp. 179-184. Elsevier (2015). doi:10.1016/B978-0-444-63578-5.50025-6
[65] Rall, D.; Menne, D.; Schweidtmann, AM; Kamp, J.; von Kolzenberg, L.; Mitsos, A.; Wessling, M., Rational design of ion separation membranes, J. Membr. Sci., 569, 209-219 (2019)
[66] Rasmussen, C.E.: Gaussian processes in machine learning. In: Advanced lectures on machine learning, pp. 63-71. Springer (2004) · Zbl 1120.68436
[67] Ryoo, HS; Sahinidis, NV, Global optimization of nonconvex NLPs and MINLPs with applications in process design, Comput. Chem. Eng., 19, 5, 551-566 (1995)
[68] Sacks, J., Welch, W.J., Mitchell, T.J., Wynn, H.P.: Design and analysis of computer experiments. Stat. Sci. (1989). doi:10.1214/ss/1177012413 · Zbl 0955.62619
[69] Schweidtmann, A.M., Clayton, A.D., Holmes, N., Bradford, E., Bourne, R.A., Lapkin, A.A.: Machine learning meets continuous flow chemistry: Automated optimization towards the pareto front of multiple objectives. Chem. Eng. J. (2018). doi:10.1016/j.cej.2018.07.031
[70] Schweidtmann, AM; Mitsos, A., Deterministic global optimization with artificial neural networks embedded, J. Optim. Theory Appl., 180, 3, 925-948 (2019) · Zbl 1407.90263
[71] Schweidtmann, A.M., Netze, L., Mitsos, A.: Melon: Machine learning models for optimization. https://git.rwth-aachen.de/avt.svt/public/MeLOn/ (2020)
[72] Shahriari, B.; Swersky, K.; Wang, Z.; Adams, RP; de Freitas, N., Taking the human out of the loop: a review of Bayesian optimization, Proc. IEEE, 104, 1, 148-175 (2016)
[73] Smith, EM; Pantelides, CC, Global optimisation of nonconvex MINLPs, Comput. Chem. Eng., 21, S791-S796 (1997)
[74] Snoek, J., Larochelle, H., Adams, R.P.: Practical Bayesian optimization of machine learning algorithms. In: Advances in Neural Information Processing Systems, pp. 2951-2959 (2012)
[75] Srinivas, N., Krause, A., Kakade, S.M., Seeger, M.: Gaussian process optimization in the bandit setting: no regret and experimental design. arXiv preprint arXiv:0912.3995 (2009) · Zbl 1365.94131
[76] Stuber, MD; Scott, JK; Barton, PI, Convex and concave relaxations of implicit functions, Optim. Methods Softw., 30, 3, 424-460 (2015) · Zbl 1327.65114
[77] Sundararajan, S., Keerthi, S.S.: Predictive approaches for choosing hyperparameters in Gaussian processes. In: Advances in Neural Information Processing Systems, pp. 631-637 (2000) · Zbl 1108.62327
[78] Tardella, F.; Floudas, CA; Pardalos, P., On the existence of polyhedral convex envelopes, Frontiers in Global Optimization, 563-573 (2004), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 1176.90473
[79] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 2, 225-249 (2005) · Zbl 1099.90047
[80] Tawarmalani, M., Sahinidis, N.V., Pardalos, P.: Convexification and global optimization in continuous and mixed-integer nonlinear programming: theory, algorithms, software, and applications. In: Nonconvex Optimization and Its Applications, vol. 65. Springer, Boston, MA (2002). doi:10.1007/978-1-4757-3532-1 · Zbl 1031.90022
[81] Tsoukalas, A.; Mitsos, A., Multivariate McCormick relaxations, J. Glob. Optim., 59, 2-3, 633-662 (2014) · Zbl 1312.90068
[82] Ulmasov, D., Baroukh, C., Chachuat, B., Deisenroth, M.P., Misener, R.: Bayesian optimization with dimension scheduling: application to biological systems. In: Computer Aided Chemical Engineering, vol. 38, pp. 1051-1056. Elsevier (2016). doi:10.1016/B978-0-444-63428-3.50180-6
[83] Von Stosch, M.; Oliveira, R.; Peres, J.; de Azevedo, SF, Hybrid semi-parametric modeling in process systems engineering: past, present and future, Comput. Chem. Eng., 60, 86-101 (2014)
[84] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542
[85] Wang, J., Hertzmann, A., Fleet, D.J.: Gaussian process dynamical models. In: Advances in Neural Information Processing Systems, pp. 1441-1448 (2006)
[86] Wechsung, A.; Scott, JK; Watson, HAJ; Barton, PI, Reverse propagation of McCormick relaxations, J. Glob. Optim., 63, 1, 1-36 (2015) · Zbl 1322.49048
[87] Wiebe, J., Cecílio, I., Dunlop, J., Misener, R.: A robust approach to warped Gaussian process-constrained optimization. arXiv:2006.08222 (2020)
[88] Wilson, J., Hutter, F., Deisenroth, M.: Maximizing acquisition functions for Bayesian optimization. In: Advances in Neural Information Processing Systems, pp. 9884-9895 (2018)
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.