220. On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints
Invited abstract in session WD-2: Conic and polynomial optimization, stream Conic optimization: theory, algorithms and applications.
Wednesday, 11:25 - 12:40Room: M:O
Authors (first author is the speaker)
| 1. | Bo Peng
|
| University of Vienna | |
| 2. | Immanuel Bomze
|
| Dept. of Statistics and OR, University of Vienna | |
| 3. | Yuzhou Qiu
|
| School of Mathematics, The University of Edinburgh | |
| 4. | E. Alper Yildirim
|
| School of Mathematics, The University of Edinburgh |
Abstract
Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearization technique, the Shor relaxation, and the relaxation resulting from their combination. We establish several structural properties of these relaxations in relation to the corresponding relaxations of StQPs without any sparsity constraints, and pay particular attention to the rank-one feasible solutions retained by these relaxations. We then utilize these relations to establish several results about the quality of the lower bounds arising from different relaxations. We also present several conditions that ensure the exactness of each relaxation.
Keywords
- Conic and semidefinite optimization
Status: accepted
Back to the list of papers