Pith. sign in

REVIEW 3 major objections 4 minor 3 cited by

New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Given primal simplicity and dual proximity, augmented Lagrangian subproblems inherit low-rank structure and are globally solvable by gradient descent at a linear rate.

desk verdict Strong theory with a false quantifier in Theorem 2; the flaw is fixable and the paper deserves review. read the letter →

arxiv 2505.15775 v1 pith:SRBAZE2T submitted 2025-05-21 math.OC

Lijun Ding , Haihao Lu , Jinwen Yang This is my paper · ORCID
classification math.OC MSC 90C2290C26
keywords semidefiniteprogrammingaugmentedLagrangianmethodBurer-Monteirofactorizationlow-rankquadraticgrowthlinearconvergencerankadaptationGPUsolver
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

The paper aims to put the empirically successful recipe of augmented Lagrangian methods combined with low-rank Burer-Monteiro factorization on solid theoretical footing. It claims that when the original semidefinite program is primal simple and the current dual variable is close enough to a strict complementary dual optimal solution, then each augmented Lagrangian subproblem inherits the same favorable structure: a unique low-rank optimum, strict complementarity, and quadratic growth with a constant that does not shrink as the algorithm progresses. Under those conditions, plain gradient descent on the nonconvex factorized subproblem converges linearly to the global optimum. The paper also presents counterexamples showing that these locality assumptions are essential, and it introduces a GPU-accelerated rank-adaptive solver that scales to very large MaxCut and matrix completion instances.

What carries the argument

The load-bearing object is the restricted constraint map $A_V$, where the columns of $V$ span the nullspace of the dual slack at the strict complementary dual optimum, equivalently the range of $X^*$. The proof shows that near $y^*$ the smallest singular value of $A_V$ stays uniformly positive, making $A_V$ injective and forcing the subproblem's optimum to be unique and supported on the same low-rank subspace. Combined with a quadratic-growth lemma for the positive-semidefinite cone under strict complementarity, this yields the $y$-independent growth constant. For the nonconvex factorized problem, the same constants produce a local descent condition on the factor space, which drives the linear convergence of gradient descent.

What would settle it

Run exact ALM on a primal-simple SDP with a rank-one optimum, starting the dual far from $y^*$, and check the subproblem solutions along the dual sequence; if some iterate $y_t$ with distance to $y^*$ arbitrarily small produces a unique subproblem optimum of rank above $r^*$ or a quadratic growth constant that vanishes, then the claimed local radius $c$ does not exist.

Watch

Extended reading notes

Core claim

The central discovery is that the regularity of a low-rank SDP passes through the augmented Lagrangian iteration. If the original problem is primal simple—strong duality, strict complementarity, and a unique primal optimum $X^*$—and the dual variable $y$ lies in a small neighborhood of a strict complementary dual optimum $y^*$, then for every penalty parameter the subproblem is also primal simple, has a unique optimum with the same rank as $X^*$, and satisfies a quadratic growth inequality whose constant is independent of $y$. Applying this to the Burer-Monteiro factorization with rank $k = r^*$ yields the paper's main algorithmic guarantee: gradient descent, initialized near the subproblem optimum, converges linearly to a global optimum of the nonconvex subproblem. The paper's counterexamples show that outside this local regime the subproblem can have a unique high-rank solution or spurious local minima, which the paper interprets as evidence that the local assumptions are inherent to the problem structure rather than artifacts of the proof. These structural results are the theoretical basis for the reported solver ALORA, whose GPU implementation solves large MaxCut and matrix completion SDPs.

Load-bearing premise

The load-bearing premise is that the dual variable $y$ stays inside an unquantified ball around a strict complementary dual optimum $y^*$; the paper does not prove that ALM's own dual updates keep $y$ in that ball, and its examples show that outside it the subproblems can be high-rank or have spurious local minima.

Editorial extensions

If this is right

  • With rank $k = r^*$, the Burer-Monteiro formulation of each local subproblem is exact, so no rank overestimation is needed once the dual variable is close to a strict complementary optimum.
  • Because the quadratic growth constant is independent of $y$, gradient descent's linear rate and initialization radius do not shrink as ALM's dual iterates approach the optimum, keeping subproblem cost controlled throughout the outer iteration.
  • For a primal-simple low-rank SDP, simple gradient descent on the factorized subproblem reaches a global optimum of that subproblem, not merely a stationary point, provided the initialization is local and the dual is local.
  • The counterexamples imply that any ALM-BM method aiming for global guarantees must either keep dual iterates in the local region or explicitly handle high-rank and spurious-minimum regimes, motivating rank-adaptive strategies.
  • The numerical results indicate that these structural guarantees can be realized in practice: the reported GPU solver handles MaxCut instances with roughly 24 million vertices and matrix completion instances with over $10^7$ observed entries in hundreds of seconds.

