Scalable Semidefinite Programming
Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell, Volkan Cevher
Abstract
Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct randomized algorithm for solving large, weakly constrained SDP problems by economizing on the storage and arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of \sf MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over $10^{14}$ entries.
Topics & Concepts
Semidefinite programmingLaptopConvex optimizationComputer scienceMatrix (chemical analysis)Range (aeronautics)Quadratic programmingMathematical optimizationMathematicsSemidefinite embeddingScalabilityQuadratic equationQuadratically constrained quadratic programAlgorithmOptimization problemRegular polygonLinear programmingMatrix completionVariable (mathematics)Matrix multiplicationSparse matrixSimple (philosophy)Positive-definite matrixEfficient algorithmRandomized algorithmAdvanced Optimization Algorithms ResearchStochastic Gradient Optimization TechniquesMatrix Theory and Algorithms