This paper presents a backward stable preprocessing technique for (nearly) ill-posed semidefinite programming, SDP, problems, i.e.,~programs for which Slater’s constraint qualification, existence of strictly feasible points, (nearly) fails. Current popular algorithms for semidefinite programming rely on \emph{primal-dual interior-point, p-d i-p} methods. These algorithms require Slater’s constraint qualification for both the primal and dual problems. This assumption guarantees the existence of Lagrange multipliers, well-posedness of the problem, and stability of algorithms. However, there are many instances of SDPs where Slater’s constraint qualification fails or {\em nearly} fails. Our backward stable preprocessing technique is based on finding a {\em rank-revealing} rotation of the problem followed by facial reduction. This results in a smaller, well-posed, \emph{nearby} problem that can be solved by standard SDP solvers.
Citation
CORR 2011-02, University of Waterloo