A Fast Certifier for Large-Scale Degenerate SDPs in Outlier-Robust Machine Perception

The Moment/Sums-of-Squares hierarchy of semidefinite relaxations at order two has been shown as a powerful tool for solving non-convex and combinatorial outlier-robust machine perception problems to certifiable global optimality. Unfortunately, the resulting semidefinite programs (SDPs) are not only large but also highly degenerate. For example, in an SDP with matrix size n=804, and a number of equality constraints m=122,601, the primal solution X has rank r=1, making it pessimistically difficult for all existing SDP solvers. In this talk, I focus on the certification problem — given a primal feasible X, assert if X is optimal — and present an efficient two-phase certifier. In phase-one, we use an (accelerated) Douglas-Rachford Splitting method to find a dual solution that attains medium-accuracy dual infeasibility. In phase-two, we incorporate second-order information and employ an inexact semi-smooth newton method to attain high accuracy. For medium-scale problems, we show that the inexact newton step can be computed using a direct solver on a linear system that is much smaller than m (in fact on the order of r*n) by invoking the matrix inverse lemma on the original newton system. For large-scale problems, we solve the original newton system using an iterative solver with an effective diagonal preconditioner. We demonstrate solving certification problems to high accuracy in seconds. Joint and ongoing work with Luca Carlone, Ling Liang (NUS), and Kim-Chuan Toh (NUS).

Link to paper: https://arxiv.org/abs/2006.06769