On the Ω(n) SDP relaxation gap for Submodular Box-Constrained Quadratic Programming
Abstract
Continuous submodular optimization is an important class of nonconvex problems with global guarantees, for which the submodular box-constrained quadratic programming (BCQP) forms a fundamental subclass. It arises naturally as quadratic subproblems of general twice-differentiable submodular problems and also has direct business and management applications such as pricing. This paper studies the worst-case relaxation gap of semidefinite programming (SDP) relaxations with a finite family of valid linear cuts for submodular BCQP. We show that in dimension n≥4, for any SDP relaxation formulated with a finite family of linear cuts, there always exists a submodular BCQP instance with a strictly positive relaxation gap. By restricting to the normalized BCQP instances that remove the problem's scaling factor, we further quantify this limitation with explicit lower bounds. In general dimension n≥4, when the SDP relaxation is formulated with only Boolean-quadric-polytope (BQP) valid cuts, including the commonly used McCormick and triangle inequalities, we establish an Ω(n) relaxation gap lower bound. For an arbitrary family of m valid linear cuts, we establish an Ω(n/m2) lower bound. These results capture the fundamental limitations of SDP relaxations, especially SDP with BQP valid cuts, and provide guidance on what additional constraints may be needed for more effective convex approximations of submodular BCQP.
Related
- Adaptive Variance-Reduced Stochastic Sequential (Quadratic Constrained) Quadratic Programming
- Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization
- A sequential quadratic programming method for optimization with expectation objective functions, deterministic inequality constraints and robust subproblems
- Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
BibTeX
@misc{zhang2026relaxation,
title = {{On the $Ω(n)$ SDP relaxation gap for Submodular Box-Constrained Quadratic Programming}},
author = {Junyu Zhang and Guanyi Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03617},
eprint = {2609.03617},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03617},
}
RIS
TY - UNPB
TI - On the Ω(n) SDP relaxation gap for Submodular Box-Constrained Quadratic Programming
AU - Junyu Zhang
AU - Guanyi Wang
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.03617
UR - https://arxiv.org/abs/2609.03617
AB - Continuous submodular optimization is an important class of nonconvex problems with global guarantees, for which the submodular box-constrained quadratic programming (BCQP) forms a fundamental subclass. It arises naturally as quadratic subproblems of general twice-differentiable submodular problems and also has direct business and management applications such as pricing. This paper studies the worst-case relaxation gap of semidefinite programming (SDP) relaxations with a finite family of valid linear cuts for submodular BCQP. We show that in dimension n≥4, for any SDP relaxation formulated with a finite family of linear cuts, there always exists a submodular BCQP instance with a strictly positive relaxation gap. By restricting to the normalized BCQP instances that remove the problem's scaling factor, we further quantify this limitation with explicit lower bounds. In general dimension n≥4, when the SDP relaxation is formulated with only Boolean-quadric-polytope (BQP) valid cuts, including the commonly used McCormick and triangle inequalities, we establish an Ω(n) relaxation gap lower bound. For an arbitrary family of m valid linear cuts, we establish an Ω(n/m^2) lower bound. These results capture the fundamental limitations of SDP relaxations, especially SDP with BQP valid cuts, and provide guidance on what additional constraints may be needed for more effective convex approximations of submodular BCQP.
ER -