Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This survey argues that four complementary families of methods (structure exploitation, low-rank factorization, first-order splitting, and conservative LP/SOCP relaxations) now make large semidefinite programs practical in machine…

desk verdict A well-organized, genuinely useful entry point to the scalable SDP literature, but it overstates the Burer–Monteiro guarantee by a factor of two and has a sign error in Hazan's Frank-Wolfe update; both are fixable and should be corrected before publication. read the letter →

arxiv 1908.05209 v3 pith:EU4SKYB4 submitted 2019-08-14 math.OC cs.LGcs.ROcs.SYeess.SY

Anirudha Majumdar , Georgina Hall , Amir Ali Ahmadi This is my paper · ORCID
classification math.OCcs.LGcs.ROcs.SYeess.SY MSC 90C2290C25
keywords semidefiniteprogrammingscalabilitysumofsquareschordalsparsitylow-rankfactorizationADMMDSOS/SDSOSoptimizationcontrolandrobotics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Semidefinite programs (SDPs) are convex optimization problems over positive semidefinite matrices, and they are famously expressive but historically slow: interior-point solvers require dense matrix operations that blow up in time and memory. This survey claims that a recent wave of methods has changed that situation, and that the practical routes to scalable SDPs fall into four complementary families: exploiting structure such as sparsity and symmetry, seeking low-rank solutions through factorizations, using first-order splitting methods (ADMM and augmented Lagrangian), and trading off optimality for feasibility with linear and second-order cone approximations. A practitioner reading the survey is meant to come away with a decision guide: use structure when it is present, low-rank methods when low-rank solutions exist or are desired, first-order methods when approximate feasibility is acceptable, and conservative LP/SOCP relaxations when guaranteed feasibility matters more than optimality. The survey also curates a software list keyed to each route. The paper's claim is not that any single method wins, but that the barriers that made SDPs prohibitive in machine learning, control, and robotics are now attackable by one of these four strategies.

What carries the argument

The load-bearing machinery is a portfolio of four identities and algorithmic templates. Chordal sparsity rests on a decomposition theorem (Proposition 1): a positive semidefinite matrix with a chordal sparsity pattern is a sum of positive semidefinite matrices supported on maximal cliques, which turns one big semidefinite constraint into several small ones plus equalities. Low-rank methods rest on the factorization $X=VV^T$ with $V\in\mathbb{R}^{n\times r}$, which cuts storage from $O(n^2)$ to $O(nr)$ and converts the conic problem into a nonconvex smooth one. The ADMM family rests on rewriting primal and dual SDPs as a homogeneous self-dual embedding and then applying operator splitting updates. The conservative family rests on diagonally dominant (dd) and scaled diagonally dominant (sdd) matrix cones and their polynomial counterparts (dsos and sdsos polynomials), which are semidefinite-representable inner approximations of the PSD cone whose membership constraints are LPs and SOCPs. Each template is what carries the corresponding scalability gain in the survey's narrative.

What would settle it

Run the four families head-to-head on a standardized suite of large SDP instances drawn from the survey's own use cases (sparse Lyapunov analysis with clique size below 15, robust PCA on a dense matrix, 100x100 sparse PCA, planar pose-graph SLAM) and compare wall-clock time to fixed accuracy against interior-point solvers. If chordal decomposition does not deliver speedups near the reported factor, or SDSOS loses far more than 2-3% optimality, or ADMM's accuracy degrades well beyond $3\times10^{-4}$ reconstruction error, the survey's decision guide fails.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is organizational: the many recent scalability improvements for SDPs cluster into four approaches with different cost-quality tradeoffs. Structure exploitation uses chordal sparsity and symmetry to replace one large semidefinite constraint by many smaller ones, sometimes reducing Lyapunov synthesis runtimes by a factor of about 80. Low-rank methods factor the semidefinite variable as $X = VV^T$ and typically solve the smaller nonconvex problem with Riemannian or coordinate-descent tools, with guarantees that second-order critical points are globally optimal when the number of constraints is below a threshold. ADMM and augmented Lagrangian solvers work on the homogeneous self-dual embedding of the primal-dual pair and can handle instances where interior-point solvers run out of memory, at a small cost in accuracy (for robust PCA, under $3\times10^{-4}$ reconstruction error). Conservative relaxations replace the positive semidefinite cone with cones of diagonally dominant or scaled diagonally dominant matrices, leading to LP/SOCP problems that can be over 1000 times faster than the SDP on sparse PCA instances while sacrificing a few percent of optimality. The survey holds that these four families are largely complementary and can be combined.

Load-bearing premise

The survey's practical guidance stands or falls with the assumption that the speedups it reports from cited papers, roughly 80x for chordal Lyapunov SDPs, over 1000x for SDSOS on sparse PCA, and under $3\times10^{-4}$ reconstruction error for ADMM on robust PCA, are representative of typical instances rather than favorable ones.

Editorial extensions

