Wednesday, March 24, 2021 - 4:00pm to 4:30pm
Event Calendar Category
LIDS & Stats Tea
Zoom meeting id
941 9313 3201
Join Zoom meeting
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
Heng Yang is a Ph.D. student at LIDS, advised by Prof. Luca Carlone. He is broadly interested in robotics, computer vision, and optimization, and learning. In particular, his research, certifiably robust perception, focuses on developing machine perception algorithms for safety-critical applications that are not only robust against large amounts of outliers but also can be certified to be optimal. He received a B.E. from Tsinghua University in China, and an S.M. from MIT, both in Mechanical Engineering. He is a recipient of the Best Paper Award in Robot Vision at the 2020 International Conference on Robotics and Automation (ICRA).