{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:24:21Z","timestamp":1787340261639,"version":"build-2736575974"},"reference-count":74,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-17-2-0101"],"award-info":[{"award-number":["FA8750-17-2-0101"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N-00014-11-1002"],"award-info":[{"award-number":["N-00014-11-1002"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N-00014-17-12146"],"award-info":[{"award-number":["N-00014-17-12146"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N-00014-18-12363"],"award-info":[{"award-number":["N-00014-18-12363"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["725594"],"award-info":[{"award-number":["725594"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00c3\u00b6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["P2ELP2 187955"],"award-info":[{"award-number":["P2ELP2 187955"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00c3\u00b6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["IIS-1846088"],"award-info":[{"award-number":["IIS-1846088"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00c3\u00b6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021_178865\/1"],"award-info":[{"award-number":["200021_178865\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>This paper develops a new storage-optimal algorithm that provably solves almost all semidefinite programs (SDPs). This method is particularly effective for weakly constrained SDPs under appropriate regularity conditions. The key idea is to formulate an approximate complementarity principle: Given an approximate solution to the dual SDP, the primal SDP has an approximate solution whose range is contained in the eigenspace with small eigenvalues of the dual slack matrix. For weakly constrained SDPs, this eigenspace has very low dimension, so this observation significantly reduces the search space for the primal solution. This result suggests an algorithmic strategy that can be implemented with minimal storage: (1) solve the dual SDP approximately; (2) compress the primal SDP to the eigenspace with small eigenvalues of the dual slack matrix; (3) solve the compressed primal SDP. The paper also provides numerical experiments showing that this approach is successful for a range of interesting large-scale SDPs.<\/jats:p>","DOI":"10.1137\/19m1244603","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T10:58:34Z","timestamp":1635418714000},"page":"2695-2725","source":"Crossref","is-referenced-by-count":16,"title":["An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity"],"prefix":"10.1137","volume":"31","author":[{"given":"Lijun","family":"Ding","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alp","family":"Yurtsever","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Volkan","family":"Cevher","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1024-1791","authenticated-orcid":true,"given":"Joel A.","family":"Tropp","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3985-915X","authenticated-orcid":true,"given":"Madeleine","family":"Udell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"atypb3","unstructured":"F. Alizadeh,\n                      Combinatorial Optimization with Interior Point Methods and Semi-definite Matrices\n                      , Ph.D. thesis, University of Minnesota, 1991."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/0805002"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614432"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623496304700"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijepes.2007.12.003"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574037"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/007\/0154876"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497328008"},{"key":"atypb12","first-page":"2757","author":"Boumal N.","year":"2016","journal-title":"Advances in Neural Information Processing Systems"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan,\n                      Linear Matrix Inequalities in System and Control Theory\n                      , Stud. Appl. Numer. Math. 15, SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611970777"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0352-8"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0564-1"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/151005099"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/27\/1\/015005"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2429594"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824783"},{"key":"atypb24","first-page":"221","author":"Diamond S.","year":"2016","journal-title":"New York"},{"key":"atypb25","unstructured":"L. Ding and M. Udell,\n                      On the Regularity and Conditioning of Low Rank Semidefinite Programs\n                      , preprint,arXiv:2002.10673, 2020."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0889"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/15M1034283"},{"key":"atypb30","unstructured":"D. Gabay and B. Mercier,\n                      A Dual Algorithm for the Solution of Non linear Variational Problems via Finite Element Approximation\n                      , Institut de Recherche d'Informatique et d'Automatique, 1975."},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"R. Glowinski and A. Marroco,\n                      Sur l'approximation, par \u00e9l\u00e9ments finis d'ordre un, et la r\u00e9solution, par p\u00e9nalisation-dualit\u00e9 d'une classe de probl\u00e8mes de dirichlet non lin\u00e9aires\n                      , Revue fran\u00e7aise d'automatique, informatique, recherche op\u00e9rationnelle. Analyse num\u00e9rique, 9 (1975), pp. 41-76.","DOI":"10.1051\/m2an\/197509R200411"},{"key":"atypb32","first-page":"422","author":"Goemans M. X.","year":"1994","journal-title":"ACM"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"atypb35","first-page":"306","author":"Hazan E.","year":"2008","journal-title":"New York"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497328987"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1381"},{"key":"atypb38","unstructured":"M. Jaggi,\n                      Revisiting Frank-Wolfe: Projection-free sparse convex optimization\n                      , in Proceedings of the 30th International Conference on Machine Learning, 2013, pp. 427-435."},{"key":"atypb39","unstructured":"D. Johnson, G. Pataki, and F. Alizadeh,\n                      The Seventh DIMACs Implementation Challenge: Semidefinite and Related Optimization Problems\n                      , DIMACS, Piscataway, NJ, 2000."},{"key":"atypb40","unstructured":"P. R. Johnstone and P. Moulin,\n                      Faster Subgradient Methods for Functions with H\u00f6lderian Growth\n                      , preprint, arXiv:1704.00196, 2017."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2046205"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1561\/2400000009"},{"key":"atypb44","first-page":"787","volume":"6","author":"Levitin E. S.","year":"1966","journal-title":"Zh. Vychisl. Mat. Mat. Fiz."},{"key":"atypb45","unstructured":"K. Y. Levy, A. Yurtsever, and V. Cevher,\n                      Online Adaptive Methods, Universality and Acceleration\n                      , preprint, arXiv:1809.02864, 2018."},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2014.2322051"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/070704575"},{"key":"atypb48","first-page":"712","author":"Mathieu C.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb49","unstructured":"A. Mosek,\n                      The Mosek Optimization Software\n                      ,http:\/\/www.mosek.com, 2010."},{"key":"atypb50","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Appl. Optim. 87, Springer, New York, 2013."},{"key":"atypb51","unstructured":"Y. Nesterov and A. Nemirovski,\n                      Self-Concordant Functions and Polynomial Time Methods in Convex Programming\n                      , USSR Academy of Sciences, Central Economic & Mathematical Institute, Moscow, 1989."},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovskii,\n                      Interior-Point Polynomial Algorithms in Convex Programming\n                      , Stud. Appl. Numer. Math. 13, SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-016-0892-3"},{"key":"atypb54","unstructured":"B. O'Donoghue, E. Chu, N. Parikh, and S. Boyd,\n                      SCS: Splitting Conic Solver, Version\n                      2.0.2,https:\/\/github.com\/cvxgrp\/scs, 2017."},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.2.339"},{"key":"atypb56","unstructured":"N. Rao, P. Shah, and S. Wright,\n                      Conditional gradient with enhancement and truncation for atomic-norm regularization\n                      , in NIPS Workshop on Greedy Algorithms, 2013."},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"atypb58","unstructured":"J. Renegar,\n                      Efficient First-Order Methods for Linear Programming and Semidefinite Programming\n                      , preprint, arXiv:1409.5832, 2014."},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1137\/0314056"},{"key":"atypb60","unstructured":"A. P. Ruszczy\u0144ski and A. Ruszczynski,\n                      Nonlinear Optimization\n                      , Princeton University Press, Princeton, NJ, 2006."},{"key":"atypb61","first-page":"545","author":"Srebro N.","year":"2005","journal-title":"New York"},{"key":"atypb62","doi-asserted-by":"crossref","unstructured":"J. F. Sturm,\n                      Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones\n                      , Optim. Methods Softw., 11 (1999), pp. 625-653.","DOI":"10.1080\/10556789908805766"},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623498338606"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2019.1576176"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492901000071"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805762"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0738-9"},{"key":"atypb69","unstructured":"I. Waldspurger and A. Waters,\n                      Rank Optimality for the Burer-Monteiro Factorization\n                      , preprint, arXiv:1812.03046, 2018."},{"key":"atypb70","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-010-0017-1"},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/asv008"},{"key":"atypb72","first-page":"7272","author":"Yurtsever A.","year":"2019","journal-title":"International Conference on Machine Learning"},{"key":"atypb73","first-page":"5727","author":"Yurtsever A.","year":"2018","journal-title":"International Conference on Machine Learning"},{"key":"atypb74","first-page":"381","author":"Yurtsever A.","year":"2015","journal-title":"Multi-Sensor Adaptive Processing, IEEE"},{"key":"atypb75","unstructured":"A. Yurtsever, J. Tropp, O. Fercoq, M. Udell, and V. Cevher,\n                      Scalable Semidefinite Programming\n                      , preprint, arXiv:1912.02949, 2019."},{"key":"atypb76","first-page":"1188","author":"Yurtsever A.","year":"2017","journal-title":"International Conference on Artificial Intelligence and Statistics"},{"key":"atypb77","doi-asserted-by":"publisher","DOI":"10.1137\/080718206"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1244603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:27:21Z","timestamp":1787336841000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1244603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":74,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1244603"],"URL":"https:\/\/doi.org\/10.1137\/19m1244603","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}