Pith. sign in

REVIEW 3 major objections 8 minor 66 references

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

T0 review · 3 major / 8 minor · reviewed 2026-07-10 · glm-5.2

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

Pith's one-line read PDHG on SDP converges linearly under either of two regularity conditions

desk verdict Clean local convergence theory for PDHG on SDP under two standard regularity conditions, plus an honest sublinear counterexample when both fail. read the letter →

arxiv 2607.08035 v1 pith:KEKVRLN2 submitted 2026-07-09 math.OC

Xin Jiang This is my paper · ORCID
classification math.OC
keywords pdhglocalconvergenceprimal-duallinearmethodprogrammingsemidefinite
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 studies the primal-dual hybrid gradient (PDHG) method applied to semidefinite programming (SDP), a convex optimization framework over the cone of positive semidefinite matrices. Global convergence theory for PDHG on SDP predicts only sublinear decay of the error, which suggests the method should slow down near the solution. This paper shows that, under either of two standard regularity conditions at the solution point, PDHG eventually enters a regime of (R-)linear convergence, where the error contracts by a fixed factor at each step. The two conditions are strict complementarity (the primal and dual matrices have complementary positive eigenspaces with no shared degenerate zero eigenspace) and primal-dual nondegeneracy (the affine constraints meet the tangent geometry of the PSD cone without hidden flat directions). The proof rests on viewing PDHG as a preconditioned proximal point method for the KKT (Karush-Kuhn-Tucker) inclusion, which yields a descent inequality in a problem-dependent metric. Under strict complementarity, the PSD cone projection is smooth near the solution, and the derivative of the PDHG map contracts directions normal to the local solution manifold. Under primal-dual nondegeneracy, the KKT mapping is strongly metrically subregular, providing a local error bound that combines with the descent inequality to give Q-linear convergence directly. The paper also constructs a small SDP instance where both conditions fail and shows that a formal local reduction of the PDHG map predicts sublinear decay at rate k^{-1/2}, which is confirmed numerically. This contrasts with linear programming, where the polyhedral geometry of the feasible set guarantees linear convergence even for degenerate instances.

What carries the argument

The key machinery is the interpretation of the PDHG iteration as the P-resolvent of the reduced KKT mapping F_KKT, where P is a block self-adjoint operator encoding the primal-dual stepsize coupling. This yields firm nonexpansiveness of the PDHG map in the P-metric. Under strict complementarity, the Fréchet derivative of the PSD cone projection (given by a Hadamard product formula involving eigenvalue ratios) linearizes the PDHG map, and the fixed-point set of this linearization equals the tangent space to the local KKT manifold. Under primal-dual nondegeneracy, strong metric subregularity of F_KKT provides the inequality ||z - z*||_P <= mu dist(0, F_KKT(z)), which combines with the descent/

What would settle it

A counterexample would be an SDP instance satisfying strict complementarity or primal-dual nondegeneracy for which PDHG (with stepsizes satisfying the stated condition) converges to the KKT point but the error does not eventually decay at a linear rate. Alternatively, a proof that the formal sublinear example in Section 6.1 actually converges linearly would contradict the paper's claim that regularity is needed.

Watch

Extended reading notes

Core claim

The central discovery is that PDHG, when applied to SDP, can be understood as a preconditioned proximal point method for the KKT inclusion, and that this viewpoint reduces the question of local linear convergence to the availability of a compatible local error bound. Under strict complementarity, the error bound comes from the spectral geometry of the PSD cone: the signed matrix Z* = X* - tau S* is nonsingular, so the cone projection is differentiable in a neighborhood, and the linearized PDHG map fixes exactly the tangent directions to the local KKT manifold while contracting all normal directions. Under primal-dual nondegeneracy, the error bound comes from strong metric subregularity of a

Load-bearing premise

The proofs of both convergence theorems assume that the PDHG iteration has already converged to a KKT point satisfying the respective regularity condition. Global convergence of the iterates to a KKT point is taken as a premise, not established within the local theory. If PDHG fails to converge for some SDP instance (e.g., due to numerical instability or an unfavorable stepsize choice), the local linear rate guarantees do not apply.

Editorial extensions

If this is right

  • Practitioners using PDHG for large-scale SDP can expect eventual linear convergence on instances where strict complementarity or primal-dual nondegeneracy holds, which are generic properties for many SDP classes.
  • The constructed sublinear example provides a concrete mechanism (nonlinear PSD-cone projection at a singular matrix) for why PDHG can stagnate on certain SDPs, guiding diagnosis of slow convergence in practice.
  • The separation of the two regularity conditions suggests that SDP solvers could be designed or adapted to detect which regime applies and adjust stepsize or restart strategies accordingly.
  • The contrast with LP (where linear convergence holds even without regularity) highlights that the nonpolyhedral geometry of the PSD cone is the fundamental obstruction, not the algorithm itself.
  • Finite-time rank identification of the primal iterate under strict complementarity provides a theoretical basis for low-rank exploitation in PDHG implementations after a transient phase.

