Fast Semidefinite Programming In The Large

Convex relaxations based upon semidefinite programming provide a powerful class of techniques for addressing challenging optimization problems across a broad spectrum of disciplines, including combinatorics, semialgebraic geometry, control theory, and statistics. However, the high memory and per-iteration computational cost of standard semidefinite programming algorithms prevent these methods from scaling effectively to problems involving more than a few thousand dimensions, thus limiting the scope of their applicability. In this informal talk, we will describe recent advances in the design of specialized semidefinite programming algorithms that are capable of efficiently solving a broad class of suitably-structured semidefinite relaxations orders of magnitude faster than standard techniques, and report recent numerical experience in the application of these methods to solve large-scale (ten- to hundred-thousand-dimensional) semidefinite relaxations arising in real-time robotic perception tasks. Attendees can expect to come away with concrete numerical approaches that they can apply in their own research.