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
- Eprint ID
- 107221
- Resolver ID
- CaltechAUTHORS:20201218-154437706
- 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
- Created
-
2020-12-21Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field