Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs. 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.
Keywords for this software
References in zbMATH (referenced in 8 articles , 1 standard article )
Showing results 1 to 8 of 8.
- Hauenstein, Jonathan D.; Liddell, Alan C. jun.; McPherson, Sanesha; Zhang, Yi: Numerical algebraic geometry and semidefinite programming (2021)
- Im, Jiyoung; Wolkowicz, Henry: A strengthened Barvinok-Pataki bound on SDP rank (2021)
- Lourenço, Bruno F.: Amenable cones: error bounds without constraint qualifications (2021)
- Lourenço, Bruno F.; Muramatsu, Masakazu; Tsuchiya, Takashi: Solving SDP completely with an interior point oracle (2021)
- Waki, Hayato; Sebe, Noboru: Characterization of the dual problem of linear matrix inequality for H-infinity output feedback control problem via facial reduction (2020)
- Pataki, Gábor: Characterizing bad semidefinite programs: normal forms and short proofs (2019)
- Roshchina, Vera; Tunçel, Levent: Facially dual complete (nice) cones and lexicographic tangents (2019)
- Zhu, Yuzixuan; Pataki, Gábor; Tran-Dinh, Quoc: Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs (2019)