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

Area of Science:

• Optimization Theory
• Mathematical Programming
• Operations Research

Background:

• Standard Quadratic Optimization Problems (StQPs) are widely used in various applications.
• Sparse StQPs, a variant with hard sparsity constraints, present unique modeling challenges.
• Existing convex relaxations for StQPs require adaptation for sparse formulations.

Purpose of the Study:

• To investigate tractable convex relaxations for sparse StQPs.
• To analyze the structural properties of these relaxations, particularly rank-one feasible solutions.
• To assess the quality of lower bounds and identify conditions for exactness.

Main Methods:

• Focus on mixed-binary quadratic formulation for sparse StQPs.
• Examine linear optimization relaxation via reformulation-linearization technique (RLT).
• Analyze Shor relaxation and combinations of RLT and Shor relaxations.

Main Results:

• Establish structural properties linking sparse StQP relaxations to standard StQP relaxations.
• Identify the role of rank-one feasible solutions in the relaxations.
• Derive results on the quality of lower bounds provided by different relaxations.

Conclusions:

• The study provides a theoretical framework for understanding convex relaxations of sparse StQPs.
• Conditions for exactness of various relaxations are presented.
• The findings contribute to improving the efficiency and accuracy of solving sparse StQPs.