Reading between the lines

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

  • Editorial inference: if ALM's dual iterates could be shown to stay in the local ball, or to return to it, then Theorem 2 and Corollary 1 would globalize into an end-to-end linear convergence guarantee for ALM-BM; the paper leaves this as an open question.
  • Editorial inference: the unquantified radius $c$ and its dependence on the smallest singular value of $A_V$ suggest that the conditioning of the constraint map, not just the rank, controls the size of the safe region around $y^*$; a testable extension would be to estimate $c$ for structured SDPs.
  • Editorial inference: the tightness examples show that ALM subproblems can saturate the rank bound set by the number of constraints, so rank adaptation such as ALORA's may be necessary for global convergence in practice even though the local theory only needs rank $r^*$.
  • Editorial inference: ALORA's negative-curvature exploration can be read as an algorithmic escape from the spurious local minima the paper constructs; a natural next test is whether this rank-adaptation mechanism provably avoids those minima.
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

3 major / 4 minor

Summary. The paper studies augmented Lagrangian methods combined with Burer--Monteiro factorization for low-rank semidefinite programs. It claims that, under primal simplicity of the original SDP, the ALM subproblems inherit low-rankness, strict complementarity, and primal simplicity when the dual variable is close to a strict complementary dual optimal solution; it also claims a quadratic growth condition with a dual-independent constant, and uses this to prove linear convergence of gradient descent on the Burer--Monteiro subproblems. The paper further gives examples intended to show necessity of the local assumptions, and proposes ALORA, a GPU-accelerated rank-adaptive ALM-BM solver, with numerical experiments on large-scale MaxCut and matrix completion instances.

Significance. The paper addresses a real gap in the theory of ALM-BM subproblems, and its intended results would be useful: quadratic growth of the subproblem with a constant independent of the dual iterate is exactly what one needs for uniform subproblem solvability along the ALM iterations. The proofs are detailed, the necessity examples are concrete, and the ALORA implementation and experiments are a genuine strength. However, the main structural theorem is currently stated with a false quantifier over the penalty parameter, and the quadratic-growth inequality in the theorem statement has a sign error; these issues must be corrected before the theoretical claims can be relied upon.

major comments (3)
  1. [Theorem 2 (Section 3)] The quantifier over rho in Theorem 2 is false as stated. The theorem asserts a single constant c>0 such that for every y with ||y-y*||≤c and every rho>0, the rank equality (13) holds. Using the data of Proposition 5 (C=0, A1=diag(1,0), A2=diag(0,1), b=(0,1), X*=diag(0,1), y*=(-1,0)), fix any c>0, choose epsilon in (0,min(c,1)), set y=(-1,-epsilon), and choose rho<epsilon. Then ||y-y*||=epsilon≤c. Up to a constant, the augmented Lagrangian is X11 + epsilon X22 + (rho/2)(X11^2+(1-X22)^2). Minimizing over X≽0 gives X11=0 (the unconstrained root is negative) and X22=0 (the unconstrained root 1-epsilon/rho is negative), so the unique minimizer is the zero matrix, which has rank 0 rather than rank(X*)=1. This contradicts (13). The source is that the constant c in Lemma 3 is chosen using Theorem 1's bounds (7a)-(7c), which contain 1/rho factors; hence c genuinely depends on rho. The theorem should be restated with rho fixed, or with c=c(rho), and Lemma 3 must state this dependence explicitly.
  2. [Equation (14)] The quadratic-growth inequality is stated with the wrong orientation. The left-hand side L_rho(X_{y,rho},y)-L_rho(X,y) is non-positive because X_{y,rho} minimizes L_rho(.,y), while the right-hand side is positive for X≠X_{y,rho}. The proof in Section 3.1 derives the reverse inequality, namely L_rho(X,y)-L_rho(X_{y,rho},y)=<Z(z_{y,rho}),X>+(rho/2)||AX-AX_{y,rho}||^2 ≥ gamma||X-X_{y,rho}||^2 (see equations (32)-(34)). The theorem statement should be corrected accordingly.
  3. [Proposition 5 (Section 3.2)] The example as written does not illustrate the stated 'necessity of localness for quadratic growth condition.' The dual optimal points y_epsilon=(-epsilon,0) converge to y=0 as epsilon→0, not to the strict complementary dual optimal solution y*=(-1,0) identified in the proof; they remain at distance approximately 1 from y*. The construction therefore shows failure of quadratic growth when the dual optimal solution loses strict complementarity, rather than failure at points arbitrarily close to a strict complementary dual optimum. Please clarify how this supports the localness claim, or modify the construction so that the failure occurs along a sequence converging to y*.
