Semidefinite Relaxations for Robot Perception and Control: From Theory to Practice and Back
Abstract:
Many problems in robot perception, control, and planning can be formulated as nonconvex polynomial optimization problems (POPs). The Moment–SOS (sums-of-squares) hierarchy provides a principled approach by relaxing a nonconvex POP into a sequence of convex semidefinite programs (SDPs) whose optimal values converge to that of the original problem. Despite its theoretical elegance, the framework is often viewed as impractical due to the need to solve large-scale and ill-conditioned SDPs.
In the first part of this talk, I will show how problem-specific structure in robotics can be exploited to make Moment–SOS relaxations practical at scale. On the perception side, I will present XM, our structure-from-motion pipeline that leverages monocular depth prediction to cast bundle adjustment as a polynomial optimization problem. Using GPU-accelerated low-rank Riemannian optimization, XM solves bundle adjustment instances with thousands to tens of thousands of images. On the control side, I will introduce SPOT, a trajectory planning pipeline that exploits sparsity inherent in robot motion planning problems, such as Markov and kinematic chain structure. With a GPU-accelerated ADMM solver, SPOT is able to generate near–globally optimal trajectories within seconds, including contact-rich motions.
In the second part, I will turn to theory, briefly highlighting our recent work on understanding and accelerating the convergence of first-order methods for SDPs. This includes proving local linear convergence of ADMM, designing a composite polynomial filter for approximate projection onto the positive semidefinite cone, and analyzing the slow-convergence regions of ADMM.
Bio:
Heng Yang is an Assistant Professor of Electrical Engineering in the School of Engineering and Applied Sciences (SEAS) at Harvard University. He received his Ph.D. from MIT in 2022 and his B.S. from Tsinghua University in 2015. He leads the Harvard Computational Robotics Group, which is broadly interested in the intersection of theory and practice, with a focus on computational algorithms that are robust, efficient, and equipped with strong performance guarantees. His work has been recognized with multiple awards, including the Best Systems Paper Award at RSS 2025, a 2025 Best Paper Award Finalist from the IEEE Technical Committee on Model-based Optimization for Robotics, a Best Paper Award Finalist at RSS 2021, the Best Paper Award in Robot Vision at ICRA 2020, a Best Paper Award Honorable Mention from IEEE Robotics and Automation Letters in 2020, and recognition as an RSS 2021 Pioneer.