Learning to Accelerate the Global Optimization of Quadratically-Constrained Quadratic Programs

arXiv2301.00306MaRDI QIDQ6422232FDOQ6422232

Authors: Rohit Kannan, Harsha Nagarajan, Deepjyoti Deka

Publication date: 31 December 2022

Abstract: We learn optimal instance-specific heuristics for the global minimization of nonconvex quadratically-constrained quadratic programs (QCQPs). Specifically, we consider partitioning-based mixed-integer programming relaxations for nonconvex QCQPs and propose the novel problem of

e x t i t s t r o n g p a r t i t i o n i n g

to optimally partition variable domains

e x t i t w i t h o u t

sacrificing global optimality. We design a local optimization method for solving this challenging max-min strong partitioning problem and replace this expensive benchmark strategy with a machine learning (ML) approximation for homogeneous families of QCQPs. We present a detailed computational study on randomly generated families of QCQPs, including instances of the pooling problem, using the open-source global solver Alpine. Our numerical experiments demonstrate that strong partitioning and its ML approximation significantly reduce Alpine's solution time by factors of

3.5 - 16.5

and

2 - 4.5

e x t i t o n a v e r a g e

and by maximum factors of

15 - 700

and

10 - 200

, respectively, over the different QCQP families.

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Sensitivity, stability, parametric optimization (90C31)

This page was built for publication: Learning to Accelerate the Global Optimization of Quadratically-Constrained Quadratic Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6422232)