Id: arxiv/2601.18545 Url: https://arxiv.org/abs/2601.18545 Tags: math.OC Score: 0 Title: Tight semidefinite programming relaxations for sparse box-constrained quadratic programs Domain: math.OC Source: arxiv Authors: Aida Khajavirad Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-01-26 Page: https://delphi.science/r/arxiv/2601.18545 We introduce a new class of semidefinite programming (SDP) relaxations for sparse box-constrained quadratic programs, obtained by a novel integration of the Reformulation Linearization Technique into standard SDP relaxations while explicitly exploiting the sparsity of the problem. The resulting relaxations are not implied by some of the most widely-used LP and SDP relaxations for this class of optimization problems. We establish a sufficient condition under which the convex hull of the feasible region of the lifted quadratic program is SDP-representable; the proof is constructive and yields…