minor comments (4)
  1. [Section 1.2] In the notation paragraph, 'We shall frequently use the fact taht' contains the typo 'taht'; it should read 'that'.
  2. [Section 3.1] The sentence 'we will choose c small enough so that Lemma 8 and Lemma 3 can always be applied' appears to mis-cite: the Lemma 8 in Appendix B concerns the generic problem (Gen-ALM), whereas the needed results at that point are Proposition 1 and Lemma 3.
  3. [Section 4.2.2] In the displayed formula for c0, the expression 'sigma_{min<0}(X*)' should read 'sigma_{min>0}(X*)'.
  4. [Section 4.2] The phrase '(gamma, B, r) quadratic growth' in Theorem 3 is inconsistent with the parameter order '(gamma, r, B)-QG' used in Definition 7; please align the notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's results are conditional derivations from explicit regularity assumptions, with no fitted-parameter predictions; the self-citation of 'primal simplicity' is not load-bearing.

full rationale

The derivation chain is self-contained in the relevant sense. Theorem 2 and Corollary 1 are conditional statements: given primal simplicity, strict complementarity, dual Slater's condition, and a localized dual variable, the paper proves rank inheritance, primal simplicity of the ALM subproblem, quadratic growth, and linear convergence of gradient descent on the Burer-Monteiro subproblem. The proofs use KKT conditions, Lemma 1 (nonexpansiveness of the proximal dual update), Lemma 3, and the appended Lemma 7 (quadratic growth of the original SDP), all derived from the stated assumptions. No parameter is fitted to data and then renamed a prediction, and no equation reduces to its own input by construction. The paper does cite the authors' prior work [24, 25] for the notion of primal simplicity and its prevalence, but that citation is not load-bearing for the main theorems: the theorems hold conditionally on primal simplicity regardless of how common that condition is, and the proof does not invoke the prevalence claim. A separate correctness concern, distinct from circularity, is that Theorem 2 and Lemma 3 state a constant c uniform in both the dual ball and ρ, while the proof of (16c) relies on Theorem 1 bounds containing 1/ρ factors, so the written proof does not justify a single c valid for all ρ > 0. This is a quantifier/technical issue in the proof, not a circular reduction of the claimed result to its inputs.

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

The theorems are conditional statements with explicit assumptions. No parameters are fitted to data, and no new unobservable entities are postulated. The paper relies on standard regularity assumptions from the SDP literature.

assumptions (5)
  • domain assumption Dual Slater's condition (D-Slater's) holds for the original SDP (P)
    Assumed throughout (Section 2.1 and Theorem 1) to ensure strong duality and existence of primal optimal solutions.
  • domain assumption Primal simplicity of (P): strong duality, strict complementarity, unique primal solution
    Central hypothesis of Theorem 2 and Corollary 1 (Section 2.1, Definition 3).
  • domain assumption Existence of strict complementary dual optimal solution y*
    Follows from primal simplicity; the localness results are stated relative to it.
  • domain assumption For (Gen-ALM): f is convex and L-smooth, unique solution exists (Section 4)
    Used for the generic BM linear convergence theorem.
  • standard math Standard linear algebra tools (Weyl, Davis-Kahan, etc.) are valid
    Invoked in proofs without proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming." pith.science (2026). https://pith.science/paper/SRBAZE2T

@misc{pith2026250515775,
  author       = {Pith},
  title        = {Pith review of: New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SRBAZE2T}},
  note         = {Machine review of arXiv:2505.15775}
}
read the original abstract

Augmented Lagrangian Method (ALM) combined with Burer-Monteiro (BM) factorization, dubbed ALM-BM, offers a powerful approach for solving large-scale low-rank semidefinite programs (SDPs). Despite its empirical success, the theoretical understandings of the resulting non-convex ALM-BM subproblems, particularly concerning their structural properties and efficient subproblem solvability by first-order methods, still remain limited. This work addresses these notable gaps by providing a rigorous theoretical analysis. We demonstrate that, under appropriate regularity of the original SDP, termed as primal simplicity, ALM subproblems inherit crucial properties such as low-rankness and strict complementarity when the dual variable is localized. Furthermore, ALM subproblems are shown to enjoy a quadratic growth condition, building on which we prove that the non-convex ALM-BM subproblems can be solved to global optimality by gradient descent, achieving linear convergence under conditions of local initialization and dual variable proximity. Through illustrative examples, we further establish the necessity of these local assumptions, revealing them as inherent characteristics of the problem structure. Motivated by these theoretical insights, we propose ALORA, a rank-adaptive augmented Lagrangian method that builds upon the ALM-BM framework, which dynamically adjusts the rank using spectral information and explores negative curvature directions to navigate the nonconvex landscape. Exploiting modern GPU computing architectures, ALORA exhibits strong numerical performance, solving SDPs with tens of millions of dimensions in hundreds of seconds.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

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

  1. A Curvature-Aware Rank-Adaptive Distributed Augmented-Lagrangian Solver for Large-Scale SDPs

    math.OC 2026-07 conditional novelty 7.0 of 10

    CARDAL grows the rank of a Burer–Monteiro factorization only when dual-slack curvature is negative and distributes the resulting low-rank augmented-Lagrangian solver across GPUs.

  2. Local Linear Convergence of the Primal-Dual Hybrid Gradient Method for Semidefinite Programming

    math.OC 2026-07 accept novelty 6.0 of 10

    PDHG converges locally linearly for SDP under strict complementarity or primal-dual nondegeneracy, and can converge sublinearly when both fail.

  3. An Overview of GPU-based First-Order Methods for Linear Programming and Extensions

    math.OC 2025-06 unverdicted novelty 2.0 of 10

    A survey of GPU-based first-order LP solvers focusing on cuPDLP, its PDHG core, theory, benchmarks, and extensions to QP, SDP, and conic programming.

