Global Optimization of Nonconvex Quadratically Constrained Programs via Sparse Sum-of-Squares Relaxations Applied to Water-Using Networks

Abstract

Nonconvex quadratically constrained programs (QCPs) with bilinear terms frequently arise in the optimization of chemical process systems such as water-using networks (WUNs). While global optimization approaches based on spatial branch-and-bound and mixed-integer linear programming relaxations have achieved significant advances, they remain computationally demanding when solving large instances. This paper proposes the novel application of an algorithm based on sparse sum-of-squares (SOS) relaxations for tractable global optimization of sparse WUNs, which is a class of nonconvex QCPs that exhibit sparsity patterns. By leveraging the structure of sparse WUNs, in which the number of connections between units is limited, the proposed approach constructs a polynomial optimization problem that can be reformulated as a hierarchy of semidefinite programs (SDPs) with reduced size via the concept of SOS polynomials. The SDPs can be solved efficiently and allow obtaining a certificate of global optimality or a bound on the best value of the objective function within the feasible region. Numerical results for several WUN instances with sparsity patterns demonstrate that the algorithm achieves a very small optimality gap, typically below 0.005%, with moderate computational effort. The proposed approach offers competitive or superior solution quality compared to state-of-the-art global optimization solvers. In addition, since the SDP size depends mostly on the number of variables of the SOS polynomials, the computational effort grows moderately with the number of water-using units. These results indicate that sparse SOS relaxations are a promising alternative for solving nonconvex QCPs with sparsity patterns to global optimality, particularly in chemical engineering applications.