(227e) Approaches to Improve Bilinear Relaxations in Reduced-Space

Global optimization is commonly required in routine process systems engineering tasks due to the nonconvexity of underlying models. Most approaches exploit a factorable representation of an underlying problem and subsequently lift this problem into a higher-dimensional space via the introduction of auxiliary variables [1, 2]. The use of McCormick-based relaxations [3, 4] may offer a significant advantage in that it allows for relaxations to be constructed in the reduced-dimension space of the original problem. Relaxations of functions constructed using this approach exhibit quadratic convergence, which reduces the amount of clustering encountered when using spatial branch-and-bound algorithms and variants thereof [1, 2, 5, 6].

Recent work has generalized this approach to include classes of problems that lack an explicit factorable representation: implicit functions [7], differential equations [4, 8, 9], and stochastic processes [10]. Applications of reduced-space McCormick relaxations in artificial neural networks and Gaussian processes have shown to perform better than state-of-the-art methods [11, 12, 13]. Moreover, when applied to a number of flowsheet applications, this approach has been shown to provide significant performance improvements [14, 15, 16]. This reduced-space approach currently forms the basis of two openly available solvers: EAGO.jl in Julia [17] and MAiNGO in C++ [18].

One of the central avenues recently explored for reduced-space optimization is the development of improved convex and concave relaxations of common functional forms in the decision space of the original problem; thereby minimizing the impact of the dependency and wrapping issues intrinsic to this approach. These efforts include the development of relaxations of componentwise-convex terms [19], novel relaxations of cost and thermodynamic functions [20], relaxations of activation functions commonly appearing in artificial neural networks [21], and Gaussian processes [13]. The bilinear operator represents one of the most commonly encountered nonlinear terms in MINLP problem formulations. Prior work on tightening relaxations of intermediate bilinear forms in a reduced-dimensionality space consists of the multivariate McCormick relaxation approach [22] and the extension to differentiable McCormick relaxations [23, 24]. A recent contribution has illustrated how additional nontrivial inequality may be used in a factorable programming [25].

In this work, we exploit the analogous representation of McCormick relaxations and factorable programming to formulate tighter relaxations using a priori information in the original decision space. We first develop the underlying theory to generate necessarily tighter reduced-space McCormick relaxations when a priori convex/concave relaxations of intermediate bilinear terms are available. We subsequently illustrate how these rules can be applied in a full McCormick relaxation scheme by comparing and contrasting three distinct approaches: the use of a coupled McCormick relaxation scheme with affine arithmetic [26], the propagation of subgradients and associated affine relaxations, and the direct use of relaxations of each factor. Use cases for these novel approaches will be examined ranging from standard applications in global optimization to exotic formulations involving embedded dynamical systems. We detail how the use of these novel relaxation methods may lead to fewer subproblems solved using branch-and-bound methods and lower overall computation time on a number of formulations. We further illustrate how this approach naturally leads to dramatic improvements in the solution time for chemical kinetic parameter estimation. We conclude by comparing the performance of our new approach to state-of-the-art methods for generating relaxations in the original problem space using a number of examples taken from the literature [3, 22, 27].

References:

[1] Horst, R. and Tuy, H., A. Global Optimization: Deterministic Approaches. Springer Berlin Heidelberg. 2013.

[2] Floudas, C.A., and Gounaris, C.E. "A review of recent advances in global optimization." Journal of Global Optimization 45.1 (2009): 3-38

[3] Mitsos, A., Chachuat, B., and Barton, P.I. “McCormick-Based Relaxations of Algorithms.” SIAM Journal on Optimization. 20(2): 573-601.

[4] Scott, J.K., Stuber, M.D., and Barton, P.I. “Generalized McCormick Relaxations.” Journal of Global Optimization, 51:569-606, 2011.

[5] Bompadre, A. and Mitsos, A. “Convergence rate of McCormick relaxations.” Journal of Global Optimization, 52:1-28, 2012.

[6] Wechsung, A., Schaber, S.D., and Barton, P.I., “The cluster problem revisited.” Journal of Global Optimization, 58(3):429-438, 2014.

