A Scalable Frank-Wolfe-Based Algorithm for the Max-Cut SDP

We consider the problem of solving large-scale instances of the Max-Cut semidefinite program (SDP), i.e., optimizing a linear function over n×n positive semidefinite (PSD) matrices with unit diagonal. When the cost matrix is PSD, we show how to exactly reformulate the problem as maximizing a smooth concave function over PSD matrices with unit trace. By applying the Frank-Wolfe method, we obtain a simple algorithm that is compatible with recent samplingbased techniques to solve SDPs using low memory. We demonstrate the practical performance of our method on 10 6 × 10 6 instances of the max-cut SDP with costs having up to 5 × 10 6 non-zero entries. Theoretically, we show that our method solves problems with diagonally dominant costs to relative error ϵ in O(nϵ -1 ) calls to a randomized approximate largest eigenvalue subroutine, each of which succeeds with high probability after O(log(n)ϵ -1/2 ) matrix-vector multiplications with the cost matrix.