Scalable Semidefinite Programming

Alp Yurtsever; Joel A. Tropp; Olivier Fercoq; Madeleine Udell; Volkan Cevher

doi:10.1137/19M1305045

Scalable Semidefinite Programming

Alp Yurtsever
, Joel A. Tropp
, Olivier Fercoq
, Madeleine Udell
, Volkan Cevher

ENAC-IIC-GEL
Massachusetts Institute of Technology
California Institute of Technology Division of Engineering and Applied Science
Cornell University College of Engineering

Research output: Contribution to journal › Article › peer-review

97 Citations (Scopus)

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 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¹⁴ entries.

Original language	English
Pages (from-to)	171-200
Number of pages	30
Journal	SIAM Journal on Mathematics of Data Science
Volume	3
Issue number	1
DOIs	https://doi.org/10.1137/19M1305045
Publication status	Published - 1 Jan 2020

Keywords

augmented Lagrangian
conditional gradient method
convex optimization
dimension reduction
first-order method
randomized linear algebra
semidefinite programming
sketching

Access to Document

10.1137/19M1305045

Cite this

@article{532ccc8db51d47f1a45424e00cf4df69,

title = "Scalable Semidefinite Programming",

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 MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over 1014 entries.",

keywords = "augmented Lagrangian, conditional gradient method, convex optimization, dimension reduction, first-order method, randomized linear algebra, semidefinite programming, sketching",

author = "Alp Yurtsever and Tropp, \{Joel A.\} and Olivier Fercoq and Madeleine Udell and Volkan Cevher",

year = "2020",

month = jan,

day = "1",

doi = "10.1137/19M1305045",

language = "English",

volume = "3",

pages = "171--200",

journal = "SIAM Journal on Mathematics of Data Science",

issn = "2577-0187",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Scalable Semidefinite Programming

AU - Yurtsever, Alp

AU - Tropp, Joel A.

AU - Fercoq, Olivier

AU - Udell, Madeleine

AU - Cevher, Volkan

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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 MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over 1014 entries.

AB - 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 MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over 1014 entries.

KW - augmented Lagrangian

KW - conditional gradient method

KW - convex optimization

KW - dimension reduction

KW - first-order method

KW - randomized linear algebra

KW - semidefinite programming

KW - sketching

UR - https://www.scopus.com/pages/publications/105009994307

U2 - 10.1137/19M1305045

DO - 10.1137/19M1305045

M3 - Article

AN - SCOPUS:105009994307

SN - 2577-0187

VL - 3

SP - 171

EP - 200

JO - SIAM Journal on Mathematics of Data Science

JF - SIAM Journal on Mathematics of Data Science

IS - 1

ER -

Scalable Semidefinite Programming

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this