Reading between the lines

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

  • The sublinear example suggests that for SDPs arising from relaxations of polynomial optimization (where strict complementarity can fail), PDHG may require restarts or acceleration to reach high accuracy, as the natural local rate can be as slow as O(k^{-1/2}).
  • The two distinct proof mechanisms (spectral smoothness vs. metric subregularity) may extend to other primal-dual proximal splitting methods beyond PDHG and ADMM, potentially yielding a unified local convergence theory for first-order methods on conic programs over nonpolyhedral cones.
  • If the stepsize condition tau*sigma*||A||^2 < 1 could be relaxed (e.g., to the larger ranges known for relaxed PDHG), the local linear convergence theory might still hold, but the proof would need a different Lyapunov function since the proximal point interpretation breaks down.
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 / 8 minor

Summary. This paper studies the local convergence behavior of the primal-dual hybrid gradient (PDHG) method applied to a standard primal-dual semidefinite programming (SDP) pair. The main results establish that PDHG converges eventually (R-)linearly whenever the limiting KKT point satisfies either strict complementarity (Theorem 1) or primal-dual nondegeneracy (Theorem 2). The proof of Theorem 1 exploits the smoothness of the PSD-cone projection near the nonsingular signed matrix Z* = X* - tau S* under strict complementarity, linearizes the PDHG fixed-point map, and proves uniform contraction of the normal component to the local KKT manifold. The proof of Theorem 2 uses the equivalence of primal-dual nondegeneracy to strong regularity of the KKT mapping, yielding strong metric subregularity, which is combined with the proximal-point descent inequality. A constructed SDP instance (Example 1) where both regularity conditions fail is shown, via formal asymptotic reduction and numerical evidence, to exhibit sublinear convergence. Numerical experiments on various SDP instances support the theory.

Significance. The paper addresses a well-motivated gap in the convergence theory of first-order methods for SDP. While global sublinear convergence of PDHG is well understood, the local linear regime — important for understanding practical high-accuracy behavior — had been established for LP (polyhedral case) and for ADMM on SDP, but not for PDHG on SDP. The two sufficient conditions (strict complementarity and primal-dual nondegeneracy) are classical and well-chosen, and the proof machinery is clean and modular: the preconditioned proximal point interpretation of PDHG, combined with either spectral geometry of the PSD cone or variational regularity of the KKT mapping, provides a transparent and reusable framework. The sublinear example (Example 1), while formally derived rather than rigorously proved, is a valuable contribution that sharpens the contrast with LP and is honestly disclosed. The numerical experiments cover a broad range of instances and honestly report difficult cases. Reproducible code is provided. The results are of clear interest to the optimization community.

major comments (3)
  1. Abstract and Theorem statements vs. Example 1: The abstract states 'We also give a simple SDP instance where both regularity conditions fail and PDHG can converge only sublinearly.' However, as disclosed in Section 6.1, Example 1 provides a formal local asymptotic reduction and numerical evidence, not a rigorous proof of sublinear convergence. The formal calculation (alpha_{k+1} = alpha_k - alpha_k^3 + O(alpha_k^5)) is plausible and the numerical evidence in Figure 3 is consistent, but the claim as stated in the abstract is stronger than what is proved. The authors should either (a) soften the abstract statement to match the formal nature of the result (e.g., 'we present an SDP instance where a formal local reduction predicts sublinear convergence, supported by numerical evidence'), or (b) upgrade Example 1 to a rigorous proof. Option (a) is sufficient given that the main positive theore
  2. Section 4.3, Theorem 1, proof of Eq. (22): The passage from dist_P(z_k, M) to dist((X_k, y_k, S_k), Omega*) uses the local representation of the KKT set M from Lemma 1. The argument constructs z_k_bar = Pi_P^{aff M}(z_k) in M and then (X_k_bar, y_k_bar, S_k_bar) in Omega*. The bound dist((X_k, y_k, S_k), Omega*) <= kappa_2 ||z_k - z_k_bar||_P is stated with a constant kappa_2 > 0 but the dependence on the relationship between the P-metric and the Frobenius/Euclidean product norm is not made explicit. Since P is a fixed positive definite operator (depending on tau, sigma, A), norm equivalence gives such a constant, but the reader would benefit from a one-line justification confirming that kappa_2 is independent of k and depends only on P, A, tau, sigma.
  3. Section 5, Theorem 2: The proof establishes Q-linear convergence of (X_k, y_k) to (X*, y*) in the P-metric under primal-dual nondegeneracy. The uniqueness of the KKT point under primal-dual nondegeneracy is invoked (citing [16, Theorem 18] for the equivalence to strong regularity). It would strengthen the result to state explicitly in the theorem or its proof that primal-dual nondegeneracy implies uniqueness of the KKT point, so that the strong metric subregularity estimate (7) — which bounds the distance to the specific point z* — is applicable. This is mentioned in the proof text but not in the theorem statement, and the logical flow (nondegeneracy => strong regularity => strong metric subregularity => Q-linear convergence) should be made fully transparent.
