On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints

Immanuel Bomze (), Bo Peng (), Yuzhou Qiu () and E. Alper Yıldırım ()
Additional contact information
Immanuel Bomze: University of Vienna
Bo Peng: University of Vienna
Yuzhou Qiu: The University of Edinburgh
E. Alper Yıldırım: The University of Edinburgh

Journal of Optimization Theory and Applications, 2025, vol. 204, issue 3, No 3, 36 pages

Abstract: 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: Standard quadratic optimization problems; Sparsity; Mixed-integer quadratic optimization; Reformulation-linearization technique; Shor relaxation; 90C11; 90C20; 90C22 (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-024-02593-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:204:y:2025:i:3:d:10.1007_s10957-024-02593-1

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-024-02593-1

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().