[7] Stuber, M.D., Scott, J.K., and Barton, P.I. “Convex and Concave Relaxations of Implicit Functions.” Optimization Methods and Software. 30(3), 424-460, 2014.

[8] Scott, J.K., and Barton P.I. “Improved relaxations for the parametric solutions of ODEs using differential inequalities.” Journal of Global Optimization 57: 143–176, 2013).

[9] Sahlodin, A.M. and Chachuat, B. “Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs.” Applied Numerical Mathematics 61:803-820, 2011.

[10] S Shao, Yuanxun, and Joseph K. Scott. "Convex relaxations for global optimization under uncertainty described by continuous random variables." AIChE Journal 64.8 (2018): 3023-3033.

[11] Schweidtmann, A.M., Wolfgang R. Huster, Jannik T. Lüthje, and Alexander Mitsos. “Deterministic global process optimization: Accurate (single-species) properties via artificial neural networks.” Computers & Chemical Engineering, 121:67–74, 2019b.

[12] Schweidtmann, A.M., and Mitsos, A. "Deterministic global optimization with artificial neural networks embedded." Journal of Optimization Theory and Applications 180.3 (2019): 925-948.

[13] Schweidtmann, A.M., Dominik Bongartz, Daniel Grothe, Tim Kerkenhoff, Xiaopeng Lin, Jaromil Najman, and Alexander Mitsos. “Global optimization of gaussian processes.” arXiv preprint arXiv:2005.10902, 2020.

[14] Bongartz, D. and Mitsos, A. “Deterministic global optimization of process flowsheets in a reduced space using McCormick relaxations.” Journal of Global Optimization, 69(4):761–796, 2017.

[15] Bongartz, D. and Mitsos, A. “Deterministic global flowsheet optimization: Between equation-oriented and sequential-modular methods.” AIChE Journal, 65(3):1022–1034, 2019.

[16] Bongartz, D., Najman, J., and Mitsos, A. “Deterministic global optimization of steam cycles using the IAPWS-IF97 model.” Optimization and Engineering, 21: 1095-1131, 2020.

[17] Wilhelm, M.E. and Stuber, M.D. “EAGO.jl: easy advanced global optimization in Julia.” Optimization Methods and Software, pages 1–26, 2020.

[18] D Bongartz, J Najman, S Sass, and A Mitsos. “MAiNGO: McCormick based algorithm for mixed integer nonlinear global optimization.” Technical report, RWTH Aachen, 2018.

[19] Najman, J., Bongartz, D., and Mitsos, A. “Convex relaxations of componentwise convex functions.” Computers & Chemical Engineering, 130:106527, 2019.

[20] Najman, J., Bongartz, D., and Mitsos, A. “Relaxations of Thermodynamic property and costing models in process engineering.” Computers & Chemical Engineering, 130:106571, 2019b.

[21] Wilhelm, M.E., Wang, C. and Stuber, M.D. “Robust Optimization with Hybrid First-Principles Data-Driven Models. Under review.

[22] Angelos Tsoukalas and Mitsos, A. “Multivariate McCormick relaxations.” Journal of Global Optimization, 59(2-3):633–662, 2014

[23] Najman, J., Bongartz, D., Tsoukalas, A., and Mitsos, A. “Erratum to: Multivariate McCormick relaxations.” Journal of Global Optimization, 68:219–225, 2017.

[24] Khan, K.A., Watson, H.A.J, and Barton, P.I. “Differentiable McCormick relaxations.” Journal of Global Optimization, 67(4):687–729, 2016.

[25] Taotao He and Mohit Tawarmalani. “A new framework to relax composite functions in nonlinear programs.” Mathematical Programming, 1–40, 2020.

[26] Frederic Messine. “Extentions of affine arithmetic: Application to unconstrained global optimization.” JUCS, 8(11):992–1015, 2002.

[27] Najman, J. and Mitsos, A. “Tighter McCormick relaxations through subgradient propagation.” Journal of Global Optimization, 75:565–593, 2019.