Sharp Singularity-Degree Bounds for Equality-Generated SDP–RLT Relaxations of Binary Programs

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 binary sets \(\{x\in\{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 \(\operatorname{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 \(\lfloor n/2\rfloor\) for \(n\geq2\). This is strikingly smaller than the sharp general bound \(n\) for feasible SDP systems with matrix variables of order \(n+1\) \cite[Example~2]{sturm2000error}. Thus, for individual relaxations, rank and nullity provide an a priori bound on the otherwise inaccessible singularity degree and on the H\”older exponent in error bounds estimating distance to feasibility from constraint residuals.

Article

Download

View PDF