A strengthened Barvinok-Pataki bound on SDP rank

DOI10.1016/j.orl.2021.09.004OpenAlexW3199604012MaRDI QIDQ2670438

Jiyoung Im, Henry Wolkowicz

Publication date: 11 March 2022

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2021.09.004

zbMATH Keywords

semidefinite programmingrankfacial reductionsingularity degreeBarvinok-Pataki bound

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items

Revisiting degeneracy, strict feasibility, stability, in linear programming, Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization

Uses Software

• SDPLR
• ADMM_QAP
• Sieve-SDP

Cites Work

• Unnamed Item
• ADMM_QAP
• Positive semidefinite rank
• Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems
• Regularizing the abstract convex program
• Problems of distance geometry and convex properties of quadratic maps
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• A remark on the rank of positive semidefinite matrices subject to affine constraints
• Geometry of semidefinite Max-Cut relaxations via matrix ranks
• ADMM for the SDP relaxation of the QAP
• Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
• Local minima and convergence in low-rank semidefinite programming
• On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues
• Error Bounds for Linear Matrix Inequalities
• A low-rank coordinate-descent algorithm for semidefinite programming relaxations of optimal power flow
• Literature survey on low rank approximation of matrices
• Exact Duality in Semidefinite Programming Based on Elementary Reformulations
• Error Bounds and Singularity Degree in Semidefinite Programming
• Handbook of semidefinite programming. Theory, algorithms, and applications