If this is right

  • If the survey's map is right, a practitioner facing a large SDP should first look for chordal sparsity, symmetry, or degeneracy, since structure exploitation preserves exactness while shrinking the semidefinite blocks.
  • For SDPs with few constraints, low-rank factorization (Burer-Monteiro) is a provably safe strategy: when $m < r(r+1)/2$, a rank-$r$ optimal solution exists, and second-order critical points of the factored problem are globally optimal for almost all objectives.
  • When approximate solutions with slightly violated constraints are tolerable, ADMM and augmented Lagrangian solvers can reach instances that are out of memory for interior-point solvers.
  • When guaranteed feasibility is required and speed matters more than optimality, DSOS/SDSOS relaxations turn the PSD constraint into LP/SOCP constraints, and adaptive improvements (change of basis, column generation) tighten the inner approximation iteratively.
  • The four routes can be combined, for example chordal sparsity inside a first-order solver, or low-rank factorization on a sparsity-reduced SDP, which the survey explicitly encourages.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Across the four families one sees a shared pattern: replace the expensive PSD cone by a cheaper surrogate and then refine it. This suggests a general recipe the paper does not spell out: any application yielding an SDP could first try a cheap LP/SOCP inner approximation, then zoom in with low-rank or first-order refinement only where the relaxation is too loose.
  • The survey's decision guide implies a testable engineering hypothesis: a benchmark suite spanning Lyapunov synthesis, robust PCA, sparse PCA, and pose-graph SLAM should reveal that no single method dominates, but that the optimal choice is predictable from instance structure (sparsity level, number of constraints, feasibility tolerance).
  • The success of adaptive DSOS/SDSOS hierarchies hints that the boundary between exact SDP and cheap relaxation is not fixed: iterative basis changes and column generation can climb from the LP/SOCP side toward SDP accuracy, which, if pushed further, could erode the need for interior-point precision in many applications.
  • The paper explicitly sets aside nonconvex local-descent alternatives to SDP relaxations. If those methods keep improving, the practical role of SDPs in machine learning may shift from being the solver of choice to being a certifier of solutions found by other means, a shift the survey's framework does not address.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper is a survey of four families of techniques for scaling semidefinite programming: exploiting problem structure (sparsity, symmetry, facial reduction), producing low-rank solutions (Burer–Monteiro and Frank–Wolfe methods), using ADMM and augmented Lagrangian methods, and trading off conservatism for scalability via LP/SOCP relaxations (DSOS/SDSOS and adaptive variants). It additionally provides a decision guide, applications in machine learning, control, and robotics, and a software list. The paper makes no new algorithmic or theoretical claims; its value is as an entry point to the scalable SDP literature.

Significance. The survey addresses a timely and important need, and its high-level organization into four methodological families is sensible and useful. It is clearly written, gives a good overview of chordal sparsity, symmetry reduction, ADMM-based conic solvers, and the DSOS/SDSOS framework, and the software list and decision guide are potentially valuable for practitioners. The paper does not present new algorithms or reproducible experiments, so its correctness rests entirely on the accuracy of its descriptions of existing results. The two technical errors identified below both occur in Section 3, which is exactly the part of the survey that the decision guide in Section 1.1.1 directs readers to for low-rank SDPs; they are therefore load-bearing for the survey's practical value.

