EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3404. Random projections for quadratically constrained quadratic programming

Invited abstract in session WB-4: Mixed Integer Nonlinear Programming and Nonconvex Optimization , stream MINLP.

Wednesday, 10:30-12:00
Room: 1001 (building: 202)

Authors (first author is the speaker)

1. Benedetto Manca
Mathematics and Computer Science, Università degli Studi di Cagliari
2. Leo Liberti
CNRS LIX, Ecole Polytechnique
3. Pierre-Louis Poirion
RIKEN-AIP

Abstract

We consider quadratically constrained quadratic programs (QCQP) in a general form with both linear and quadratic constraints. We will show that, if the number of quadratic constraints m and the number of decision variables n are large enough, there exist two random matrices T (with k rows and m columns) and R (with r rows and n columns) such that it is possible to apply them to the parameters of the original problem in order to obtain another QCQP with fewer decision variables and quadratic constraints which is easier and faster to solve.
We will provide theoretical results showing that the projected program is related to the original one in terms of both feasibility and optimality and a procedure that exploits a solution of the projected program to obtain a solution of the original one.
Numerical experiments on some different classes of QCQPs will be presented.

Keywords

Status: accepted

Back to the list of papers