Tight semidefinite programming relaxations for sparse box-constrained quadratic programs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.18545
curl -X POST /api/v1/records/arxiv/2601.18545/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.18545/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'