(251a) Global Optimization of Nonconvex Quadratically Constrained Programs Via Sparse Sum-of-Squares Relaxations

Optimization problems with equality constraints that include bilinear terms are very common in chemical engineering since they arise whenever these constraints involve products of two decision variables, such as a flow rate and a composition or a heat capacity rate and a temperature. These problems result in nonconvex quadratically constrained programs (QCPs). Most of the existing global optimization algorithms for this purpose rely on a branch-and-bound approach, where the space of decision variables is successively divided one variable after another, and the regions where the optimum cannot be located are excluded until the optimum is eventually found. Even before a global optimum is determined, these algorithms allow obtaining an optimality gap between the best known objective and the best possible objective. However, even for state-of-the-art optimization solvers, a high computational effort is required to determine a tight optimality gap for large problem instances. This means that it remains computationally expensive to solve these large optimization problems to global optimality. Hence, it would be useful to exploit the structure of certain nonconvex QCPs in a way that allows achieving a small optimality gap with reduced computational effort.

The optimization of water-using networks (WUNs) is a relevant example of a nonconvex QCP with equality constraints that include bilinear terms. In these optimization problems, a typical objective is the minimization of the use of freshwater, while constraints related to the demands of the water-using units and the concentrations of certain pollutants must be satisfied. The outlet stream of each water-using unit is split and supplied to mixers at the inlet of each water-using unit, where it is mixed with a freshwater stream and outlet streams of other water-using units. The mass balance to each pollutant in each mixer results in an equality constraint that includes bilinear terms, which correspond to the product of a flow rate and a concentration.

For optimization problems that involve a polynomial objective function and polynomial constraints, which are also known as polynomial optimization problems (POPs) and are nonconvex in general, there exists another class of global optimization algorithms that use sum-of-squares (SOS) relaxations. In these algorithms, the POPs are expressed as a hierarchy of convex semidefinite programs (SDP) of increasing relaxation order by using the concept of SOS polynomials, that is, nonnegative polynomials that can be written as the sum of squares of polynomials. The relaxation order depends on the degree of the polynomials in the POP and determines the maximum degree of the SOS polynomials [1]. More specifically, for each relaxation order, one determines the maximum scalar value such that the difference between the objective function and that scalar value is a conical combination of SOS polynomials weighted by the polynomial constraints. In turn, this implies that the difference between the objective function and the scalar value is strictly positive and the scalar value is a lower bound for the objective function in the feasible region specified by the polynomial constraints. Since each SOS polynomial has an equivalent representation in terms of a linear matrix inequality, this results in the reformulation of POPs as convex SDPs of increasing size. If the optimality gap is zero for some relaxation order, it is possible to obtain a certificate of global optimality as well as the global optimum from the solution to the SDP [2]. Even if this certificate is not obtained, it is possible to compute a lower bound that is increasingly tight as the relaxation order increases. The size of the SDPs is related to the degree and the number of variables of the SOS polynomials, and the degree of the SOS polynomials is related to the degree of the polynomials in the POP, as mentioned. Since the degree of the polynomials in the constraints of QCPs is at most two, which is small, the size of the SDPs is potentially small for QCPs. However, if all the variables of the QCP are included in the SOS polynomials, this may lead to an SDP with a very large size that results in an intractable problem. Hence, it is necessary to look for a way to reduce the number of variables of the SOS polynomials.

To deal with this problem, the concept of sparse SOS relaxations can be used for POPs that contain a sparsity pattern. In these relaxations, the SOS polynomials only involve sets of variables such that: (i) the set of all the variables in each constraint is contained in at least one of the sets of variables of the SOS polynomials; (ii) the objective function is a sum of subfunctions, where the set of all the variables in each subfunction is contained in at least one of the sets of variables of the SOS polynomials; (iii) the sets of variables of the SOS polynomials can be ordered in a way that satisfies the so-called running intersection property. This allows using SOS polynomials with a reduced number of variables, which results in a smaller size of the SDPs [3].

Hence, for a QCP that contains a sparsity pattern, both the degree and the number of variables of the resulting SOS polynomials are relatively small, which implies that the size of the SDP is relatively small and the SDP can be solved efficiently, even if the QCP involves a large number of decision variables. For example, in the case of the QCPs that stem from optimization of WUNs, such a sparsity pattern can be found if (i) the outlet stream of each water-using unit is connected to a small number of mixers at the inlet of the water-using units and (ii) the mixer at the inlet of each water-using unit mixes outlet streams from a small number of water-using units. Note that such a sparsity pattern may exist even if the WUN contains a very large number of water-using units, which makes sparse SOS relaxations particularly useful for optimization of these WUNs. In practice, this sparsity pattern may exist if the water-using units are geographically dispersed, which may hinder connections between distant units.

In previous work, optimization of WUNs was tested for several problem instances using different state-of-the-art global optimization solvers and algorithms, and it was found that the optimality gap is relatively large for several instances even after some hours of computational time [4]. These problem instances were adapted to include sparsity patterns, and the algorithm based on sparse SOS relaxations was used. For all the problem instances that were tested, the algorithm based on sparse SOS relaxations achieved a very small optimality gap of around 0.1% or less for a relaxation order of two, which required at most some hours of computational time for each instance. Also, since the size of the resulting SDPs for a given relaxation order can be analytically computed in advance before each SDP is solved, it is possible to have a rather precise estimate of the time needed to solve the SDP. From this analysis, it is possible to state that the size of the SDP that results from each instance depends linearly on the number of water-using units, which is also the case for the number of decision variables of each instance. Hence, for a given instance of optimization of WUNs with a sparsity pattern, it is possible to know in advance how much time one needs to wait before a very small optimality gap is obtained using sparse SOS relaxations.

In future work, other problem instances of optimization of WUNs with a similar sparsity pattern but an even larger number of decision variables will also be tested, to check whether a very small optimality gap is also obtained for these larger instances. Since the size of the SDPs depends linearly on the number of water-using units and SDPs are convex optimization problems, as mentioned, this future work is also expected to confirm that the computational time grows moderately with an increasing number of water-using units. Also, it would be interesting to find other relevant classes of problems that can be formulated as nonconvex QCPs with a sparsity pattern. In general, this work is expected to disseminate sparse SOS relaxations among the chemical engineering community since this global optimization approach is currently less known than other ones such as branch-and-bound methods. This may open new perspectives for computationally tractable global optimization of several relevant problems in chemical engineering that can be formulated as nonconvex QCPs.

Acknowledgments: This work was supported by national funds through FCT/MCTES (PIDDAC): LSRE-LCM, UIDB/50020/2020 (DOI: 10.54499/UIDB/50020/2020) and UIDP/50020/2020 (DOI: 10.54499/UIDP/50020/2020); ALiCE, LA/P/0045/2020 (DOI: 10.54499/LA/P/0045/2020); and CERENA, UIDB/04028/2020 (DOI: 10.54499/UIDB/04028/2020).

References:

[1] J. B. Lasserre. Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11:796-817, 2001.

[2] J. B. Lasserre. A semidefinite programming approach to the generalized problem of moments, Math. Program., 112:65-92, 2008.

[3] M. Kojima, S. Kim, and H. Waki. Sparsity in sums of squares of polynomials, Math. Program., 103:1, 45-62, 2005.

[4] P. M. Castro and J. P. Teles. Comparison of global optimization algorithms for the design of water-using networks. Comput. Chem. Eng., 52, 249-261, 2013.