{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:44:48Z","timestamp":1783579488145,"version":"3.55.0"},"reference-count":129,"publisher":"Annual Reviews","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annu. Rev. Control Robot. Auton. Syst."],"published-print":{"date-parts":[[2020,5,3]]},"abstract":"<jats:p> Historically, scalability has been a major challenge for the successful application of semidefinite programming in fields such as machine learning, control, and robotics. In this article, we survey recent approaches to this challenge, including those that exploit structure (e.g., sparsity and symmetry) in a problem, those that produce low-rank approximate solutions to semidefinite programs, those that use more scalable algorithms that rely on augmented Lagrangian techniques and the alternating-direction method of multipliers, and those that trade off scalability with conservatism (e.g., by approximating semidefinite programs with linear and second-order cone programs). For each class of approaches, we provide a high-level exposition, an entry point to the corresponding literature, and examples drawn from machine learning, control, or robotics. We also present a list of software packages that implement many of the techniques discussed in the review. Our hope is that this article will serve as a gateway to the rich and exciting literature on scalable semidefinite programming for both theorists and practitioners. <\/jats:p>","DOI":"10.1146\/annurev-control-091819-074326","type":"journal-article","created":{"date-parts":[[2019,12,24]],"date-time":"2019-12-24T18:38:40Z","timestamp":1577212720000},"page":"331-360","source":"Crossref","is-referenced-by-count":77,"title":["Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics"],"prefix":"10.1146","volume":"3","author":[{"given":"Anirudha","family":"Majumdar","sequence":"first","affiliation":[{"name":"Department of Mechanical and Aerospace Engineering, Princeton University, Princeton, New Jersey 08544, USA;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georgina","family":"Hall","sequence":"additional","affiliation":[{"name":"Decision Sciences, INSEAD, 77300 Fontainebleau, France;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amir Ali","family":"Ahmadi","sequence":"additional","affiliation":[{"name":"Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544, USA;"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"22","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1137\/050645506"},{"key":"B5","author":"Hall G","year":"2018","journal-title":"Optimization over nonnegative and convex polynomials with and without semidefinite programming"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"B8","first-page":"192","volume":"3","author":"Ahmadi AA","year":"2019","journal-title":"SIAM J. Appl. Algebr. Geom."},{"key":"B9","author":"Parrilo PA","year":"2000","journal-title":"Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1203-y"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.35"},{"key":"B13","unstructured":"Ding L, Yurtsever A, Cevher V, Tropp JA, Udell M. 2019. An optimal-storage approach to semidefinite programming using approximate complementarity. arXiv:1902.03373 [math.OC]"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1080\/10556780903191165"},{"key":"B15","unstructured":"Yurtsever A, Fercoq O, Cevher V. 2019. A conditional gradient-based augmented Lagrangian framework. arXiv:1901.04013 [math.OC]"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1137\/110825844"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2012.656114"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897529"},{"key":"B19","unstructured":"Sun J. 2019. Provable nonconvex methods\/algorithms. https:\/\/sunju.org\/research\/nonconvex"},{"key":"B20","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry","author":"Blekherman G","year":"2013"},{"key":"B21","unstructured":"Hall G. 2019. Engineering and business applications of sum of squares polynomials. arXiv:1906.07961 [math.OC]"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1993.42.42045"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(88)90240-6"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2726578"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(84)90207-6"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366218"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0402-6"},{"key":"B28","author":"Fujisawa K","year":"2009","journal-title":"User's manual for SparseCoLO: conversion methods for sparse conic-form linear optimization problems"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2014.6859255"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7799333"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01366-3"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1137\/S105262340240851X"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-010-0016-2"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1137\/130926924"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2015.7402462"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2015.7403152"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1137\/15M1011020"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2305934"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.2172\/947970"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-017-0121-6"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1007\/s13675-015-0050-y"},{"key":"B42","doi-asserted-by":"crossref","unstructured":"Mangelson JG, Liu J, Eustice RM, Vasudevan R. 2018. Guaranteed globally optimal planar pose graph and landmark SLAM via sparse-bounded sums-of-squares programming. arXiv:1809.07744 [cs.RO]","DOI":"10.1109\/ICRA.2019.8794454"},{"key":"B43","volume-title":"Probabilistic Robotics","author":"Thrun S","year":"2005"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918784361"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2003.12.011"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2008.07.025"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.01.025"},{"key":"B48","author":"Permenter FN","year":"2017","journal-title":"Reduction methods in semidefinite and conic optimization"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1007\/b96977"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2007.10.004"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29928-0"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1561\/2400000011"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(81)90138-4"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-7621-4_28"},{"key":"B55","unstructured":"Kungurtsev V, Marecek J. 2018. A two-step pre-processing for semidefinite programming. arXiv:1806.10868 [math.OC]"},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7798342"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1137\/090759392"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-019-00164-4"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574037"},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.2.339"},{"key":"B61","doi-asserted-by":"publisher","DOI":"10.1561\/2400000009"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2009.2035722"},{"key":"B63","first-page":"3","volume-title":"Proceedings of KDD Cup and Workshop 2007","author":"Bennett J","year":"2007"},{"key":"B64","first-page":"235","volume-title":"Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics","author":"Kulis B","year":"2007"},{"key":"B65","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0352-8"},{"key":"B66","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589116"},{"key":"B67","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0564-1"},{"key":"B68","first-page":"406","volume-title":"Advances in Neural Information Processing Systems 24","author":"Boumal N","year":"2011"},{"key":"B69","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-005-0179-9"},{"key":"B70","volume-title":"Optimization Algorithms on Matrix Manifolds","author":"Absil PA","year":"2009"},{"key":"B71","doi-asserted-by":"publisher","DOI":"10.1137\/080731359"},{"key":"B72","first-page":"2757","volume-title":"Advances in Neural Information Processing Systems 29","author":"Boumal N","year":"2016"},{"key":"B73","doi-asserted-by":"crossref","unstructured":"Boumal N, Voroninski V, Bandeira AS. 2018. Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs. arXiv:1804.02008 [math.OC]","DOI":"10.1002\/cpa.21830"},{"key":"B74","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/imanum\/drx080","volume":"39","author":"Boumal N","year":"2018","journal-title":"IMA J. Numer. Anal."},{"key":"B75","doi-asserted-by":"publisher","DOI":"10.1080\/02331934.2013.836650"},{"key":"B76","first-page":"1455","volume":"15","author":"Boumal N","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"B77","unstructured":"Mei S, Misiakiewicz T, Montanari A, Oliveira RI. 2017. Solving SDPs for synchronization and maxcut problems via the Grothendieck inequality. arXiv:1703.08729 [math.OC]"},{"key":"B78","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-017-9365-9"},{"key":"B79","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2632149"},{"key":"B80","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7353364"},{"key":"B81","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2544304"},{"key":"B82","unstructured":"Erdogdu MA, Ozdaglar A, Parrilo PA, Vanli ND. 2018. Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs. arXiv:1807.04428 [math.OC]"},{"key":"B83","unstructured":"Wang PW, Chang WC, Kolter JZ. 2017. The mixing method: coordinate descent for low-rank semidefinite programming. arXiv:1706.00476 [math.OC]"},{"key":"B84","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"B85","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78773-0_27"},{"key":"B86","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22015-9"},{"key":"B87","unstructured":"Yurtsever A, Udell M, Tropp JA, Cevher V. 2017. Sketchy decisions: convex low-rank matrix optimization with optimal storage. arXiv:1702.06838 [math.OC]"},{"key":"B88","doi-asserted-by":"publisher","DOI":"10.1137\/15M104726X"},{"key":"B89","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-016-0892-3"},{"key":"B90","doi-asserted-by":"publisher","DOI":"10.1137\/080718206"},{"key":"B91","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0082-6"},{"key":"B92","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"B93","author":"Sturm J","year":"2001","journal-title":"Lehigh University"},{"key":"B94","author":"Mosek","year":"2019","journal-title":"Mosek"},{"key":"B95","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970395"},{"key":"B96","author":"Toh KC","journal-title":"Carnegie Mellon University"},{"key":"B97","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1.2.97"},{"key":"B98","doi-asserted-by":"publisher","DOI":"10.1137\/050641983"},{"key":"B99","unstructured":"Szegedy C, Zaremba W, Sutskever I, Bruna J, Erhan D, et al. 2013. Intriguing properties of neural networks. arXiv:1312.6199 [cs.CV]"},{"key":"B100","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP.2016.36"},{"key":"B101","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.485"},{"key":"B102","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.17"},{"key":"B103","unstructured":"Tjeng V, Xiao K, Tedrake R. 2017. Evaluating robustness of neural networks with mixed integer programming. arXiv:1711.07356 [cs.LG]"},{"key":"B104","unstructured":"Wong E, Kolter JZ. 2017. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv:1711.00851 [cs.LG]"},{"key":"B105","unstructured":"Liu C, Arnon T, Lazarus C, Barrett C, Kochenderfer MJ. 2019. Algorithms for verifying deep neural networks. arXiv:1903.06758 [cs.LG]"},{"key":"B106","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-2012-0525"},{"key":"B107","unstructured":"Xiang W, Musau P, Wild AA, Lopez DM, Hamilton N, et al. 2018. Verification for machine learning, autonomy, and neural networks survey. arXiv:1810.01989 [cs.AI]"},{"key":"B108","first-page":"6367","volume-title":"Advances in Neural Information Processing Systems 31","author":"Wang S","year":"2018"},{"key":"B109","first-page":"10877","volume-title":"Advances in Neural Information Processing Systems 31","author":"Raghunathan A","year":"2018"},{"key":"B110","unstructured":"Qin C, O'Donoghue B, Bunel R, Stanforth R, Gowal S, et al. 2019. Verification of non-linear specifications for neural networks. arXiv:1902.09592 [cs.LG]"},{"key":"B111","doi-asserted-by":"crossref","unstructured":"Fazlyab M, Morari M, Pappas GJ. 2019. Safety verification and robustness analysis of neural networks via quadratic constraints and semidefinite programming. arXiv:1903.01287 [math.OC]","DOI":"10.1109\/TAC.2020.3046193"},{"key":"B112","first-page":"749","volume":"6","author":"Ger\u0161gorin SA","year":"1931","journal-title":"Bull. Acad. Sci. URSS Classe Sci. Math."},{"key":"B113","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/685\/13712"},{"key":"B114","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2014.7039413"},{"key":"B115","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-015-0894-3"},{"key":"B116","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12598-0_1"},{"key":"B117","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0962"},{"key":"B118","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2016.04.004"},{"key":"B119","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1975.57.15"},{"key":"B120","doi-asserted-by":"publisher","DOI":"10.1109\/CACSD.2004.1393890"},{"key":"B121","first-page":"83","volume":"17","author":"Diamond S","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"B122","author":"Stahlberg M","year":"2018","journal-title":"GitLab"},{"key":"B123","author":"Posa M","year":"2013","journal-title":"GitHub"},{"key":"B124","doi-asserted-by":"publisher","DOI":"10.1137\/15M1020575"},{"key":"B125","author":"O'Donoghue B","year":"2017","journal-title":"GitHub"},{"key":"B126","first-page":"4755","volume":"17","author":"Townsend J","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"B127","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1169-9"},{"key":"B128","author":"Papachristodoulou A","year":"2013","journal-title":"Caltech"},{"key":"B129","author":"JuliaOpt","year":"2019","journal-title":"GitHub"}],"container-title":["Annual Review of Control, Robotics, and Autonomous Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.annualreviews.org\/doi\/pdf\/10.1146\/annurev-control-091819-074326","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,8]],"date-time":"2021-10-08T10:31:47Z","timestamp":1633689107000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.annualreviews.org\/doi\/10.1146\/annurev-control-091819-074326"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,3]]},"references-count":129,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,5,3]]}},"alternative-id":["10.1146\/annurev-control-091819-074326"],"URL":"https:\/\/doi.org\/10.1146\/annurev-control-091819-074326","relation":{},"ISSN":["2573-5144","2573-5144"],"issn-type":[{"value":"2573-5144","type":"print"},{"value":"2573-5144","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,3]]}}}