Search papers, labs, and topics across Lattice.
This paper introduces the Central-Path Certifier (CP-Cert), a novel method designed to certify candidate optima in non-convex problems that exhibit degeneracy, particularly in robotics applications. By leveraging indirect linear algebra techniques and exploiting problem sparsity, CP-Cert efficiently navigates the central path of the feasible space to obtain valid certificates, achieving significant speed improvements. The method demonstrates remarkable scalability, with runtimes up to three orders of magnitude faster than existing direct solvers, and is successfully applied to outlier-robust pose estimation in real-world scenarios.
CP-Cert achieves certification of optimality in degenerative non-convex problems at speeds up to 1,000 times faster than traditional solvers.
Certifiable methods have arisen as a means to guarantee global optimality of solutions to non-convex problems using convex semidefinite programming (SDP) relaxations. The most performant of these methods use a local solver to obtain the candidate solution, and then certify its optimality using efficient linear algebra techniques. However, for many problems of interest in robotics, this local-solve-then-certify approach is impeded by a form of degeneracy in the relaxation, leaving a costly optimization of the relaxation as the only recourse. In this paper, we introduce our Central-Path Certifier (CP-Cert), a certifiable method explicitly tailored to certify candidate optima to problems that exhibit this form of degeneracy. Using a candidate as a starting point, our approach seeks a nearby region of the feasible space -- known as the central path -- where a valid certificate can be readily obtained. The approach is kept efficient by exploiting indirect linear algebra techniques, problem sparsity, and parallelism. We apply CP-Cert to both matrix-weighted pose registration and pointcloud data association, whose novel SDP relaxation is of independent interest. On simulated examples, we explore the properties of this novel relaxation and show that CP-Cert is fast and scalable, achieving runtimes that are up to three orders of magnitude faster than state-of-the-art direct solvers. Finally, we combine these contributions into a certifiable, outlier-robust pose-estimation pipeline, which we apply to real-world data.
