1 Search Results for "Kuhnke, Sascha"

Document
DOI: 10.4230/LIPIcs.SEA.2022.24
An Adaptive Refinement Algorithm for Discretizations of Nonconvex QCQP

Authors: Akshay Gupte, Arie M. C. A. Koster, and Sascha Kuhnke

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

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.
Cite as

Akshay Gupte, Arie M. C. A. Koster, and Sascha Kuhnke. An Adaptive Refinement Algorithm for Discretizations of Nonconvex QCQP. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.24},
  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}
}
  • Refine by Author
  • 1 Gupte, Akshay
  • 1 Koster, Arie M. C. A.
  • 1 Kuhnke, Sascha

  • Refine by Classification
  • 1 Mathematics of computing → Nonconvex optimization
  • 1 Theory of computation → Mixed discrete-continuous optimization

  • Refine by Keyword
  • 1 BoxQP
  • 1 Disjoint Bilinear
  • 1 Heuristics
  • 1 Mixed Integer Linear Programming
  • 1 Quadratically Constrained Quadratic Programs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact