Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
arXiv:1710.08954 · doi:10.1007/s12532-019-00164-4
Abstract
We introduce Sieve-SDP, a simple facial reduction algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP inspects the constraints of the problem to detect lack of strict feasibility, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, hence it can be implemented in a few lines of code in machine precision. We present extensive computational results on several problem collections from the literature, with many SDPs coming from polynomial optimization.
arXiv commentChanges wrt to previous version: very minor. There was a space omitted in the list of authors
References in corpus (6)
- A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with -Type of Constraints
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Bad semidefinite programs: they all look the same
- A real stable extension of the Vamos matroid polynomial
- A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs
Cited by in corpus (6)
- Amenable cones: error bounds without constraint qualifications
- Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert
- Douglas--Rachford Splitting and ADMM for Pathological Convex Optimization
- A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
- Solving SDP Completely with an Interior Point Oracle
- On Positive Duality Gaps in Semidefinite Programming