Strong Partitioning and a Machine Learning Approximation for Accelerating the Global Optimization of Nonconvex Quadratically Constrained Quadratic Programs

We learn optimal instance-specific heuristics for the global minimization of nonconvex quadratically constrained quadratic programs (QCQPs). Specifically, we consider partitioning-based convex mixed-integer programming relaxations for nonconvex QCQPs and propose the novel problem of strong partitioning to optimally partition variable domains without sacrificing global optimality. Because solving this max-min strong partitioning problem exactly can be very challenging, we design a local optimization method that leverages generalized gradients of the value function of its inner-minimization problem. However, even solving the strong partitioning problem to local optimality can be time consuming. To address this, we propose a simple and practical machine learning (ML) approximation for homogeneous families of QCQPs. Motivated by practical applications, we conduct a detailed computational study using the open-source global solver Alpine to evaluate the effectiveness of our ML approximation in accelerating the repeated solution of homogeneous QCQPs with fixed structure. Our study considers randomly generated QCQP families, including instances of the pooling problem, that are benchmarked using state-of-the-art global optimization software. Numerical experiments demonstrate that our ML approximation of strong partitioning reduces Alpine’s solution time by a factor of 2–4.5 on average, with maximum reduction factors ranging from 10 to 200 across these QCQP families.

History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous.

Funding: The authors gratefully acknowledge funding from Los Alamos National Laboratory’s Center for Nonlinear Studies and the U.S. Department of Energy’s Laboratory Directed Research and Development program [Grants 20230091ER (Project “Learning to Accelerate Global Solutions for Non-convex Optimization”) and 20210078DR (Project “The Optimization of Machine Learning: Imposing Requirements on Artificial Intelligence”)].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0424) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0424). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.