Scalable Convex Optimization with Applications to Semidefinite Programming

Semidefinite programming is a powerful framework from convex optimization that has striking potential for data science applications. Even so, practitioners often critique this approach by asserting that it is not possible to solve semidefinite programs at the scale demanded by real-world applications. As a result, there is a recent trend where heuristics with unverifiable assumptions are overtaking more rigorous, conventional optimization techniques. We argue that convex optimization did not reach yet its limits of scalability. In particular, we present a new optimization algorithm that can solve large semidefinite programming instances with low-rank solutions to moderate accuracy using limited arithmetic and minimal storage. 

Joint work with Joel Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher.