Fast Algorithms for Solving SDPs on Graphs SPUR Final Paper, Summer 2014
Yibo Gao, Yuzhou Gu, Adrian Vladu, Richard Peng · 2014
Semidefinite programming (SDP) is a basic optimization primitive, which has been successfully applied to many combinatorial graph algorithms. Unfortunately, in the era of big data, standard methods for solving SDP’s (Interior Point, Ellipsoid) are prohibitively slow. Instead of focusing on these, we shift our attention to first order methods, which appear to be very fast for practical purposes. It turns out that simply by applying mirror descent, one can solve SDP’s within accuracy using O( −2) iterations, each of them consisting of simple matrix operations. However, the standard setup for mirror descent has the fundamental flaw that iterations are computationally expensive. In this work, we consider the SDP relaxation for MAXCUT, and attempt to provide an efficient algorithm for solving it, which takes into account the sparsity of the input. We provide a different (and simpler) setup for mirror descent in hope of achieving cheaper iterations.