Certifying Solutions of Degenerate Semidefinite Programs

We consider the problem of certifying the feasibility of a (possibly degenerate) semidefinite programming problem represented by rational input data together with a numerical solution that is guaranteed to be sufficiently close to an exact solution of maximal rank. Our method constructs a polynomial system whose set of real solutions has an isolated point that satisfies the input program. An experimental comparison between the corresponding symbolic-numerical algorithm and the purely symbolic algorithm from [3, 5] shows that the hybrid algorithm is able to certify instances where the exact method fails.