Reference graph

Works this paper leans on

101 extracted references · 66 canonical work pages · cited by 3 Pith papers

  1. [1]

    1, 13–51

    Farid Alizadeh, Interior point methods in semidefinite programming with app lications to combinatorial optimization, SIAM journal on Optimization 5 (1995), no. 1, 13–51

    1995

  2. [2]

    1, 111–128

    Farid Alizadeh, Jean-Pierre A Haeberly, and Michael L Overton, Complementarity and nondegeneracy in semidefinite programming , Mathematical programming 77 (1997), no. 1, 111–128

    1997

  3. [3]

    MOSEK ApS, Mosek optimization suite 11.0.20. , 2025

    2025

  4. [4]

    Barvinok, Problems of distance geometry and convex properties of quad ratic maps, Discrete & Computational Geometry 13 (1995), 189–202

    Alexander I. Barvinok, Problems of distance geometry and convex properties of quad ratic maps, Discrete & Computational Geometry 13 (1995), 189–202

    1995

  5. [5]

    2, 443–461

    Steven J Benson, Yinyu Ye, and Xiong Zhang, Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM Journal on Optimization 10 (2000), no. 2, 443–461

    2000

  6. [6]

    4, 827–841

    Tim Besard, Christophe Foket, and Bjorn De Sutter, Effective extensible programming: unleashing julia on gpus , IEEE Transactions on Parallel and Distributed Systems 30 (2018), no. 4, 827–841

    2018

  7. [7]

    1, 65–98

    Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah, Julia: A fresh approach to numerical computing, SIAM review 59 (2017), no. 1, 65–98

    2017

  8. [8]

    3243–3270

    Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, and Praneeth Netrapalli, Smoothed analysis for low-rank solutions to semidefinite programs in quadratic pe nalty form , Conference on learning theory, PMLR, 2018, pp. 3243–3270

    2018