major comments (2)
  1. [§3.1.2, Burer–Monteiro guarantee] The stated condition for the global optimality of second-order critical points is incorrect. The text says 'if m < r(r+1)/2' then, under smoothness and compactness, every second-order critical point of Problem (11) is globally optimal for almost all C, citing [25, Theorem 2]. The theorem in [25] requires r(r+1)/2 > 2m. The survey's inequality is weaker by a factor of two and is the complement of the Barvinok–Pataki existence bound in Eq. (8), so a reader who chooses r from Eq. (8) can land precisely in the regime where spurious second-order critical points are known to occur. This overstates the scope of the 'provably recover global low-rank solutions' promise in Case 1 and undermines the corresponding guidance in Section 1.1.1. Please correct the threshold and adjust the surrounding discussion, including the claim that smoothness follows from the stated inequality.
  2. [§3.2.1, Hazan's Frank–Wolfe update] The displayed update for Hazan's algorithm is wrong. The text sets X_{k+1} = (1 − α_k) X_k + α_k (−v_k v_k^T), where v_k is the eigenvector for the maximum eigenvalue of ∇f(X_k). The correct Frank–Wolfe update on the trace-one spectrahedron is X_{k+1} = (1 − α_k) X_k + α_k v_k v_k^T, with v_k an eigenvector for the minimum eigenvalue of ∇f(X_k) (equivalently, the maximum eigenvalue of −∇f(X_k)). As printed, the update has trace 1 − 2α_k, so it violates the trace-one constraint and is not a valid Frank–Wolfe step for Problem (14). This is a local but substantive error in a central algorithm description and should be corrected.
minor comments (5)
  1. [§1.1.1] Typo: 'convservative' should be 'conservative'.
  2. [§2.2, Eq. (7)] The notation in the reduced problem reuses m both for the number of constraints and for the dimension of the reduced cone. Please use distinct symbols to avoid confusion.
  3. [§3.1.2] The sentence 'an optimal solution of rank≤k is guaranteed to exist here' uses an undefined variable k; it should refer to the factorization rank r.
  4. [§3.2.1] The accuracy statement 'f(X) ≤ f* + Ω(1/k)' should use O(1/k); Ω denotes a lower bound and is not the correct notation for an approximation guarantee.
  5. [§4.1] Reported performance figures such as the 'less than 3 × 10^-4 reconstruction error' and the order-of-magnitude speedups come from specific instances in the cited papers; a brief caveat that these numbers are instance-dependent would help practitioners calibrate expectations.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reasoning: this is an expository survey, and its few self-citations in the DSOS/SDSOS sections are presentation choices rather than load-bearing logical loops.

full rationale

The paper is a survey, not a derivation with fitted parameters or predicted quantities. Its central claim is organizational: that the four families of methods surveyed are useful routes to scalable semidefinite programming. That claim is supported by citing and summarizing external literature, not by deriving a result from an input that is itself the result. The DSOS/SDSOS material in Sections 5.1 and 5.2 is drawn heavily from the authors' own prior work, and the SPOT toolbox (also theirs) appears in the software list, but this self-citation is not load-bearing in the technical sense: the definitions of dd/sdd matrices and dsos/sdsos polynomials, Theorem 1's equivalence, and the iterative inner-approximation arguments are stated with enough mathematical content to be checked independently, and the reported speedups are presented as experimental findings from the cited papers rather than as predictions generated by this survey. The apparent rank-threshold discrepancy in Section 3.1.2, where the survey states the Burer-Monteiro guarantee under m < r(r+1)/2 while the cited theorem is often stated with r(r+1)/2 > 2m, is a correctness or accuracy concern about the survey's reporting of an external theorem, not a circularity in the survey's own derivation chain. No equation in the paper is defined in terms of its own conclusion, and no fitted parameter is renamed as a prediction. Accordingly, there is no significant circularity; the score reflects the minor, non-load-bearing self-citation presence rather than any logical circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The survey introduces no new free parameters, axioms, or entities. Its content is a summary of existing work, so the ledger contains only background assumptions about the reliability of the cited literature and the completeness of the survey's taxonomy.

assumptions (3)
  • domain assumption The cited literature is accurately summarized and the reported performance gains are representative.
    The survey's practical guidance rests on numbers such as the roughly 80x speedup in Section 2.1, the over 1000x speedup in Section 5.1, and the <3x10^-4 reconstruction error in Section 4.1, all taken from external papers.
  • domain assumption The four-way taxonomy (structure, low-rank, ADMM/augmented Lagrangian, conservative relaxation) covers the principal approaches to scalable SDPs.
    Section 1.1.1 presents this as the organizing scheme; if a major family is omitted, the survey's completeness is compromised.
  • standard math Standard convex analysis facts such as the PSD cone, chordal decomposition (Proposition 1, cited to Agler et al.), and the Burer-Monteiro factorization preserve the SDP solution set as stated.
    These results are used without proof in Sections 2 and 3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics." pith.science (2026). https://pith.science/paper/EU4SKYB4

@misc{pith2026190805209,
  author       = {Pith},
  title        = {Pith review of: A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EU4SKYB4}},
  note         = {Machine review of arXiv:1908.05209}
}
read the original abstract

Historically, scalability has been a major challenge to the successful application of semidefinite programming in fields such as machine learning, control, and robotics. In this paper, we survey recent approaches for addressing this challenge including (i) approaches for exploiting structure (e.g., sparsity and symmetry) in a problem, (ii) approaches that produce low-rank approximate solutions to semidefinite programs, (iii) more scalable algorithms that rely on augmented Lagrangian techniques and the alternating direction method of multipliers, and (iv) approaches 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 paper. Our hope is that this paper will serve as a gateway to the rich and exciting literature on scalable semidefinite programming for both theorists and practitioners.

Figures

Figures reproduced from arXiv: 1908.05209 by the authors.

