Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 21, 2020 | Submitted
Report Open

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 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.

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.

Attached Files

Submitted - 1912.02949.pdf

Files

1912.02949.pdf
Files (4.0 MB)
Name Size Download all
md5:0da52ca5f7ed360ba0c17ac812267ecd
4.0 MB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 23, 2023