An adaptive refinement algorithm for discretizations of nonconvex QCQP

Akshay Gupte*, Arie M.C.A. Koster, Sascha Kuhnke

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract / Description of output

We present an iterative algorithm to compute feasible solutions in reasonable running time to quadratically constrained quadratic programs (QCQPs), which form a challenging class of nonconvex continuous optimization. This algorithm is based on a mixed-integer linear program (MILP) which is a restriction of the original QCQP obtained by discretizing all quadratic terms. In each iteration, this MILP restriction is solved to get a feasible QCQP solution. Since the quality of this solution heavily depends on the chosen discretization of the MILP, we iteratively adapt the discretization values based on the MILP solution of the previous iteration. To maintain a reasonable problem size in each iteration of the algorithm, the discretization sizes are fixed at predefined values. Although our algorithm did not always yield good feasible solutions on arbitrary QCQP instances, an extensive computational study on almost 1300 test instances of two different problem classes -- box-constrained quadratic programs with complementarity constraints and disjoint bilinear programs, demonstrates the effectiveness of our approach. We compare the quality of our solutions against those from heuristics and local optimization algorithms in two state-of-the-art commercial solvers and observe that on one instance class we clearly outperform the other methods whereas on the other class we obtain competitive results.
Original languageEnglish
Title of host publication20th International Symposium on Experimental Algorithms
Subtitle of host publicationSEA 2022
EditorsChristian Schulz, Bora Uçar
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages14
Publication statusAccepted/In press - 2022

Publication series

NameLIPIcs - Leibniz International Proceedings in Informatics


Dive into the research topics of 'An adaptive refinement algorithm for discretizations of nonconvex QCQP'. Together they form a unique fingerprint.

Cite this