(206b) Advances in Constructing Tight Quadratic Underestimators for Global Optimization

Several complex problems arising in chemical engineering applications, such as molecular conformation identification, distillation sequencing, reactor network design [1], among others, require non-convex mathematical optimization, which prescribes the use of global optimization algorithms to identify globally optimal solutions. Recently, global optimization has been applied in identifying synergistic domains of process intensification for reactive separation [2], scheduling hybrid energy sources for hydrogen production [3], regulating nitrogen oxide emissions under process uncertainty [4], and synthesizing heat exchanger networks [5]. In the aforementioned settings, global optimization algorithms address the non-convexities present in the mathematical representations of the problems by constructing convex relaxations in the context of spatial branch-and-bound to identify globally optimal solutions. Hence, as convex relaxation techniques improve in tightness and construction efficiency, practitioners will be enabled to tractably solve to global optimality a greater variety of problem types and sizes.

Current state-of-the art algorithms compute lower bounds for non-convex problems by (i) determining convex relaxations for non-convex expressions, (ii) polyhedrally outer approximating those, and (iii) solving the linear programming (LP) subproblems [6]. While linear approximations utilize the computational efficiency and reliability afforded by linear programming technology, recent advances in the computational efficiency and reliability of algorithms solving convex quadratically constrained quadratic programming problems (QCQPs) [7] suggest that utilizing non-linear convex quadratic relaxations rather than linear ones might be a numerically promising alternative. We conjecture that, in comparison to their linear counterparts, the marginal computational expense required to generate non-linear convex quadratic approximations at select nodes in the branch-and-bound tree will, by utilizing fathoming efficiencies, ultimately reduce the overall algorithm runtime.

In prior work [8], we developed a novel cutting-plane algorithm to construct valid convex quadratic underestimators of the form proposed by Su et al. [9] for (i) twice differentiable convex functions and (ii) twice differentiable non-convex functions with a difference of convex (d.c.) function representation under certain conditions. In this work, we propose multiple advances to our cutting-plane algorithm and quadratic underestimator form to generate even tighter quadratic underestimators with less stringent conditions for construction, and at improved computational times.

First, we modify the quadratic underestimator form by introducing a vector of scaling parameters into the 2^nd-order Taylor series term, each parameter corresponding to scaling a particular eigenvalue, thus achieving a non-uniformly scaled quadratic underestimator. Observing the linearity of the quadratic form as a function of the parameters, we determine the appropriate scaling parameters in the cutting- plane algorithm using an auxiliary LP. We provide examples of non-uniformly scaled quadratic underestimators and emphasize the improvement in tightness achieved.

Second, we introduce a linear shift parameter into the quadratic form that relaxes the stringent conditions for valid underestimator construction on d.c. functions. In particular, for points of construction that previously did not admit a valid quadratic underestimator, the linear shift parameter allows the cutting-plane algorithm to escape the rigidity of the Taylor series approximation and linearly shift the underestimator, thereby creating valid underestimators for all trial points of construction, although in many cases these underestimators are linear. Furthermore, by simultaneously optimizing the linear shift parameter and the non-uniform scaling parameters in the auxiliary LP, the cutting-plane algorithm generates quadratic underestimators for all trial points of construction where they are tighter than linear.

Third, we leverage the auxiliary LP in the cutting-plane algorithm to assess the computational efficiency and the underestimator quality of solving the parameter determination problem of multiple quadratic underestimators simultaneously. In other words, given a set of points of construction, rather than sequentially generating quadratic underestimators for points of construction one at a time without shared information and then taking the point-wise maximum to achieve an aggregate convex underestimator, we solve the parameter selection problem simultaneously for all points of construction directly on the point-wise maximum form. The advantages that arise from this approach are two-fold: (i) parameter values are determined in light of the aggregate underestimator, thus improving tightness and (ii) the procedure requires only one execution of the cutting-plane algorithm, rather than one per point of construction, thus conserving computational resources.

Fourth and finally, we explore more general forms of the quadratic underestimator that extend beyond the scaling of the diagonal and modify the off-diagonal elements. We start with the set of diagonally dominant symmetric matrices, which represents a (quite) restricted set of symmetric matrices that, while permitting modification of off-diagonal terms also preserves guarantees of convexity over domains.

We showcase the performance of our quadratic underestimators in two different computational studies. First, we examine the computational efficiency and underestimator quality of each variant on a set of modified test functions extracted from various established optimization benchmark libraries, such as PrincetonLib [10] and MINLPLib [11]. Second, we use the most promising variant in a root-node relaxation comparison with state-of-the-art global optimization algorithms. Observing that no benchmark library of d.c. optimization problems currently exists in literature, we consequently develop a set of multimodal d.c. optimization problems for testing.

[1] Adjiman, C. S., Dallwig, S., Floudas, C. A., & Neumaier, A. "A global optimization method, αBB, for general twice-differentiable constrained NLPs—I. Theoretical advances." Computers & Chemical Engineering 22.9 (1998): 1137-1158.

[2] Li, Jianping, and MM Faruque Hasan. "A parametric approach to identify synergistic domains of process intensification for reactive separation." Chemical Engineering Science 267 (2023): 118337.

[3] Yang, Y., De La Torre, B., Stewart, K., Lair, L., Phan, N.L., Das, R., Gonzalez, D. & Lo, R.C. "The scheduling of alkaline water electrolysis for hydrogen production using hybrid energy sources." Energy Conversion and Management 257 (2022): 115408.

[4] Kim, M., Cho, S., Jang, K., Hong, S., Na, J., & Moon, I. "Data-driven robust optimization for minimum nitrogen oxide emission under process uncertainty." Chemical Engineering Journal 428 (2022): 130971.

[5] Kazi, S. R., Short, M., Isafiade, A. J., & Biegler, L. T. "Heat exchanger network synthesis with detailed exchanger designs—2. Hybrid optimization strategy for synthesis of heat exchanger networks." AIChE Journal 67.1 (2021): e17057.

[6] Mohit Tawarmalani and Nikolaos V Sahinidis. “A polyhedral branch-and-cut approach to global optimization.” Mathematical programming, 103(2):225–249, 2005.

[7] Mittelmann, Hans D. Convex continuous QPLIB benchmark. http://plato.asu.edu/ftp/cconvex.html, 2021. [Online; Accessed: 22-March-2023].

[8] Strahl, W., Raghunathan, A., Sahinidis, N.V., & Gounaris, C.E. “A Novel Algorithm for Constructing Tight Quadratic Underestimators for Global Optimization [Conference presentation].” AIChE Annual Meeting, 13-18 Nov. 2022, Phoenix, Arizona.

[9] Su, L., Tang, L., Bernal, D. E., & Grossmann, I. E. "Improved quadratic cuts for convex mixed-integer nonlinear programs." Computers & Chemical Engineering 109 (2018): 77-95.

[10] Vanderbei, Robert. Princeton library of nonlinear programming models. http: //www.gamsworld.org/performance/princetonlib/princetonlib.htm, 2022. [Online; Accessed: 22-March-2023].

[11] Minlplib, a library of mixed-integer and continuous nonlinear programming instances. http://www.minlplib.org/, 2023