Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.18545 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908829719986176 |
|---|---|
| author | Khajavirad, Aida |
| author_facet | Khajavirad, Aida |
| contents | 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 the existing 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 an explicit extended formulation. Although the resulting SDP may be of exponential size in general, we further identify additional structural conditions on the sparsity of the optimization problem that guarantee the existence of a polynomial-size SDP-representable formulation, which can be constructed in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_18545 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tight semidefinite programming relaxations for sparse box-constrained quadratic programs Khajavirad, Aida Optimization and Control 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 the existing 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 an explicit extended formulation. Although the resulting SDP may be of exponential size in general, we further identify additional structural conditions on the sparsity of the optimization problem that guarantee the existence of a polynomial-size SDP-representable formulation, which can be constructed in polynomial time. |
| title | Tight semidefinite programming relaxations for sparse box-constrained quadratic programs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2601.18545 |