(10b) A Novel Algorithm for Constructing Tight Quadratic Underestimators for Global Optimization

Global optimization problems arise frequently in chemical engineering applications, such as in phase equilibrium, the identification of molecular conformations, distillation sequencing, reactor network design [1], among others. More recently, global optimization has also been used to scheduling hybrid energy sources for hydrogen production [2], regulating nitrogen oxide emissions under process uncertainty [3], synthesizing heat exchanger networks [4], and optimizing superstructures for producing fuels from ethanol [5]. In the aforementioned settings, non-convexities inherently present in the mathematical representation of the problem require the construction of convex relaxations within the context of spatial branch-and-bound search algorithms to identify a globally optimal solution. 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 global optimization algorithms address non-convexities by computing convex relaxations, polyhedrally outer approximating those, and solving linear programming (LP) subproblems to determine bounds for the spatial branch-and-bound tree [6]. While polyhedral outer approximations capitalize on the computational efficiency afforded by their construction, the approximations suffer in approximation accuracy. Considering also the strides achieved in the computational efficiency of convex quadratically constrained quadratic programming problems (QCQPs) [7], we conjecture that investing a greater amount of computational resources in the construction of non-linear convex quadratic outer approximations and in solving the resulting convex QCQP bounding subproblem at select nodes in the branch-and-bound tree will produce tighter bounds, expedite fathoming, and ultimately reduce the overall algorithm runtime. In this work, we address foundational work relevant to our hypothesis.

We create a novel algorithm to construct valid convex quadratic underestimators for twice differentiable convex functions. In this endeavor, we adopt and expand the work of Su et al. [8] that proposes constructing quadratic underestimators for convex functions by scaling the 2nd-order term of a Taylor series approximation at an arbitrary point of construction. More specifically, we generalize the classes of functions for which constructing such underestimators is possible, going beyond functions that possess specific coordinate-wise monotonicity properties. To that end, we reformulate the underestimation validity problem as a concave minimization problem over a convex set and modify the algorithm in [9] to simultaneously prove underestimation validity and determine the tightest scaling parameter for such scaled Hessian quadratic underestimators.

We further capitalize on features of our novel algorithm to naturally extend the construction of valid convex quadratic underestimators to non-convex functions representable as difference of convex (d.c.) functions. The procedure simultaneously convexifies and underestimates the non-convex d.c. functions, allowing direct outer approximation of the non-convex functions. However, as not all non-convex d.c. functions admit a valid convex scaled Hessian quadratic underestimator, we outline conditions under which our algorithm successfully executes.

Furthermore, in the context of constrained optimization problems, we identify an opportunity to modify our algorithm to further tighten our quadratic underestimators by permitting them to overestimate target functions in regions of the domain that are ascertained as infeasible in consideration of the external constraint information. We specifically show that integrating external linear constraint information produces tighter underestimators in a computationally tractable manner.

We test the performance of our convex quadratic underestimator construction algorithm on a comprehensive set of convex and d.c. functions to explicate the tractability limits of the algorithm and to demonstrate the quality of the underestimators obtained. We compile the test library of functions and optimization problems by adopting and combining different functions from various established optimization benchmark libraries, such as PrincetonLib [10] and MINLPLib [11]. We present the general applicability of our quadratic underestimation procedure to convex functions, demonstrate the results of direct outer approximation of non-convex d.c. functions, and characterize the overall quality of the generated underestimators.

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

[2] Yang, Yu, et al. "The scheduling of alkaline water electrolysis for hydrogen production using hybrid energy sources." Energy Conversion and Management 257 (2022): 115408.

[3] Kim, Minsu, et al. "Data-driven robust optimization for minimum nitrogen oxide emission under process uncertainty." Chemical Engineering Journal 428 (2022): 130971.

[4] Kazi, Saif R., et al. "Heat exchanger network synthesis with detailed exchanger designs—2. Hybrid optimization strategy for synthesis of heat exchanger networks." AIChE Journal 67.1 (2021): e17057.

[5] Restrepo-Flórez, Juan Manuel, and Christos T. Maravelias. "Advanced fuels from ethanol–a superstructure optimization approach." Energy & Environmental Science 14.1 (2021): 493-506.

[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: 30-March-2022].

[8] Su, Lijie, et al. "Improved quadratic cuts for convex mixed-integer nonlinear programs." Computers & Chemical Engineering 109 (2018): 77-95.

[9] Horst, Reiner, et al. "On solving a DC programming problem by a sequence of linear programs." Journal of Global Optimization 1.2 (1991): 183-203.

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

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