Fast Semidefinite Programming In The Large

Tuesday, April 16, 2019 - 3:00pm to Wednesday, April 17, 2019 - 3:55pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

David Rosen



Building and Room Number

LIDS Lounge


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.


David M. Rosen is a postdoctoral associate in the Laboratory for Information and Decision Systems (LIDS) at the Massachusetts Institute of Technology, working with Professors Pablo Parrilo, Alexandre Megretski, and Russ Tedrake. He holds the degrees of ScD in Computer Science from the Massachusetts Institute of Technology (2016), MA in Mathematics from the University of Texas at Austin (2010), and BS in Mathematics from the California Institute of Technology (2008). His research interests are in the mathematical foundations of machine perception and control, with a particular focus on algorithms for optimization and probabilistic inference.