Figure 1
Figure 1. Dsos and sdsos polynomials form structured subsets of sos polynomials which can [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. Figure reproduced from [7] showing improvement (in all directions) after one [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
Figure 3
Figure 3. Figure reproduced from [11] showing the successive improvement on the dd (left) [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Exploiting sparse structures and synergy designs to advance situational awareness of electrical power grid

    eess.SP 2024-12 conditional novelty 5.0 of 10

    The thesis claims that sparse threat indicators and physics-ML synergy make power grid situational awareness tools robust and efficient at scale.

Reference graph

Works this paper leans on

130 extracted references · 72 canonical work pages · cited by 1 Pith paper

  1. [25]

    Boumal, V

    N. Boumal, V. Voroninski, and A. Bandeira. The non-convex Burer-Monteiro approach works on smooth semidefinite programs. In Advances in Neural Information Processing Systems , pages 2757–2765, 2016

    2016

  2. [1]

    URL https://github.com/JuliaOpt/SumOfSquares

    Sum of Squares Programming for Julia . URL https://github.com/JuliaOpt/SumOfSquares. jl

  3. [2]

    URL https://github.com/ spot-toolbox/spotless

    Systems Polynomial Optimization Toolbox (SPOT) , 2013. URL https://github.com/ spot-toolbox/spotless. www.annualreviews.org • Scalability in Semidefinite Programming 27

    2013

  4. [3]

    URL https://docs.mosek.com/8.1/ intro/index.html

    Introducing the MOSEK Optimization Suite , 2018. URL https://docs.mosek.com/8.1/ intro/index.html

    2018

  5. [4]

    Absil, C

    P.-A. Absil, C. G. Baker, and K. A. Gallivan. Trust-region methods on Riemannian manifolds. Foundations of Computational Mathematics , 7(3):303–330, 2007

    2007

  6. [5]

    Absil, R

    P.-A. Absil, R. Mahony, and R. Sepulchre. Optimization Algorithms on Matrix Manifolds . Princeton University Press, 2009

    2009

  7. [6]

    Agler, W

    J. Agler, W. Helton, S. McCullough, and L. Rodman. Positive semidefinite matrices with a given sparsity pattern. Linear Algebra and its Applications , 107:101–149, 1988

    1988

  8. [7]

    A. A. Ahmadi and G. Hall. Sum of squares basis pursuit with linear and second order cone programming. Contemporary Mathematics, pages 27–53, 2017. Available at https://arxiv. org/pdf/1510.01597.pdf

    work page Pith review arXiv 2017

Show all 130 references
  1. [8]

    A. A. Ahmadi and G. Hall. On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity. Mathematics of Operations Research ,

  2. [9]

    A. A. Ahmadi and A. Majumdar. Some applications of polynomial optimization in operations research and real-time decision making. Optimization Letters, 10(4):709–729, 2016

    2016

  3. [10]

    A. A. Ahmadi and A. Majumdar. DSOS and SDSOS optimization: more tractable alterna- tives to sum of squares and semidefinite optimization. SIAM Journal on Applied Algebraic Geometry, 3(193), 2019

    2019

  4. [11]

    A. A. Ahmadi, S. Dash, and G. Hall. Optimization over structured subsets of positive semidef- inite matrices via column generation. Discrete Optimization, 24:129–151, 2017

    2017

  5. [12]

    M. S. Andersen, J. Dahl, and L. Vandenberghe. Implementation of nonsymmetric interior- point methods for linear optimization over sparse matrix cones. Mathematical Programming Computation, 2(3-4):167–201, 2010

    2010

  6. [13]

    M. S. Andersen, S. K. Pakazad, A. Hansson, and A. Rantzer. Robust stability analysis of sparsely interconnected uncertain systems. IEEE Transactions on Automatic Control , 59(8): 2151–2156, 2014

    2014

  7. [14]

    Arcak, C

    M. Arcak, C. Meissen, and A. Packard. Networks of Dissipative Systems: Compositional Certification of Stability, Performance, and Safety . Springer, 2016

    2016

  8. [15]

    Arora, E

    S. Arora, E. Hazan, and S. Kale. Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science , pages 339–348, 2005

    2005

  9. [16]

    Barker and D

    G. Barker and D. Carlson. Cones of diagonally dominant matrices. Pacific Journal of Math- ematics, 57(1):15–32, 1975

    1975

  10. [17]

    A. I. Barvinok. Problems of distance geometry and convex properties of quadratic maps. Discrete & Computational Geometry , 13(2):189–202, 1995

    1995

  11. [18]

    Bennett, S

    J. Bennett, S. Lanning, et al. The Netflix prize. In Proceedings of KDD cup and workshop , volume 2007, page 35. New York, NY, USA., 2007

    2007

  12. [19]

    S. J. Benson, Y. Ye, et al. DSDP5 user guide-software for semidefinite programming. Technical report, Argonne National Lab, Argonne, 2006

    2006

  13. [20]

    Bertsimas, R

    D. Bertsimas, R. M. Freund, and X. A. Sun. An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems. Optimization Methods and Software, 28(3):424–441, 2013

    2013

  14. [21]

    Blekherman, P

    G. Blekherman, P. A. Parrilo, and R. Thomas. Semidefinite Optimization and Convex Alge- braic Geometry. SIAM Series on Optimization, 2013

    2013

  15. [22]

    Borwein and H

    J. Borwein and H. Wolkowicz. Regularizing the abstract convex program. Journal of Mathe- matical Analysis and Applications , 83(2):495–530, 1981

    1981

  16. [23]

    Boumal and P.-a

    N. Boumal and P.-a. Absil. RTRMC: A Riemannian trust-region method for low-rank matrix completion. In Advances in Neural Information Processing Systems , pages 406–414, 2011

    2011

  17. [24]

    Boumal, B

    N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre. Manopt, a MATLAB toolbox for optimization on manifolds. Journal of Machine Learning Research, 15:1455–1459, 2014. URL 28 Majumdar, Hall, Ahmadi http://www.manopt.org

    2014

  18. [26]

    Boumal, P.-A

    N. Boumal, P.-A. Absil, and C. Cartis. Global rates of convergence for nonconvex optimization on manifolds. IMA Journal of Numerical Analysis , 39(1):1–33, 2018

    2018

  19. [27]

    Boumal, V

    N. Boumal, V. Voroninski, and A. S. Bandeira. Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs. arXiv preprint arXiv:1804.02008 , 2018

    2018 arXiv

  20. [28]

    S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statis- tical learning via the alternating direction method of multipliers. Foundations and Trends R© in Machine learning , 3(1):1–122, 2011

    2011

  21. [29]

    S. Burer. Semidefinite programming in the space of partial positive semidefinite matrices. SIAM Journal on Optimization , 14(1):139–172, 2003

    2003

  22. [30]

    Burer and R

    S. Burer and R. D. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):329–357, 2003

    2003

  23. [31]

    Burer and R

    S. Burer and R. D. Monteiro. Local minima and convergence in low-rank semidefinite pro- gramming. Mathematical Programming, 103(3):427–444, 2005

    2005

  24. [32]

    E. J. Cand` es and Y. Plan. Matrix completion with noise. Proceedings of the IEEE , 98(6): 925–936, 2010

    2010

  25. [33]

    E. J. Cand` es, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of the ACM (JACM) , 58(3):11, 2011

    2011

  26. [34]

    Carlone, D

    L. Carlone, D. M. Rosen, G. Calafiore, J. J. Leonard, and F. Dellaert. Lagrangian duality in 3D SLAM: verification techniques and optimal solutions. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) , pages 125–132, 2015

    2015

  27. [35]

    Carlone, G

    L. Carlone, G. C. Calafiore, C. Tommolillo, and F. Dellaert. Planar pose graph optimization: duality, optimal solutions, and verification. IEEE Transactions on Robotics , 32(3):545–565, 2016

    2016

  28. [36]

    Cogill, S

    R. Cogill, S. Lall, and P. A. Parrilo. Structured semidefinite programs for the control of symmetric systems. Automatica, 44(5):1411–1417, 2008

    2008

  29. [37]

    d Aspremont, L

    A. d Aspremont, L. E. Ghaoui, M. I. Jordan, and G. R. Lanckriet. A direct formulation for sparse PCA using semidefinite programming. SIAM Review, 49(3):434–448, 2007

    2007

  30. [38]

    D. D. Henrion and J. Malick. Projection methods for conic feasibility problems: applications to polynomial sum-of-squares decompositions. Optimization Methods & Software, 26(1):23–46, 2011

    2011

  31. [39]

    De Klerk

    E. De Klerk. Exploiting special structure in semidefinite programming: a survey of theory and applications. European Journal of Operational Research, 201(1):1–10, 2010

    2010

  32. [40]

    Diamond and S

    S. Diamond and S. Boyd. CVXPY: A Python-embedded modeling language for convex opti- mization. Journal of Machine Learning Research , 17(83):1–5, 2016

    2016

  33. [41]

    L. Ding, A. Yurtsever, V. Cevher, J. A. Tropp, and M. Udell. An optimal-storage ap- proach to semidefinite programming using approximate complementarity. arXiv preprint arXiv:1902.03373, 2019

    1902 arXiv

  34. [42]

    Drusvyatskiy, H

    D. Drusvyatskiy, H. Wolkowicz, et al. The many faces of degeneracy in conic optimization. Foundations and Trends R© in Optimization, 3(2):77–170, 2017

    2017

  35. [43]

    Dunning, J

    I. Dunning, J. Huchette, and M. Lubin. JuMP: a modeling language for mathematical opti- mization. SIAM Review, 59(2):295–320, 2017

    2017

  36. [44]

    M. D¨ ur. Copositive programming–a survey. In Recent Advances in Optimization and its Applications in Engineering, pages 3–20. Springer, 2010

    2010

  37. [45]

    M. A. Erdogdu, A. Ozdaglar, P. A. Parrilo, and N. D. Vanli. Convergence rate of block- coordinate maximization Burer-Monteiro method for solving large SDPs. arXiv preprint arXiv:1807.04428, 2018

    2018 arXiv

  38. [46]

    Fazlyab, M

    M. Fazlyab, M. Morari, and G. J. Pappas. Safety verification and robustness analysis of www.annualreviews.org • Scalability in Semidefinite Programming 29 neural networks via quadratic constraints and semidefinite programming. arXiv preprint arXiv:1903.01287, 2019

    1903 arXiv

  39. [47]

    Frank and P

    M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95–110, 1956

    1956

  40. [48]

    R. M. Freund, P. Grigas, and R. Mazumder. An extended Frank–Wolfe method with in-face directions, and its application to low-rank matrix completion. SIAM Journal on Optimization, 27(1):319–346, 2017

    2017

  41. [49]

    Fujisawa, S

    K. Fujisawa, S. Kim, M. Kojima, Y. Okamoto, and M. Yamashita. User’s manual for SparseC- oLO: conversion methods for sparse conic-form linear optimization problems. Research Report B-453, Dept. of Math. and Comp. Sci. Japan, Tech. Rep. , pages 152–8552, 2009

    2009

  42. [50]

    Fukuda, M

    M. Fukuda, M. Kojima, K. Murota, and K. Nakata. Exploiting sparsity in semidefinite pro- gramming via matrix completion I: General framework. SIAM Journal on Optimization , 11 (3):647–674, 2001

    2001

  43. [51]

    G¨ artner and J

    B. G¨ artner and J. Matousek. Approximation Algorithms and Semidefinite Programming . Springer Science & Business Media, 2012

    2012

  44. [52]

    Gatermann and P

    K. Gatermann and P. A. Parrilo. Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra , 192(1-3):95–128, 2004

    2004

  45. [53]

    S. A. Gershgorin. Uber die Abgrenzung der Eigenwerte einer Matrix. Bulletin de l’Acad´ emie des Sciences de l’URSS. Classe des sciences math´ ematiques et na, (6):749–754, 1931

    1931

  46. [54]

    M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM , 42(6): 1115–1145, 1995

    1995

  47. [55]

    Grone, C

    R. Grone, C. R. Johnson, E. M. S´ a, and H. Wolkowicz. Positive definite completions of partial Hermitian matrices. Linear Algebra and its Applications , 58:109–124, 1984

    1984

  48. [56]

    G. Hall. Optimization over nonnegative and convex polynomials with and without semidefinite programming. PhD thesis, Princeton University, 2018

    2018

  49. [57]

    G. Hall. Engineering and business applications of sum of squares polynomials. Available at https://arxiv.org/pdf/1906.07961.pdf, 2019

    1906 arXiv

  50. [58]

    E. Hazan. Sparse approximate solutions to semidefinite programs. In Latin American Sym- posium on Theoretical Informatics, pages 306–316. Springer, 2008

    2008

  51. [59]

    Henrion and A

    D. Henrion and A. Garulli. Positive polynomials in control , volume 312. Springer Science & Business Media, 2005

    2005

  52. [60]

    S. B. Hopkins, T. Schramm, J. Shi, and D. Steurer. Fast spectral algorithms from sum-of- squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing , pages 178–191, 2016

    2016

  53. [61]

    Journ´ ee, F

    M. Journ´ ee, F. Bach, P.-A. Absil, and R. Sepulchre. Low-rank optimization on the cone of positive semidefinite matrices. SIAM Journal on Optimization , 20(5):2327–2351, 2010

    2010

  54. [62]

    Kalbat and J

    A. Kalbat and J. Lavaei. A fast distributed algorithm for decomposable semidefinite programs. In Proceedings of the 54th IEEE Conference on Decision and Control, pages 1742–1749, 2015

    2015

  55. [63]

    S. Kim, M. Kojima, M. Mevissen, and M. Yamashita. Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. Mathematical pro- gramming, 129(1):33–68, 2011

    2011

  56. [64]

    Krislock and H

    N. Krislock and H. Wolkowicz. Explicit sensor network localization using semidefinite repre- sentations and facial reductions. SIAM Journal on Optimization , 20(5):2679–2708, 2010

    2010

  57. [65]

    Kulis, A

    B. Kulis, A. C. Surendran, and J. C. Platt. Fast low-rank semidefinite programming for embedding and clustering. In Artificial Intelligence and Statistics , pages 235–242, 2007

    2007

  58. [66]

    Kungurtsev and J

    V. Kungurtsev and J. Marecek. A two-step pre-processing for semidefinite programming. arXiv preprint arXiv:1806.10868 , 2018

    2018 arXiv

  59. [67]

    J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization , 11(3):796–817, 2001

    2001

  60. [68]

    J. B. Lasserre, K.-C. Toh, and S. Yang. A bounded degree SOS hierarchy for polynomial 30 Majumdar, Hall, Ahmadi optimization. EURO Journal on Computational Optimization , 5(1-2):87–117, 2017

    2017

  61. [69]

    Lemon, A

    A. Lemon, A. M.-C. So, Y. Ye, et al. Low-rank semidefinite programming: theory and appli- cations. Foundations and Trends R© in Optimization, 2(1-2):1–156, 2016

    2016

  62. [70]

    C. Liu, T. Arnon, C. Lazarus, C. Barrett, and M. J. Kochenderfer. Algorithms for verifying deep neural networks. arXiv preprint arXiv:1903.06758 , 2019

    1903 arXiv

  63. [71]

    D. C. Liu and J. Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1-3):503–528, 1989

    1989

  64. [72]

    L¨ ofberg

    J. L¨ ofberg. Yalmip: a toolbox for modeling and optimization in matlab. In Proceedings of the CACSD Conference, Taipei, Taiwan, 2004

    2004

  65. [73]

    Lov´ asz

    L. Lov´ asz. On the Shannon capacity of a graph. IEEE Transactions on Information Theory , 25(1):1–7, 1979

    1979

  66. [74]

    Madani, A

    R. Madani, A. Kalbat, and J. Lavaei. ADMM for sparse semidefinite programming with applications to optimal power flow problem. In Proceedings of the 54th IEEE Conference on Decision and Control, pages 5932–5939, 2015

    2015

  67. [75]

    Majumdar, A

    A. Majumdar, A. A. Ahmadi, and R. Tedrake. Control and verification of high-dimensional systems via DSOS and SDSOS optimization. In Proceedings of the IEEE Conference on Decision and Control, 2014

    2014

  68. [76]

    J. G. Mangelson, J. Liu, R. M. Eustice, and R. Vasudevan. Guaranteed globally optimal planar pose graph and landmark SLAM via sparse-bounded sums-of-squares programming. arXiv preprint arXiv:1809.07744 , 2018

    2018 arXiv

  69. [77]

    R. P. Mason and A. Papachristodoulou. Chordal sparsity, decomposing SDPs and the Lya- punov equation. In Proceedings of the American Control Conference, pages 531–537, 2014

    2014

  70. [78]

    S. Mei, T. Misiakiewicz, A. Montanari, and R. I. Oliveira. Solving SDPs for synchronization and maxcut problems via the Grothendieck inequality.arXiv preprint arXiv:1703.08729, 2017

    2017 arXiv

  71. [79]

    Moosavi-Dezfooli, A

    S.-M. Moosavi-Dezfooli, A. Fawzi, O. Fawzi, and P. Frossard. Universal adversarial perturba- tions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , pages 1765–1773, 2017

    2017

  72. [80]

    Nie and L

    J. Nie and L. Wang. Regularization methods for SDP relaxations in large-scale polynomial optimization. SIAM Journal on Optimization , 22(2):408–428, 2012

    2012

  73. [81]

    O’Donoghue, E

    B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 169 (3):1042–1068, 2016

    2016

  74. [82]

    O’Donoghue, E

    B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd. SCS: Splitting conic solver, version 2.1.0. https://github.com/cvxgrp/scs, Nov. 2017

    2017

  75. [83]

    Papernot, P

    N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami. The limitations of deep learning in adversarial settings. In Proceedings of the IEEE European Symposium on Security and Privacy , pages 372–387, 2016

    2016

  76. [84]

    P. A. Parrilo. Structured semidefinite programs and semialgebraic geometry methods in ro- bustness and optimization . PhD thesis, California Institute of Technology, May 2000

    2000

  77. [85]

    P. A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming, 96(2, Ser. B):293–320, 2003

    2003

  78. [86]

    G. Pataki. On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Mathematics of Operations Research, 23(2):339–358, 1998

    1998

  79. [87]

    G. Pataki. Strong duality in conic linear programming: facial reduction and extended duals. In Computational and Analytical Mathematics , pages 613–634. Springer, 2013

    2013

  80. [88]

    Peng and Y

    J. Peng and Y. Wei. Approximating k-means-type clustering via semidefinite programming. SIAM Journal on Optimization , 18(1):186–205, 2007

    2007

  81. [89]

    Permenter and P

    F. Permenter and P. Parrilo. Partial facial reduction: simplified, equivalent SDPs via approx- imations of the PSD cone. Mathematical Programming, 171(1-2):1–54, 2018

    2018

  82. [90]

    F. N. Permenter. Reduction methods in semidefinite and conic optimization . PhD thesis, Massachusetts Institute of Technology, 2017. www.annualreviews.org • Scalability in Semidefinite Programming 31

    2017

  83. [91]

    The PICOS Documentation , 2018

    PICOS. The PICOS Documentation , 2018. URL https://picos-api.gitlab.io/picos/

    2018

  84. [92]

    Prajna, A

    S. Prajna, A. Papachristodoulou, and P. A. Parrilo. SOSTOOLS: Sum of squares optimization toolbox for MATLAB , 2002-05. Available from http://www.cds.caltech.edu/sostools and http://www.mit.edu/~parrilo/sostools

    2002

  85. [93]

    Pulina and A

    L. Pulina and A. Tacchella. Challenging SMT solvers to verify neural networks. AI Commu- nications, 25(2):117–135, 2012

    2012

  86. [94]

    M. Putinar. Positive polynomials on compact semi-algebraic sets. Indiana University Mathe- matics Journal, 42(3):969–984, 1993

    1993

  87. [95]

    C. Qin, B. O’Donoghue, R. Bunel, R. Stanforth, S. Gowal, J. Uesato, G. Swirszcz, P. Kohli, et al. Verification of non-linear specifications for neural networks. arXiv preprint arXiv:1902.09592, 2019

    1902 arXiv

  88. [96]

    Raghunathan, J

    A. Raghunathan, J. Steinhardt, and P. S. Liang. Semidefinite relaxations for certifying robust- ness to adversarial examples. In Advances in Neural Information Processing Systems , pages 10877–10887, 2018

    2018

  89. [97]

    Recht, M

    B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471–501, 2010

    2010

  90. [98]

    J. Renegar. Accelerated first-order methods for hyperbolic programming. Mathematical Pro- gramming, pages 1–35, 2019

    2019

  91. [99]

    R. T. Rockafellar. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Research, 1(2):97–116, 1976

    1976

  92. [100]

    D. M. Rosen, L. Carlone, A. S. Bandeira, and J. J. Leonard. SE-Sync: a certifiably correct algorithm for synchronization over the special Euclidean group. The International Journal of Robotics Research, 38(2-3):95–125, 2019

    2019

  93. [101]

    Sato and T

    H. Sato and T. Iwai. A new, globally convergent Riemannian conjugate gradient method. Optimization, 64(4):1011–1031, 2015

    2015

  94. [102]

    J. Sturm. SeDuMi version 1.05 , Oct. 2001. Latest version available at http://sedumi.ie.lehigh.edu/

    2001

  95. [103]

    J. Sun. Provable nonconvex methods and algorithms (collection of papers). References avail- able at https://sunju.org/research/nonconvex/, 2019

    2019

  96. [104]

    J. Sun, Q. Qu, and J. Wright. Complete dictionary recovery over the sphere II: recovery by Riemannian trust-region method. IEEE Transactions on Information Theory , 63(2):885–914, 2016

    2016

  97. [105]

    J. Sun, Q. Qu, and J. Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18(5):1131–1198, 2018

    2018

  98. [106]

    Sun and L

    Y. Sun and L. Vandenberghe. Decomposition methods for sparse matrix nearness problems. SIAM Journal on Matrix Analysis and Applications , 36(4):1691–1717, 2015

    2015

  99. [107]

    Y. Sun, M. S. Andersen, and L. Vandenberghe. Decomposition in conic optimization with partially separable structure. SIAM Journal on Optimization , 24(2):873–897, 2014

    2014

  100. [108]

    Szegedy, W

    C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 , 2013

    2013 arXiv

  101. [109]

    Thrun, W

    S. Thrun, W. Burgard, and D. Fox. Probabilistic Robotics. MIT press, 2005

    2005

  102. [110]

    Tjeng, K

    V. Tjeng, K. Xiao, and R. Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.07356 , 2017

    2017 arXiv

  103. [111]

    K. C. Toh, R. H. T¨ ut¨ unc¨ u, and M. J. Todd. SDPT3 - a MATLAB software package for semidefinite-quadratic-linear programming. Available from http://www.math.cmu.edu/~reha/sdpt3.html

  104. [112]

    Townsend, N

    J. Townsend, N. Koep, and S. Weichwald. Pymanopt: A python toolbox for optimization on manifolds using automatic differentiation. The Journal of Machine Learning Research , 17(1): 4755–4759, 2016

    2016

  105. [113]

    Vallentin

    F. Vallentin. Symmetry in semidefinite programs. Linear Algebra and its Applications , 430 (1):360–369, 2009. 32 Majumdar, Hall, Ahmadi

    2009

  106. [114]

    Vandenberghe and S

    L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review, 38(1):49–95, Mar. 1996

    1996

  107. [115]

    H. Waki, Y. Ebihara, and N. Sebe. Reduction of SDPs in H-infinity control of SISO systems and performance limitations analysis. In Proceedings of the 55th IEEE Conference on Decision and Control, pages 646–651, 2016

    2016

  108. [116]

    Wang, W.-C

    P.-W. Wang, W.-C. Chang, and J. Z. Kolter. The mixing method: coordinate descent for low-rank semidefinite programming. arXiv preprint arXiv:1706.00476 , 2017

    2017 arXiv

  109. [117]

    S. Wang, K. Pei, J. Whitehouse, J. Yang, and S. Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems , pages 6367–6377, 2018

    2018

  110. [118]

    Weisser, J

    T. Weisser, J. B. Lasserre, and K.-C. Toh. Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity. Mathematical Programming Computation, 10(1):1–32, 2018

    2018

  111. [119]

    Wong and J

    E. Wong and J. Z. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXiv:1711.00851 , 2017

    2017 arXiv

  112. [120]

    Xiang, P

    W. Xiang, P. Musau, A. A. Wild, D. M. Lopez, N. Hamilton, X. Yang, J. Rosenfeld, and T. T. Johnson. Verification for machine learning, autonomy, and neural networks survey. arXiv preprint arXiv:1810.01989, 2018

    2018 arXiv

  113. [121]

    L. Yang, D. Sun, and K.-C. Toh. SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Mathematical Programming Computation, 7(3):331–366, 2015

    2015

  114. [122]

    Yurtsever, M

    A. Yurtsever, M. Udell, J. A. Tropp, and V. Cevher. Sketchy decisions: Convex low-rank matrix optimization with optimal storage. arXiv preprint arXiv:1702.06838 , 2017

    2017 arXiv

  115. [123]

    Yurtsever, O

    A. Yurtsever, O. Fercoq, and V. Cevher. A conditional gradient-based augmented Lagrangian framework. arXiv preprint arXiv:1901.04013 , 2019

    1901 arXiv

  116. [124]

    X.-Y. Zhao, D. Sun, and K.-C. Toh. A Newton-CG augmented Lagrangian method for semidef- inite programming. SIAM Journal on Optimization , 20(4):1737–1765, 2010

    2010

  117. [125]

    Zheng, Y

    S. Zheng, Y. Song, T. Leung, and I. Goodfellow. Improving the robustness of deep neural networks via stability training. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4480–4488, 2016

    2016

  118. [126]

    Zheng, R

    Y. Zheng, R. P. Mason, and A. Papachristodoulou. A chordal decomposition approach to scalable design of structured feedback gains over directed graphs. In Proceedings of the 55th IEEE Conference on Decision and Control , pages 6909–6914, 2016

    2016

  119. [127]

    Zheng, R

    Y. Zheng, R. P. Mason, and A. Papachristodoulou. Scalable design of structured controllers using chordal decomposition. IEEE Transactions on Automatic Control, 63(3):752–767, 2017

    2017

  120. [128]

    Zheng, G

    Y. Zheng, G. Fantuzzi, A. Papachristodoulou, P. Goulart, and A. Wynn. Chordal decomposi- tion in operator-splitting methods for sparse semidefinite programs. Mathematical Program- ming, pages 1–44, 2019

    2019

  121. [129]

    Y. Zhu, G. Pataki, and Q. Tran-Dinh. Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs. Mathematical Programming Computation, 11(3):503–586, 2019. www.annualreviews.org • Scalability in Semidefinite Programming 33

    2019

  122. [2019]

    Available at https://arxiv.org/pdf/1709.09307.pdf

    arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.