Sharp Singularity-Degree Bounds for Equality-Generated SDP-RLT Relaxations of Binary Programs
Abstract
Singularity degree is an important measure of semidefinite programming (SDP) degeneracy, but it is generally unavailable a priori from the problem data. We augment the Shor relaxation of nonempty binary sets {x∈{0,1}n:Ax=b} with the first-level Reformulation-Linearization Technique (RLT) equations generated by the defining linear equalities. For the resulting equality-generated SDP-RLT relaxation, we determine the exact worst-case singularity degree. If rank(A)=m and 0<m<n, then the associated relaxation has singularity degree at most min{m,n−m}, and this rank-nullity bound is attained for every possible rank in this range. Consequently, the worst-case singularity degree over this class is ⌊ n/2⌋ for n≥ 2. This is strikingly smaller than the sharp general bound n for feasible SDP systems with matrix variables of order n+1 (Sturm, 2000, Example 2). Thus, for individual relaxations, rank and nullity provide an a priori bound on the otherwise inaccessible singularity degree and on the Hölder exponent in error bounds estimating distance to feasibility from constraint residuals.
Related
- Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations
- On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs
- A bounded degree SDSOS hierarchy for solving SPLD polynomial programs
- Relax and Follow: L0-Path Computation with L0-Bregman Relaxations
- Optimal Control of State Constrained Systems via Measure Relaxations and Polynomial Optimization
BibTeX
@misc{hu2026sharp,
title = {{Sharp Singularity-Degree Bounds for Equality-Generated SDP-RLT Relaxations of Binary Programs}},
author = {Hao Hu},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29945},
eprint = {2608.29945},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29945},
}
RIS
TY - UNPB
TI - Sharp Singularity-Degree Bounds for Equality-Generated SDP-RLT Relaxations of Binary Programs
AU - Hao Hu
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.29945
UR - https://arxiv.org/abs/2608.29945
AB - Singularity degree is an important measure of semidefinite programming (SDP) degeneracy, but it is generally unavailable a priori from the problem data. We augment the Shor relaxation of nonempty binary sets {x∈{0,1}^n:Ax=b} with the first-level Reformulation-Linearization Technique (RLT) equations generated by the defining linear equalities. For the resulting equality-generated SDP-RLT relaxation, we determine the exact worst-case singularity degree. If rank(A)=m and 0<m<n, then the associated relaxation has singularity degree at most min{m,n−m}, and this rank-nullity bound is attained for every possible rank in this range. Consequently, the worst-case singularity degree over this class is ⌊ n/2⌋ for n≥ 2. This is strikingly smaller than the sharp general bound n for feasible SDP systems with matrix variables of order n+1 (Sturm, 2000, Example 2). Thus, for individual relaxations, rank and nullity provide an a priori bound on the otherwise inaccessible singularity degree and on the Hölder exponent in error bounds estimating distance to feasibility from constraint residuals.
ER -