minor comments (8)
  1. Abstract: The phrase 'PDHG can converge only sublinearly' overstates Example 1, which is a formal reduction plus numerics, not a proved theorem. Consider rewording to 'a formal local reduction predicts sublinear convergence, supported by numerical evidence.'
  2. Assumptions 2 and 3 (Sections 3.3 and 3.4): Each assumes that the PDHG iteration converges to a KKT point satisfying the respective regularity condition. This is standard for local convergence analysis and is justified by existing global convergence theory under the stepsize condition (3), but a brief remark explicitly citing the global convergence result (e.g., [14,15]) that guarantees convergence under (3) would help the reader understand that the assumptions are not vacuous.
  3. Section 6.1, Example 1: The formal expansion is carried out to O(alpha^5). It would help the reader to briefly state why the expansion is truncated at this order (i.e., that the leading-order dynamics alpha_{k+1} = alpha_k - alpha_k^3 + O(alpha_k^5) are sufficient to determine the asymptotic rate, and higher-order terms do not change the leading behavior for sufficiently small alpha).
  4. Section 4.2, Eq. (14): The derivative G_z of the PDHG map R is stated. A brief remark that this follows from the chain rule applied to the resolvent representation (12) and the Fréchet differentiability of Pi_{S^n_+} (cited from [52, Theorem 4.6]) would aid readers less familiar with the PSD projection derivative.
  5. Figure 1 caption: The caption states 'In all four instances, PDHG with fixed stepsizes eventually exhibits local linear convergence.' However, panel (d) corresponds to the sublinear example (Example 1) where both SC and ND fail. The caption appears to contradict the sublinear prediction. Clarification is needed — perhaps panel (d) of Figure 1 is a different instance from Example 1, or the caption should note that the linear regime in (d) is observed only over a finite horizon.
  6. Section 7.2: The two possible explanations for slow convergence (contraction factor near 1 vs. local linear regime not yet reached) are discussed. It would be useful to note whether the diagnostic sqrt(k) * ||X_k - X*||_F (used in Figure 3 for Example 1) was also checked for the instances in Figure 8, as this could help distinguish the two explanations.
  7. Table 1: The column headers 'n' and 'm' are used without explicit definition in the table caption. While they are defined earlier in the paper (n is the matrix dimension, m is the number of constraints), restating this in the caption would make the table self-contained.
  8. References: Several references have incomplete or future-dated publication information (e.g., [5] 'Mathematical Programming Computation, 2026'; [7] 'Optimization Letters, 20(3):503-520, 2026'; [47] 'Mathematical Programming, 2026'). These should be updated with final publication details if available.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; derivation chain is self-contained with independently established building blocks

full rationale

The paper's two main positive results (Theorems 1 and 2) are proved in full within the manuscript. The load-bearing ingredients are: (1) the proximal point interpretation of PDHG, attributed to He & Yuan [32] and O'Connor & Vandenberghe [48] — independently established by multiple groups; (2) Fréchet differentiability of the PSD cone projection, from Sun & Sun [52] — a standard result in matrix analysis; (3) equivalence of primal-dual nondegeneracy to strong regularity, from Chan & Sun [16] — an independent theorem; (4) strong regularity implying strong metric subregularity, from Dontchev & Rockafellar [21] — a standard variational analysis result. The self-citations present ([33,34] Jiang & Vandenberghe, [35] Kang, Jiang, Yang) are used for supplementary purposes: the equivalent SDP construction for WLOG diagonalization, and the ADMM comparison in Section 6.2. None of these self-citations are load-bearing for the main convergence theorems. Lemmas 1-3 and both theorems are proved directly in the paper text. The sublinear example (Example 1) is constructed from first principles via a formal asymptotic expansion, and the paper is transparent that it is a formal reduction rather than a rigorous proof. No step in the derivation chain reduces to its own inputs by construction, and no prediction is equivalent to a fitted parameter. The derivation is self-contained against external benchmarks and standard mathematical results.

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

