Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Gupte, Akshay; Koster, Arie M. C. A.; Kuhnke, Sascha https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-165585
URL:

; ;

An Adaptive Refinement Algorithm for Discretizations of Nonconvex QCQP

pdf-format:


Abstract

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.

BibTeX - Entry

@InProceedings{gupte_et_al:LIPIcs.SEA.2022.24,
  author =	{Gupte, Akshay and Koster, Arie M. C. A. and Kuhnke, Sascha},
  title =	{{An Adaptive Refinement Algorithm for Discretizations of Nonconvex QCQP}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16558},
  URN =		{urn:nbn:de:0030-drops-165585},
  doi =		{10.4230/LIPIcs.SEA.2022.24},
  annote =	{Keywords: Quadratically Constrained Quadratic Programs, Mixed Integer Linear Programming, Heuristics, BoxQP, Disjoint Bilinear}
}

Keywords: Quadratically Constrained Quadratic Programs, Mixed Integer Linear Programming, Heuristics, BoxQP, Disjoint Bilinear
Seminar: 20th International Symposium on Experimental Algorithms (SEA 2022)
Issue date: 2022
Date of publication: 11.07.2022
Supplementary Material: Software (Source Code): https://github.com/skuhnke/qcqp_sourcecode


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI