(468d) Separable Edge-Concave Underestimator for Global Optimization of High-Dimensional Problems Involving Signomials

Signomial functions are a generalization of multivariate polynomials where the exponents can be any real number such as negative and nonnegative fractions [1]. Signomials are ubiquitously found in chemical process optimization, engineering design, energy systems, supply chain management, healthcare and aerospace engineering etc [2-3]. Early works on signomial mostly considered posynomials, signomials with positive exponents. However, due to the existence of non-posynomial terms in applied fields, extensions were made to include any real exponents in signomial programming. For example, reactor design equations, the mass and energy balance constraints, and concave cost functions for different unit operations are signomials.

Deterministic global optimization aims to provide a theoretical guarantee on the optimality of such nonconvex problems. For this, underestimators are used to provide valid lower bounds. Convex underestimators are often used for relaxation of the original non-convex problem. While convex envelope is the tightest convex underestimator, these are known for only a few functions. For instance, multilinear, univariate monomials are signomials for which convex envelope formulations are available [4-5]. Moreover, convex underestimators, such as ɑ-BB and its variants [6], fail to generate tight lower bounds for general signomials. Apart from convex underestimators, edge-concave underestimators show promising results for relaxation of non-convex problems [7]. However, relaxation based on edge-concave underestimators perform function evaluations at 2ⁿ vertices which limits the computational efficiency as the number of vertices grows exponentially with dimensions.

To overcome these challenges, we have made several original contributions. First we show that for any n-dimensional separable function, there exists a single n-dimensional linear hyperplane that coincides at all the vertices of the function [8]. For any general signomial function defined in nonnegative orthant, we first develop a separable underestimator based on domain analysis and interval arithmetic. Then, the separable edge-concave (SEC) underestimator is generated by subtracting a positive quadratic expression such that all nonedge-concavities of the separable underestimators is overpowered. The SEC underestimator retains the properties of both separability and edge-concavity. This ensures the number of evaluations to be minimum to generate the convex envelope of the SEC underestimator. SEC underestimator attains a single n-dimensional linear hyperplane as its convex envelope where the convex envelope of an edge-concave underestimator is constructed with multiple linear facets. This significantly reduces the number of function evaluations from 2ⁿ to (n+1) to construct the convex envelope. Moreover, having an explicit expression of the hyperplane representing the convex envelope allows us to have a linear relaxation of the original nonconvex problem. Furthermore, we test our proposed relaxation technique to obtain root node lower bounds (LB) for several test functions with dimensions up to 100. With our relaxation technique, we successfully obtained tighter root node LBs in 9 out of 10 cases compared to the state-of-the-art commercial solver BARON v25.2.1. [9] in GAMS v49.2.0. We find that our method of relaxation, on average, provides tighter lower bounds for higher dimensional signomials.

Keywords: Global optimization, Linear Relaxation, Separable Functions, Edge-concave Underestimators, Signomials.

References:

[1] Dressler, M., & Murray, R. (2022). Algebraic perspectives on signomial optimization. SIAM Journal on Applied Algebra and Geometry, 6(4), 650-684.

[2] Biegler, L. T., Grossmann, I. E., Westerberg, A. W., & Kravanja, Z. (1997). Systematic methods of chemical process design (Vol. 796). Upper Saddle River, NJ: Prentice Hall PTR.

[3] Avriel, M., & Williams, A. C. (1971). An extension of geometric programming with applications in engineering optimization. Journal of Engineering Mathematics, 5(2), 187-194.

[4] Liberti, L., & Pantelides, C. C. (2003). Convex envelopes of monomials of odd degree. Journal of Global Optimization, 25, 157-168.

[5] Sherali, H. D. (1997). Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta mathematica vietnamica, 22(1), 245-270.

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

[7] Hasan, M. M. F. (2018). An edge-concave underestimator for the global optimization of twice-differentiable nonconvex problems. Journal of Global Optimization, 71(4), 735-752.

[8] Nath Roy, B., Hasan, M. M. F. (2025). Separable Edge-Concave Underestimator for High-Dimensional Signomials in Nonnegative Orthant, Under Review.

[9] Tawarmalani, M., & Sahinidis, N. V. (2005). A polyhedral branch-and-cut approach to global optimization. Mathematical programming, 103(2), 225-249.