No new entities, particles, or postulated objects are introduced. The analysis uses standard objects from SDP theory (KKT mappings, tangent/normal cones, resolvent operators) and established regularity conditions. The P-metric (equation 10) is a standard construction in PDHG analysis.

free parameters (3)
  • Stepsizes τ, σ = Various per instance (Table 1)
    Fixed throughout each run; chosen to satisfy τσ‖A‖² < 1. Not fitted to the convergence result.
  • Contraction factor ρ_SC = Derived, not fitted
    Arises from the spectral gap and geometry; not a free parameter.
  • Error bound constant μ = Derived from strong metric subregularity
    Existence guaranteed by nondegeneracy; not fitted.
assumptions (5)
  • domain assumption PDHG converges to a KKT point satisfying the respective regularity condition (Assumptions 2, 3).
    The local convergence theory is conditional on global convergence to a regular KKT point. This is standard in the local convergence literature but is not proved here.
  • domain assumption The linear operator A is surjective and the KKT set is nonempty (Assumption 1).
    Standard SDP regularity assumption; ensures existence of solutions.
  • standard math PDHG is the P-resolvent of the reduced KKT mapping (equation 12).
    Established result from He & Yuan 2012 [32] and O'Connor & Vandenberghe 2020 [48].
  • standard math Primal-dual nondegeneracy implies strong regularity of the KKT mapping.
    Chan & Sun 2008 [16, Theorem 18]. Used in Section 3.4 to derive the error bound.
  • standard math Fréchet differentiability of the PSD cone projection at nonsingular matrices.
    Sun & Sun 2002 [52, Theorem 4.6]. Used in Section 4.2 to linearize the PDHG map.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Local Linear Convergence of the Primal-Dual Hybrid Gradient Method for Semidefinite Programming." pith.science (2026). https://pith.science/paper/KEKVRLN2

@misc{pith2026260708035,
  author       = {Pith},
  title        = {Pith review of: Local Linear Convergence of the Primal-Dual Hybrid Gradient Method for Semidefinite Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KEKVRLN2}},
  note         = {Machine review of arXiv:2607.08035}
}
read the original abstract

Primal-dual first-order methods are widely used for large-scale semidefinite programming (SDP), but their ability to compute highly accurate solutions is not well explained by global convergence theory alone. We study the local convergence of the primal-dual hybrid gradient (PDHG) method applied to a standard primal--dual SDP pair. We show that PDHG converges eventually (R-)linearly whenever the limiting KKT point satisfies either strict complementarity or primal--dual nondegeneracy. The proof views PDHG as a preconditioned proximal point method for the KKT inclusion and combines its descent inequality with a local error bound. Under strict complementarity, the error bound follows from the local spectral geometry of the positive semidefinite cone; under primal-dual nondegeneracy, it follows from strong regularity of the KKT mapping. We also give a simple SDP instance where both regularity conditions fail and PDHG can converge only sublinearly. This contrasts with linear programming, where PDHG admits a local linear convergence regime even for degenerate instances. Numerical experiments support the theory and identify difficult SDP instances where PDHG struggles to reach high accuracy.

Figures

Figures reproduced from arXiv: 2607.08035 by the authors.