Show all 101 references
  1. [9]

    1-4, 613–623

    Brian Borchers, Csdp, ac library for semidefinite programming , Optimization methods and Software 11 (1999), no. 1-4, 613–623

    1999

  2. [10]

    Nicolas Boumal, Vlad Voroninski, and Afonso Bandeira, The non-convex burer-monteiro approach works on smooth semidefinite programs , Advances in Neural Information Processing Systems 29 (2016)

    2016

  3. [11]

    3, 581–608

    Nicolas Boumal, Vladislav Voroninski, and Afonso S Bandeira, Deterministic guarantees for burer- monteiro factorizations of smooth semidefinite programs , Communications on Pure and Applied Math- ematics 73 (2020), no. 3, 581–608

    2020

  4. [12]

    3, 493–512

    Samuel Burer and Changhui Choi, Computational enhancements in low-rank semidefinite progr amming, Optimisation Methods and Software 21 (2006), no. 3, 493–512

    2006

  5. [13]

    2, 329–357

    Samuel Burer and Renato DC Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization , Mathematical programming 95 (2003), no. 2, 329–357. 30

    2003

  6. [14]

    3, 427–444

    , Local minima and convergence in low-rank semidefinite progr amming, Mathematical program- ming 103 (2005), no. 3, 427–444

    2005

  7. [15]

    2, 024001

    Daniel Cavalcanti and Paul Skrzypczyk, Quantum steering: a review with focus on semidefinite pro- gramming, Reports on Progress in Physics 80 (2016), no. 2, 024001

    2016

  8. [16]

    Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, a nd Xinyuan Zhao, Hpr-lp: An imple- mentation of an hpr method for solving linear programming , arXiv preprint arXiv:2408.12179 (2024)

    2024 arXiv

  9. [17]

    Liang Chen, Defeng Sun, and Kim-Chuan Toh, An efficient inexact symmetric gauss–seidel based ma- jorized admm for high-dimensional convex composite conic p rogramming, Mathematical Programming 161 (2017), 237–270

    2017

  10. [18]

    4, 14–31

    Yudong Chen and Yuejie Chi, Harnessing structures in big data via guaranteed low-rank m atrix estima- tion: Recent theory and fast algorithms via convex and nonco nvex optimization, IEEE Signal Processing Magazine 35 (2018), no. 4, 14–31

    2018

  11. [19]

    Yudong Chen and Martin J Wainwright, Fast low-rank estimation by projected gradient descent: Ge n- eral statistical and algorithmic guarantees , arXiv preprint arXiv:1509.03025 (2015)

    2015 arXiv

  12. [20]

    Yuwen Chen, Danny Tse, Parth Nobel, Paul Goulart, and Steph en Boyd, Cuclarabel: Gpu acceleration for a conic optimization solver , arXiv preprint arXiv:2412.19027 (2024)

    2024

  13. [21]

    Ying Cui, Defeng Sun, and Kim-Chuan Toh, On the r-superlinear convergence of the kkt residuals generated by the augmented lagrangian method for convex com posite conic programming, Mathematical Programming 178 (2019), 381–415

    2019

  14. [22]

    Timothy A Davis and Yifan Hu, The university of florida sparse matrix collection , ACM Transactions on Mathematical Software (TOMS) 38 (2011), no. 1, 1–25

    2011

  15. [23]

    2, 1305–1332

    Lijun Ding and Benjamin Grimmer, Revisiting spectral bundle methods: Primal-dual (sub) lin ear con- vergence rates, SIAM Journal on Optimization 33 (2023), no. 2, 1305–1332

    2023

  16. [24]

    4, 2614–2637

    Lijun Ding and Madeleine Udell, On the simplicity and conditioning of low rank semidefinite p rograms, SIAM Journal on Optimization 31 (2021), no. 4, 2614–2637

    2021

  17. [25]

    Wang, Sharpness and well-conditioning of nonsmooth convex formu lations in statistical signal recovery , 2023

    Lijun Ding and Alex L. Wang, Sharpness and well-conditioning of nonsmooth convex formu lations in statistical signal recovery , 2023

    2023

  18. [26]

    4, 2695–2725

    Lijun Ding, Alp Yurtsever, Volkan Cevher, Joel A Tropp, and Ma deleine Udell, An optimal-storage approach to semidefinite programming using approximate com plementarity, SIAM Journal on Opti- mization 31 (2021), no. 4, 2695–2725

    2021

  19. [27]

    Dmitriy Drusvyatskiy and Adrian S Lewis, Generic nondegeneracy in convex optimization , Proceedings of the American Mathematical Society (2011), 2519–2527

    2011

  20. [28]

    Simon S Du, Wei Hu, and Jason D Lee, Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced , Advances in neural information processing systems 31 (2018)

    2018

  21. [29]

    1, 17–40

    Daniel Gabay and Bertrand Mercier, A dual algorithm for the solution of nonlinear variational p roblems via finite element approximation , Computers & mathematics with applications 2 (1976), no. 1, 17–40

    1976

  22. [30]

    3, 779–810

    Michael Garstka, Mark Cannon, and Paul Goulart, Cosmo: A conic operator splitting method for convex conic problems , Journal of Optimization Theory and Applications 190 (2021), no. 3, 779–810

    2021

  23. [31]

    1233–1242

    Rong Ge, Chi Jin, and Yi Zheng, No spurious local minima in nonconvex low rank problems: A un ified geometric analysis , International Conference on Machine Learning, PMLR, 2017, pp . 1233–1242. 31

    2017

  24. [32]

    34 3–360

    Michel Goemans and Franz Rendl, Combinatorial optimization , Handbook of Semidefinite Program- ming: Theory, Algorithms, and Applications, Springer, 2000, pp. 34 3–360

    2000

  25. [33]

    Paul J Goulart and Yuwen Chen, Clarabel: An interior-point solver for conic programs with quadratic objectives, arXiv preprint arXiv:2405.12762 (2024)

    2024 arXiv

  26. [34]

    Qiushi Han, Chenxi Li, Zhenwei Lin, Caihua Chen, Qi Deng, Dong dong Ge, Huikang Liu, and Yinyu Ye, A low-rank admm splitting approach for semidefinite program ming, arXiv preprint arXiv:2403.09133 (2024)

    2024 arXiv

  27. [35]

    Qiushi Han, Zhenwei Lin, Hanwen Liu, Caihua Chen, Qi Deng, Don gdong Ge, and Yinyu Ye, Ac- celerating low-rank factorization-based semidefinite pro gramming algorithms on gpu , arXiv preprint arXiv:2407.15049 (2024)

    2024 arXiv

  28. [36]

    thesis, 2000

    Christoph Helmberg, Semidefinite programming for combinatorial optimization , Ph.D. thesis, 2000

    2000

  29. [37]

    3, 673–696

    Christoph Helmberg and Franz Rendl, A spectral bundle method for semidefinite programming , SIAM Journal on Optimization 10 (2000), no. 3, 673–696

    2000

  30. [38]

    2, 342–361

    Christoph Helmberg, Franz Rendl, Robert J Vanderbei, and Hen ry Wolkowicz, An interior-point method for semidefinite programming , SIAM Journal on optimization 6 (1996), no. 2, 342–361

    1996

  31. [39]

    5, 303–320

    Magnus R Hestenes, Multiplier and gradient methods , Journal of optimization theory and applications 4 (1969), no. 5, 303–320

    1969

  32. [40]

    Yicheng Huang, Wanyu Zhang, Hongpei Li, Dongdong Ge, Huikan g Liu, and Yinyu Ye, Restarted primal-dual hybrid conjugate gradient method for large-sc ale quadratic programming , arXiv preprint arXiv:2405.16160 (2024)

    2024 arXiv

  33. [41]

    5, 2327–2351

    Michel Journ´ ee, Francis Bach, P-A Absil, and Rodolphe Sepulch re, Low-rank optimization on the cone of positive semidefinite matrices , SIAM Journal on Optimization 20 (2010), no. 5, 2327–2351

    2010

  34. [42]

    4, 35–49

    Galina M Korpelevich, Extragradient method for finding saddle points and other pro blems, Matekon 13 (1977), no. 4, 35–49

    1977

  35. [43]

    1, 511–547

    Guanghui Lan and Renato DC Monteiro, Iteration-complexity of first-order augmented lagrangian methods for convex programming , Mathematical Programming 155 (2016), no. 1, 511–547

    2016

  36. [44]

    1, 92–107

    Javad Lavaei and Steven H Low, Zero duality gap in optimal power flow problem , IEEE Transactions on Power systems 27 (2011), no. 1, 92–107

    2011

  37. [45]

    1-2, 1–156

    Alex Lemon, Anthony Man-Cho So, Yinyu Ye, et al., Low-rank semidefinite programming: Theory and applications, Foundations and Trends ® in Optimization 2 (2016), no. 1-2, 1–156

    2016

  38. [46]

    Feng-Yi Liao, Lijun Ding, and Yang Zheng, An overview and comparison of spectral bundle methods for primal and dual semidefinite programs , arXiv preprint arXiv:2307.07651 (2023)

    2023

  39. [47]

    , Inexact augmented lagrangian methods for conic optimizati on: Quadratic growth and linear convergence, Advances in Neural Information Processing Systems 37 (2024), 41013–41050

    2024

  40. [48]

    Zhenwei Lin, Zikai Xiong, Dongdong Ge, and Yinyu Ye, Pdcs: A primal-dual large-scale conic pro- gramming solver with gpu enhancements , arXiv preprint arXiv:2505.00311 (2025)

    2025

  41. [49]

    2, 632–650

    Ya-Feng Liu, Xin Liu, and Shiqian Ma, On the nonergodic convergence rate of an inexact augmented lagrangian framework for composite convex programming , Mathematics of Operations Research 44 (2019), no. 2, 632–650

    2019

  42. [50]

    L´ aszl´ o Lov´ asz,Semidefinite programs and combinatorial optimization , Recent advances in algorithms and combinatorics, Springer, 2003, pp. 137–194. 32

    2003

  43. [51]

    1, 15–27

    Steven H Low, Convex relaxation of optimal power flow—part i: Formulation s and equivalence , IEEE Transactions on Control of Network Systems 1 (2014), no. 1, 15–27

    2014

  44. [52]

    2, 177–189

    , Convex relaxation of optimal power flow—part ii: Exactness , IEEE Transactions on Control of Network Systems 1 (2014), no. 2, 177–189

    2014

  45. [53]

    jl: A gpu implementation of restarted primal-dual h ybrid gradient for linear programming in julia , arXiv preprint arXiv:2311.12180 (2023)

    Haihao Lu and Jinwen Yang, cupdlp. jl: A gpu implementation of restarted primal-dual h ybrid gradient for linear programming in julia , arXiv preprint arXiv:2311.12180 (2023)

    2023 arXiv

  46. [54]

    , A practical and optimal first-order method for large-scale c onvex quadratic programming, arXiv preprint arXiv:2311.07710 (2023)

    2023 arXiv

  47. [55]

    Haihao Lu, Jinwen Yang, Haodong Hu, Qi Huangfu, Jinsong Liu, T ianhao Liu, Yinyu Ye, Chuwen Zhang, and Dongdong Ge, cupdlp-c: A strengthened implementation of cupdlp for line ar programming by c language , arXiv preprint arXiv:2312.14832 (2023)

    2023 arXiv

  48. [56]

    2, 1159–1190

    Zhaosong Lu and Zirui Zhou, Iteration-complexity of first-order augmented lagrangian methods for convex conic programming, SIAM journal on optimization 33 (2023), no. 2, 1159–1190

    2023

  49. [57]

    1, 59–81

    Zhi-Quan Luo, Jos F Sturm, and Shuzhong Zhang, Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming , SIAM Journal on Optimization 8 (1998), no. 1, 59–81

    1998

  50. [58]

    1, 199–211

    Ramtin Madani, Somayeh Sojoudi, and Javad Lavaei, Convex relaxation for optimal power flow prob- lem: Mesh networks , IEEE Transactions on Power Systems 30 (2014), no. 1, 199–211

    2014

  51. [59]

    1, 331–360

    Anirudha Majumdar, Georgina Hall, and Amir Ali Ahmadi, Recent scalability improvements for semidefinite programming with applications in machine lear ning, control, and robotics , Annual Re- view of Control, Robotics, and Autonomous Systems 3 (2020), no. 1, 331–360

    2020

  52. [60]

    Tim Martin, Thomas B Sch¨ on, and Frank Allg¨ ower, Guarantees for data-driven control of nonlinear systems using semidefinite programming: A survey , Annual Reviews in Control 56 (2023), 100911

    2023

  53. [61]

    8, 083001

    David A Mazziotti, Large-scale semidefinite programming for many-electron qu antum mechanics, Phys- ical review letters 106 (2011), no. 8, 083001

    2011

  54. [62]

    Renato DC Monteiro, Arnesh Sujanani, and Diego Cifuentes, A low-rank augmented lagrangian method for large-scale semidefinite programming based on a hybrid c onvex-nonconvex approach, arXiv preprint arXiv:2401.12490 (2024)

    2024 arXiv

  55. [63]

    Ion Necoara, Yu Nesterov, and Francois Glineur, Linear convergence of first order methods for non- strongly convex optimization , Mathematical Programming 175 (2019), 69–107

    2019

  56. [64]

    5, 3109–3134

    Valentin Nedelcu, Ion Necoara, and Quoc Tran-Dinh, Computational complexity of inexact gradient augmented lagrangian methods: application to constrained mpc, SIAM Journal on Control and Opti- mization 52 (2014), no. 5, 3109–3134

    2014

  57. [65]

    2, 324–364

    Yu E Nesterov and Michael J Todd, Primal-dual interior-point methods for self-scaled cones , SIAM Journal on optimization 8 (1998), no. 2, 324–364

    1998

  58. [66]

    137, Springer

    Yurii Nesterov, Lectures on convex optimization , vol. 137, Springer

  59. [67]

    Liam O’Carroll, Vaidehi Srinivas, and Aravindan Vijayaraghavan, The burer-monteiro sdp method can fail even above the barvinok-pataki bound , Advances in Neural Information Processing Systems 35 (2022), 31254–31264

    2022

  60. [68]

    3, 1999–2023

    Brendan O’Donoghue, Operator splitting for a homogeneous embedding of the linea r complementarity problem, SIAM Journal on Optimization 31 (2021), no. 3, 1999–2023

    2021

  61. [69]

    Cardinal Operations, Cardinal optimizer (copt) user guide. , 2025. 33

    2025

  62. [70]

    Brendan O’donoghue, Eric Chu, Neal Parikh, and Stephen Boyd , Conic optimization via operator splitting and homogeneous self-dual embedding , Journal of Optimization Theory and Applications 169 (2016), 1042–1068

    2016

  63. [71]

    2, 339–358

    G´ abor Pataki,On the rank of extreme matrices in semidefinite programs and t he multiplicity of optimal eigenvalues, Mathematics of operations research 23 (1998), no. 2, 339–358

    1998

  64. [72]

    Michael JD Powell, A method for nonlinear constraints in minimization problem s, Optimization (1969), 283–298

    1969

  65. [73]

    3, 471–501

    Benjamin Recht, Maryam Fazel, and Pablo A Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization , SIAM review 52 (2010), no. 3, 471–501

    2010

  66. [74]

    6, 555–562

    R Tyrell Rockafellar, The multiplier method of hestenes and powell applied to conv ex programming, Journal of Optimization Theory and applications 12 (1973), no. 6, 555–562

    1973

  67. [75]

    1, 354–373

    R Tyrrell Rockafellar, A dual approach to solving nonlinear programming problems b y unconstrained optimization, Mathematical programming 5 (1973), no. 1, 354–373

    1973

  68. [76]

    2, 97–116

    , Augmented lagrangians and applications of the proximal poi nt algorithm in convex program- ming, Mathematics of operations research 1 (1976), no. 2, 97–116

    1976

  69. [77]

    Sungho Shin, Mihai Anitescu, and Fran¸ cois Pacaud,Accelerating optimal power flow with GPUs: SIMD abstraction of nonlinear programs and condensed-space int erior-point methods, Electric Power Systems Research 236 (2024), 110651

    2024

  70. [78]

    Paul Skrzypczyk and Daniel Cavalcanti, Semidefinite programming in quantum information science , IOP Publishing, 2023

    2023

  71. [79]

    1, 117–144

    Mario Souto, Joaquim D Garcia, and ´Alvaro Veiga, Exploiting low-rank structure in semidefinite pro- gramming by approximate operator splitting , Optimization 71 (2022), no. 1, 117–144

    2022

  72. [80]

    1-4, 625–653

    Jos F Sturm, Using sedumi 1.02, a matlab toolbox for optimization over sy mmetric cones, Optimization methods and software 11 (1999), no. 1-4, 625–653

    1999

  73. [81]

    6, 1105–1154

    , Implementation of interior point methods for mixed semidefi nite and second order cone opti- mization problems , Optimization methods and software 17 (2002), no. 6, 1105–1154

    2002

  74. [82]

    1, 87–115

    Defeng Sun, Kim-Chuan Toh, Yancheng Yuan, and Xin-Yuan Zha o, Sdpnal+: A matlab software for semidefinite programming with bound constraints (version 1 .0), Optimization Methods and Software 35 (2020), no. 1, 87–115

    2020

  75. [83]

    Michael J Todd, Semidefinite optimization , Acta Numerica 10 (2001), 515–560

    2001

  76. [84]

    3, 769–796

    Michael J Todd, Kim-Chuan Toh, and Reha H T¨ ut¨ unc¨ u,On the nesterov–todd direction in semidefinite programming, SIAM Journal on Optimization 8 (1998), no. 3, 769–796

    1998

  77. [85]

    1-4, 545–581

    Kim-Chuan Toh, Michael J Todd, and Reha H T¨ ut¨ unc¨ u,Sdpt3—a matlab software package for semidef- inite programming, version 1.3 , Optimization methods and software 11 (1999), no. 1-4, 545–581

    1999

  78. [86]

    4, 1454–1485

    Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher , Practical sketching algorithms for low-rank matrix approximation , SIAM Journal on Matrix Analysis and Applications 38 (2017), no. 4, 1454–1485

    2017

  79. [87]

    Reha H T¨ ut¨ unc¨ u, Kim-Chuan Toh, and Michael J Todd,Solving semidefinite-quadratic-linear programs using sdpt3 , Mathematical programming 95 (2003), 189–217

    2003

  80. [88]

    1, 49–95

    Lieven Vandenberghe and Stephen Boyd, Semidefinite programming , SIAM review 38 (1996), no. 1, 49–95. 34

    1996

  81. [89]

    3, 2577–2602

    Irene Waldspurger and Alden Waters, Rank optimality for the burer–monteiro factorization , SIAM journal on Optimization 30 (2020), no. 3, 2577–2602

    2020

  82. [90]

    Jie Wang and Liangbing Hu, Solving low-rank semidefinite programs via manifold optimi zation, arXiv preprint arXiv:2303.01722 (2023)

    2023 arXiv

  83. [91]

    3, 1361– 1390

    Yifei Wang, Kangkang Deng, Haoyang Liu, and Zaiwen Wen, A decomposition augmented lagrangian method for low-rank semidefinite programming , SIAM Journal on Optimization 33 (2023), no. 3, 1361– 1390

    2023

  84. [92]

    27, Springer Science & Business Media, 2012

    Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe, Handbook of semidefinite programming: theory, algorithms, and applications , vol. 27, Springer Science & Business Media, 2012

    2012

  85. [93]

    Nuoya Xiong, Lijun Ding, and Simon S Du, How over-parameterization slows down gradient descent in matrix sensing: The curses of symmetry and initializatio n, arXiv preprint arXiv:2310.01769 (2023)

    2023 arXiv

  86. [94]

    Yangyang Xu, Iteration complexity of inexact augmented lagrangian meth ods for constrained convex programming, Mathematical Programming 185 (2021), 199–244

    2021

  87. [95]

    3, 331–366

    Liuqin Yang, Defeng Sun, and Kim-Chuan Toh, Sdpnal+: a majorized semismooth newton-cg aug- mented lagrangian method for semidefinite programming with nonnegative constraints, Mathematical Programming Computation 7 (2015), no. 3, 331–366

    2015

  88. [96]

    Xinyang Yi, Dohyung Park, Yudong Chen, and Constantine Cara manis, Fast algorithms for robust pca via gradient descent , Advances in neural information processing systems 29 (2016)

    2016

  89. [97]

    2, 315–323

    Yi Yu, Tengyao Wang, and Richard J Samworth, A useful variant of the davis–kahan theorem for statisticians, Biometrika 102 (2015), no. 2, 315–323

    2015

  90. [98]

    7272–7281

    Alp Yurtsever, Olivier Fercoq, and Volkan Cevher, A conditional-gradient-based augmented lagrangian framework, International Conference on Machine Learning, PMLR, 2019, pp . 7272–7281

    2019

  91. [99]

    5727–5736

    Alp Yurtsever, Olivier Fercoq, Francesco Locatello, and Volkan Cevher, A conditional gradient frame- work for composite convex minimization with applications t o semidefinite programming , International conference on machine learning, PMLR, 2018, pp. 5727–5736

    2018

  92. [100]

    1, 171–200

    Alp Yurtsever, Joel A Tropp, Olivier Fercoq, Madeleine Udell, an d Volkan Cevher, Scalable semidefinite programming, SIAM Journal on Mathematics of Data Science 3 (2021), no. 1, 171–200

    2021

  93. [101]

    4, 1737–1765

    Xin-Yuan Zhao, Defeng Sun, and Kim-Chuan Toh, A newton-cg augmented lagrangian method for semidefinite programming, SIAM Journal on Optimization 20 (2010), no. 4, 1737–1765. A A weaker result on solution rank of the ALM subproblem We present a weaker result of Theorem 2 under a...

    2010

Pith tools

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