Skip to Main content Skip to Navigation
Journal articles

Scalable Semidefinite Programming

Alp Yurtsever 1 Joel A. Tropp 2 Olivier Fercoq 3, 4 Madeleine Udell 5 Volkan Cevher 1
1 LIONS - Laboratory for Information and Inference Systems
2 Caltech Division of Engineering and Applied Science
3 S2A - Signal, Statistique et Apprentissage
LTCI - Laboratoire Traitement et Communication de l'Information
4 LTCI - Laboratoire Traitement et Communication de l'Information
5 ORIE - School of Operations Research and Information Engineering
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 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^{13}$ entries.
Document type :
Journal articles
Complete list of metadata
https://hal.telecom-paris.fr/hal-02493338
Contributor : Olivier Fercoq Connect in order to contact the contributor
Submitted on : Thursday, February 27, 2020 - 4:50:17 PM
Last modification on : Tuesday, October 19, 2021 - 11:16:16 AM

Links full text

openaccess

Identifiers

Collections

INSMI | INSTITUT-TELECOM | TDS-MACS | IDS | LTCI | S2A

Citation

Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell, Volkan Cevher. Scalable Semidefinite Programming. SIAM Journal on Mathematics of Data Science, Society for Industrial and Applied Mathematics, 2021, ⟨10.1137/19M1305045⟩. ⟨hal-02493338⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

102