Figure 1
Figure 1. Convergence behavior on four simple SDP instances with different combinations of strict comple [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Relationships among strict complementarity (SC), primal/dual nondegeneracy (ND), primal/dual [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Numerical behavior of PDHG for the SDP in [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: PDHG convergence on MaxCut SDP instances. The red and blue curves report the KKT residual [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]
Figure 5
Figure 5. Figure 5: PDHG convergence on random QS problems. The red and blue curves report the KKT residual [PITH_FULL_IMAGE:figures/full_fig_p020_5.png]
Figure 6
Figure 6. Figure 6: PDHG convergence on synthetic SDP instances. The unique KKT point satisfies primal–dual [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]
Figure 7
Figure 7. Figure 7: PDHG convergence on structure-from-motion problems. The red and blue curves report the KKT [PITH_FULL_IMAGE:figures/full_fig_p021_7.png]
Figure 8
Figure 8. Figure 8: PDHG convergence on additional SDP instances. The red and blue curves report the KKT residual [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 66 canonical work pages

  1. [1]

    Aguirre, Diego Cifuentes, Vincent Guigues, Renato D

    Jacob M. Aguirre, Diego Cifuentes, Vincent Guigues, Renato D. C. Monteiro, Victor Hugo Nascimento, and Arnesh Sujanani. cuHALLaR: A GPU accelerated low-rank augmented lagrangian method for large-scale semidefinite programming.arXiv preprint, arXiv:2505.13719, 2025

    work page arXiv 2025

  2. [2]

    Interior point methods in semidefinite programming with applications to combinatorial optimization.SIAM Journal on Optimization, 5(1):13–51, 1995

    Farid Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization.SIAM Journal on Optimization, 5(1):13–51, 1995

    work page 1995

  3. [3]

    Haeberly, and Michael L

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

    work page 1997

  4. [4]

    Practicallarge-scalelinearprogrammingusingprimal-dualhybridgradient

    David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and WarrenSchudy. Practicallarge-scalelinearprogrammingusingprimal-dualhybridgradient. InAdvances in Neural Information Processing Systems, volume 34, pages 20243–20257, 2021

    work page 2021

  5. [5]

    PDLP: A practical first-order method for large-scale linear programming.Mathematical Programming Computation, 2026

    David Applegate, Mateo Díaz, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O’Donoghue, and Warren Schudy. PDLP: A practical first-order method for large-scale linear programming.Mathematical Programming Computation, 2026

    work page 2026

  6. [6]

    Faster first-order primal-dual methods for linear programming using restarts and sharpness.Mathematical Programming, 201(1–2):133–184, 2023

    David Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness.Mathematical Programming, 201(1–2):133–184, 2023

    work page 2023

  7. [7]

    The Chambolle–Pock method converges weakly withθ >1/2andτ σ∥L∥ 2 <4/(1 + 2θ).Optimization Letters, 20(3):503–520, 2026

    Sebastian Banert, Manu Upadhyaya, and Pontus Giselsson. The Chambolle–Pock method converges weakly withθ >1/2andτ σ∥L∥ 2 <4/(1 + 2θ).Optimization Letters, 20(3):503–520, 2026

    work page 2026

  8. [8]

    Bauschke and Patrick L

    Heinz H. Bauschke and Patrick L. Combettes.Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Cham, 2 edition, 2017

    work page 2017

Show all 66 references
  1. [9]

    Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan.Linear Matrix Inequalities in System and Control Theory, volume 15 ofStudies in Applied Mathematics

    Stephen P. Boyd, Laurent El Ghaoui, Eric Feron, and Venkataramanan Balakrishnan.Linear Matrix Inequalities in System and Control Theory, volume 15 ofStudies in Applied Mathematics. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1994

    1994

  2. [10]

    Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein

    Stephen P. Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers.Foundations and Trends in Machine Learning, 3(1):1–122, 2011

    2011

  3. [11]

    Boyd and Lieven Vandenberghe.Convex Optimization

    Stephen P. Boyd and Lieven Vandenberghe.Convex Optimization. Cambridge University Press, Cam- bridge, 2004

    2004

  4. [12]

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

    2003

  5. [13]

    Samuel Burer and Renato D. C. Monteiro. Local minima and convergence in low-rank semidefinite programming.Mathematical Programming, 103(3):427–444, 2005

    2005

  6. [14]

    A first-order primal-dual algorithm for convex problems with applications to imaging.Journal of Mathematical Imaging and Vision, 40(1):120–145, 2011

    Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging.Journal of Mathematical Imaging and Vision, 40(1):120–145, 2011

    2011

  7. [15]

    On the ergodic convergence rates of a first-order primal–dual algorithm.Mathematical Programming, 159(1–2):253–287, 2016

    Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of a first-order primal–dual algorithm.Mathematical Programming, 159(1–2):253–287, 2016

    2016

  8. [16]

    Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming.SIAM Journal on Optimization, 19(1):370–396, 2008

    Zi Xian Chan and Defeng Sun. Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming.SIAM Journal on Optimization, 19(1):370–396, 2008

    2008

  9. [17]

    A golden ratio primal-dual algorithm for structured convex opti- mization.Journal of Scientific Computing, 87(2):47, 2021

    Xiaokai Chang and Junfeng Yang. A golden ratio primal-dual algorithm for structured convex opti- mization.Journal of Scientific Computing, 87(2):47, 2021. 23

    2021

  10. [18]

    HPR-LP: An imple- mentation of an HPR method for solving linear programming.Mathematical Programming Computation, 2025

    Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, and Xinyuan Zhao. HPR-LP: An imple- mentation of an HPR method for solving linear programming.Mathematical Programming Computation, 2025

    2025

  11. [19]

    On the global and linear convergence of the generalized alternating direction method of multipliers.Journal of Scientific Computing, 66(3):889–916, 2016

    Wei Deng and Wotao Yin. On the global and linear convergence of the generalized alternating direction method of multipliers.Journal of Scientific Computing, 66(3):889–916, 2016

    2016

  12. [20]

    New understandings and computation on augmented la- grangian methods for low-rank semidefinite programming.arXiv preprint, arXiv:2505.15775, 2025

    Lijun Ding, Haihao Lu, and Jinwen Yang. New understandings and computation on augmented la- grangian methods for low-rank semidefinite programming.arXiv preprint, arXiv:2505.15775, 2025

    2025 arXiv

  13. [21]

    Dontchev and R

    Asen L. Dontchev and R. Tyrrell Rockafellar. Regularity and conditioning of solution mappings in variational analysis.Set-Valued Analysis, 12(1–2):79–109, 2004

    2004

  14. [22]

    Dmitriy Drusvyatskiy and Adrian S. Lewis. Optimality, identifiability, and sensitivity.Mathematical Programming, 147(1–2):467–498, 2014

    2014

  15. [23]

    Bertsekas

    Jonathan Eckstein and Dimitri P. Bertsekas. On the Douglas–Rachford splitting method and the prox- imal point algorithm for maximal monotone operators.Mathematical Programming, 55(1–3):293–318, 1992

    1992

  16. [24]

    Ageneralframeworkforaclassoffirstorderprimal-dual algorithms for convex optimization in imaging science.SIAM Journal on Imaging Sciences, 3(4):1015– 1046, 2010

    ErnieEsser, XiaoqunZhang, andTonyF.Chan. Ageneralframeworkforaclassoffirstorderprimal-dual algorithms for convex optimization in imaging science.SIAM Journal on Imaging Sciences, 3(4):1015– 1046, 2010

    2010

  17. [25]

    A dual algorithm for the solution of nonlinear variational problems via finite element approximation.Computers and Mathematics with Applications, 2(1):17–40, 1976

    Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation.Computers and Mathematics with Applications, 2(1):17–40, 1976

    1976

  18. [26]

    Pontus Giselsson and Stephen P. Boyd. Linear convergence and metric selection for Douglas–Rachford splitting and ADMM.IEEE Transactions on Automatic Control, 62(2):532–544, 2017

    2017

  19. [27]

    cuADMM: GPU-accelerated first-order optimiza- tion for large-scale multi-block semidefinite programs

    Antoine Groudiev, Shucheng Kang, and Heng Yang. cuADMM: GPU-accelerated first-order optimiza- tion for large-scale multi-block semidefinite programs. In2025 RSS Workshop on Fast Motion Planning and Control in the Era of Parallelism, 2025

    2025

  20. [28]

    Linear rate convergence of the alternating direction method of multipliers for convex composite programming.Mathematics of Operations Research, 43(2):622–637, 2018

    Deren Han, Defeng Sun, and Liwei Zhang. Linear rate convergence of the alternating direction method of multipliers for convex composite programming.Mathematics of Operations Research, 43(2):622–637, 2018

    2018

  21. [29]

    Building Romewith convexoptimization

    Haoyu Han and HengYang. Building Romewith convexoptimization. InRobotics: Science and Systems, 2025

    2025

  22. [30]

    A low-rank ADMM splitting approach for semidefinite programming.INFORMS Journal on Computing, 2025

    Qiushi Han, Chenxi Li, Zhenwei Lin, Caihua Chen, Qi Deng, Dongdong Ge, Huikang Liu, and Yinyu Ye. A low-rank ADMM splitting approach for semidefinite programming.INFORMS Journal on Computing, 2025

    2025

  23. [31]

    A generalized primal-dual algorithm with improved convergence condition for saddle point problems.SIAM Journal on Imaging Sciences, 15(3):1157–1183, 2022

    Bingsheng He, Feng Ma, Shengjie Xu, and Xiaoming Yuan. A generalized primal-dual algorithm with improved convergence condition for saddle point problems.SIAM Journal on Imaging Sciences, 15(3):1157–1183, 2022

    2022

  24. [32]

    Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective.SIAM Journal on Imaging Sciences, 5(1):119–149, 2012

    Bingsheng He and Xiaoming Yuan. Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective.SIAM Journal on Imaging Sciences, 5(1):119–149, 2012

    2012

  25. [33]

    Bregman primal-dual first-order method and applications to sparse semidefinite programming.Computational Optimization and Applications, 81(1):127–159, 2022

    Xin Jiang and Lieven Vandenberghe. Bregman primal-dual first-order method and applications to sparse semidefinite programming.Computational Optimization and Applications, 81(1):127–159, 2022

    2022

  26. [34]

    Bregman three-operator splitting methods.Journal of Optimiza- tion Theory and Applications, 196(3):936–972, 2023

    Xin Jiang and Lieven Vandenberghe. Bregman three-operator splitting methods.Journal of Optimiza- tion Theory and Applications, 196(3):936–972, 2023. 24

    2023

  27. [35]

    Local linear convergence of the alternating direction method of multipliers for semidefinite programming under strict complementarity.arXiv preprint, arXiv:2503.20142, 2025

    Shucheng Kang, Xin Jiang, and Heng Yang. Local linear convergence of the alternating direction method of multipliers for semidefinite programming under strict complementarity.arXiv preprint, arXiv:2503.20142, 2025

    2025 arXiv

  28. [36]

    Local second-order limit dynamics of ADMM for SDP.arXiv preprint, 2026

    Shucheng Kang and Heng Yang. Local second-order limit dynamics of ADMM for SDP.arXiv preprint, 2026

    2026

  29. [37]

    Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers.arXiv preprint, 2024

    Guanghui Lan and Tianjiao Li. Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers.arXiv preprint, 2024

    2024

  30. [38]

    Lasserre.Moments, Positive Polynomials and Their Applications

    Jean B. Lasserre.Moments, Positive Polynomials and Their Applications. Imperial College Press Optimization Series. Imperial College Press, London, 2009

    2009

  31. [39]

    Activesets, nonsmoothness, andsensitivity.SIAM Journal on Optimization, 13(3):702– 725, 2002

    AdrianS.Lewis. Activesets, nonsmoothness, andsensitivity.SIAM Journal on Optimization, 13(3):702– 725, 2002

    2002

  32. [40]

    D-PDLP: Scaling PDLP to distributed multi-GPU systems.arXiv preprint, arXiv:2601.07628, 2026

    Hongpei Li, Yicheng Huang, Huikang Liu, Dongdong Ge, and Yinyu Ye. D-PDLP: Scaling PDLP to distributed multi-GPU systems.arXiv preprint, arXiv:2601.07628, 2026

    2026 arXiv

  33. [41]

    Local convergence properties of Douglas–Rachford and alternating direction method of multipliers.Journal of Optimization Theory and Applications, 172(3):874–913, 2017

    Jingwei Liang, Jalal Fadili, and Gabriel Peyré. Local convergence properties of Douglas–Rachford and alternating direction method of multipliers.Journal of Optimization Theory and Applications, 172(3):874–913, 2017

    2017

  34. [42]

    PDCS: A primal–dual large-scale conic pro- gramming solver with GPU enhancements.arXiv preprint, arXiv:2505.00311, 2025

    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

  35. [43]

    cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia.Operations Research, 73(6):3440–3452, 2025

    Haihao Lu and Jinwen Yang. cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia.Operations Research, 73(6):3440–3452, 2025

    2025

  36. [44]

    On the geometry and refined rate of primal–dual hybrid gradient for linear programming.Mathematical Programming, 212:349–387, 2025

    Haihao Lu and Jinwen Yang. On the geometry and refined rate of primal–dual hybrid gradient for linear programming.Mathematical Programming, 212:349–387, 2025

    2025

  37. [45]

    Understanding the convergence of the preconditioned PDHG method: A view of indefinite proximal ADMM.Journal of Scientific Computing, 94(3):60, 2023

    Yumin Ma, Xingju Cai, Bo Jiang, and Deren Han. Understanding the convergence of the preconditioned PDHG method: A view of indefinite proximal ADMM.Journal of Scientific Computing, 94(3):60, 2023

    2023

  38. [46]

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

    2020

  39. [47]

    Renato D. C. Monteiro, Arnesh Sujanani, and Diego Cifuentes. A low-rank augmented lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach.Math- ematical Programming, 2026

    2026

  40. [48]

    On the equivalence of the primal-dual hybrid gradient method and Douglas–Rachford splitting.Mathematical Programming, 179(1–2):85–108, 2020

    Daniel O’Connor and Lieven Vandenberghe. On the equivalence of the primal-dual hybrid gradient method and Douglas–Rachford splitting.Mathematical Programming, 179(1–2):85–108, 2020

    2020

  41. [49]

    An algorithm for minimizing the Mumford–Shah functional

    Thomas Pock, Daniel Cremers, Horst Bischof, and Antonin Chambolle. An algorithm for minimizing the Mumford–Shah functional. InProceedings of the IEEE International Conference on Computer Vision, pages 1133–1140, 2009

    2009

  42. [50]

    Tyrrell Rockafellar

    R. Tyrrell Rockafellar. Monotone operators and the proximal point algorithm.SIAM Journal on Control and Optimization, 14(5):877–898, 1976

    1976

  43. [51]

    Jos F. Sturm. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones.Opti- mization Methods and Software, 11(1–4):625–653, 1999

    1999

  44. [52]

    Semismooth matrix-valued functions.Mathematics of Operations Research, 27(1):150–169, 2002

    Defeng Sun and Jie Sun. Semismooth matrix-valued functions.Mathematics of Operations Research, 27(1):150–169, 2002. 25

    2002

  45. [53]

    A preconditioned augmented Lagrangian method for solving semidefinite programming problems.arXiv preprint, arXiv:2605.17089, 2026

    Tianyun Tang and Kim-Chuan Toh. A preconditioned augmented Lagrangian method for solving semidefinite programming problems.arXiv preprint, arXiv:2605.17089, 2026

    2026 arXiv

  46. [54]

    Michael J. Todd. Semidefinite optimization.Acta Numerica, 10:515–560, 2001

    2001

  47. [55]

    Tütüncü, and Michael J

    Kim-Chuan Toh, Reha H. Tütüncü, and Michael J. Todd.SDPT3 Version 3.02: A MATLAB Soft- ware for Semidefinite-Quadratic-Linear Programming, 2002. Available athttps://www.math.cmu.edu/ ~reha/sdpt3.html

    2002

  48. [56]

    The Chambolle–Pock method also converges weakly with0< θ≤1andτ σ∥L∥ 2 < 4θ(2−θ)/(1−2θ+ 9θ 2 −4θ 3).arXiv preprint, 2026

    Manu Upadhyaya. The Chambolle–Pock method also converges weakly with0< θ≤1andτ σ∥L∥ 2 < 4θ(2−θ)/(1−2θ+ 9θ 2 −4θ 3).arXiv preprint, 2026

    2026

  49. [57]

    Andersen

    Lieven Vandenberghe and Martin S. Andersen. Chordal graphs and semidefinite optimization.Founda- tions and Trends in Optimization, 1(4):241–433, 2015

    2015

  50. [58]

    Lieven Vandenberghe and Stephen P. Boyd. Semidefinite programming.SIAM Review, 38(1):49–95, 1996

    1996

  51. [59]

    Solving low-rank semidefinite programs via manifold optimization.Journal of Scientific Computing, 104(1):33, 2025

    Jie Wang and Liangbing Hu. Solving low-rank semidefinite programs via manifold optimization.Journal of Scientific Computing, 104(1):33, 2025

    2025

  52. [60]

    A tuning-free primal-dual splitting algorithm for large-scale semidefinite programming.arXiv preprint, arXiv:2402.00311, 2024

    Yinjun Wang, Haixiang Lan, and Yinyu Ye. A tuning-free primal-dual splitting algorithm for large-scale semidefinite programming.arXiv preprint, arXiv:2402.00311, 2024

    2024 arXiv

  53. [61]

    Alternating direction augmented lagrangian methods for semidefinite programming.Mathematical Programming Computation, 2(3–4):203–230, 2010

    Zaiwen Wen, Donald Goldfarb, and Wotao Yin. Alternating direction augmented lagrangian methods for semidefinite programming.Mathematical Programming Computation, 2(3–4):203–230, 2010

    2010

  54. [62]

    Kluwer Academic Publishers, Boston, MA, 2000

    Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe, editors.Handbook of Semidefinite Pro- gramming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Boston, MA, 2000

    2000

  55. [63]

    Stephen J. Wright. Identifiable surfaces in constrained optimization.SIAM Journal on Control and Optimization, 31(4):1063–1079, 1993

    1993

  56. [64]

    Heng Yang, Ling Liang, Luca Carlone, and Kim-Chuan Toh. An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization.Mathematical Programming, 201(1–2):409–472, 2023

    2023

  57. [65]

    SDPNAL+: A majorized semismooth Newton-CG augmentedlagrangianmethodforsemidefiniteprogrammingwithnonnegativeconstraints.Mathematical Programming Computation, 7(3):331–366, 2015

    Liuqin Yang, Defeng Sun, and Kim-Chuan Toh. SDPNAL+: A majorized semismooth Newton-CG augmentedlagrangianmethodforsemidefiniteprogrammingwithnonnegativeconstraints.Mathematical Programming Computation, 7(3):331–366, 2015

    2015

  58. [66]

    A Newton-CG augmented lagrangian method for semidefinite programming.SIAM Journal on Optimization, 20(4):1737–1765, 2010

    Xinyuan Zhao, Defeng Sun, and Kim-Chuan Toh. A Newton-CG augmented lagrangian method for semidefinite programming.SIAM Journal on Optimization, 20(4):1737–1765, 2010. 26

    2010

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.