A Caltech Library Service

Scalable Semidefinite Programming

Yurtsever, Alp and Tropp, Joel A. and Fercoq, Olivier and Udell, Madeleine and Cevher, Volkan (2019) Scalable Semidefinite Programming. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct algorithm for solving large SDP problems by economizing on both the storage and the arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop, the algorithm can handle SDP instances where the matrix variable has over 10¹³ entries.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Tropp, Joel A.0000-0003-1024-1791
Fercoq, Olivier0000-0002-3393-9757
Udell, Madeleine0000-0002-3985-915X
Additional Information:Submitted to the editors 6 December 2019. Funding: VC and AY have received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme under the grant agreement number 725594 (time-data) and the Swiss National Science Foundation (SNSF) under the grant number 200021_178865/1. JAT gratefully acknowledges ONR Awards N00014-11-1-0025, N00014-17-1-2146, and N00014-18-1-2363. MU gratefully acknowledges DARPA Award FA8750-17-2-0101.
Funding AgencyGrant Number
European Research Council (ERC)725594
Swiss National Science Foundation (SNSF)200021_178865/1
Office of Naval Research (ONR)N00014-11-1-0025
Office of Naval Research (ONR)N00014-17-1-2146
Office of Naval Research (ONR)N00014-18-1-2363
Defense Advanced Research Projects Agency (DARPA)FA8750-17-2-0101
Subject Keywords:Augmented Lagrangian, conditional gradient method, convex optimization, dimension reduction, first-order method, Frank-Wolfe method, MaxCut, phase retrieval, quadratic assignment, randomized linear algebra, semidefinite programming, sketching
Classification Code:AMS subject classifications. Primary: 90C22, 65K05. Secondary: 65F99.
Record Number:CaltechAUTHORS:20201218-154437706
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:107221
Deposited By: George Porter
Deposited On:21 Dec 2020 15:36
Last Modified:21 Dec 2020 15:36

Repository Staff Only: item control page