Local linear convergence of the primal-dual hybrid gradient algorithm for semidefinite programming
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: I'm Ada.
Emmy: And I'm Emmy, here with Kolya.
Ada: We're looking at the paper: "Local linear convergence of the primal-dual hybrid gradient algorithm for semidefinite programming".
Paper summary: Ada: To recap where we are, we've seen that the paper "Local linear convergence of the primal-dual hybrid gradient algorithm for semidefinite programming" studies the local convergence of this primal-dual hybrid gradient method applied to a standard primal-dual SDP pair. The core claim is that this method converges eventually at an R-linear rate if the limiting KKT point satisfies either strict complementarity or primal-dual nondegeneracy.
Emmy: They achieve this by viewing the primal-dual hybrid gradient method as a preconditioned proximal point method for the KKT inclusion and combining its descent inequality with a local error bound. Under strict complementarity, that error bound follows from the local spectral geometry of the positive semidefinite cone.
Kolya: And for primal-dual nondegeneracy, they show that it follows from strong regularity of the KKT mapping, which is a different mechanism entirely from the strict complementarity one.
Ada: The paper also highlights an important contrast by providing a simple semidefinite program instance where both strict complementarity and primal-dual nondegeneracy fail, and they prove that PDHG can only converge sublinearly in that case.
Emmy: This contrasts with linear programming, where a special case of the same method identifies a two-phase phenomenon: after an initial global phase, the iterates enter a local phase governed by the active geometry of the optimal face and then converge at an R-linear rate for linear programming.
Kolya: So what this means for us in practice is that we need to check if our SDP solution has those structural properties before we can expect that local linear speed. It’s not just a matter of running the algorithm; it's about understanding the geometry of the problem you're solving.
Ada: Exactly. The paper title itself points to this shift in focus from global theory to local behavior, and it suggests that for large scale SDP solvers, knowing where you are in your solution space—whether strict complementarity or nondegeneracy holds—is what determines how fast you can expect the algorithm to converge locally.
Emmy: It gives us a framework for understanding why some first-order methods are more reliable than others when high precision is needed, by linking convergence rate directly to the structure of the solution point itself.
Conclusion: Ada: So looking at the paper "Local linear convergence of the primal-dual hybrid gradient algorithm for semidefinite programming," what we really learned is that this method converges locally linearly if you have strict complementarity or primal-dual nondegeneracy at the limiting KKT point.
Emmy: That’s right, and it’s important to remember that this isn't guaranteed just by running the algorithm; it depends on whether those specific geometric conditions are satisfied by the solution you are targeting.
Kolya: And for someone who only listens to the show, this means if your SDP has these structural properties, you can expect a fast local convergence rate, which is much better than the sublinear rates we usually see in global theory when those conditions aren't met.
Ada: It’s about understanding the structure of the solution point and how that structure dictates the local speed of convergence for this primal-dual hybrid gradient algorithm.
Emmy: The authors show us a way to identify those structural checkpoints—strict complementarity or primal-dual nondegeneracy—that unlock that local linear regime, which is a key finding for understanding first-order methods in optimization.
Xin Jiang
University of Houston
math.OC
Submitted: 2026-07-09
Updated: 2026-11-16
Code: https://github.com/NumOptLab/pdhg-sdp-linear-conv
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 79/100
The gist: 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…
Key concepts
- Primal–Dual Hybrid Gradient (PDHG)
- PDHG is an iterative first-order method used to solve optimization problems, particularly SDPs. It combines gradient descent steps with projections onto constraints (like the positive semidefinite cone). The paper analyzes its local convergence properties, treating it as a preconditioned proximal point method for the KKT inclusion.
- Strict Complementarity
- This is a regularity condition where the solution to an optimization problem has no zero values in certain constraint sets. In this context, it means that the set of active constraints at the solution has a fixed structure, which allows for smooth analysis of how the algorithm approaches the optimal point.
- Primal–Dual Nondegeneracy
- This condition relates to how strongly regular the KKT mapping is at a solution. When this holds, it implies strong metric subregularity of the reduced KKT mapping. This strong regularity allows for a direct derivation of local Q-linear convergence rates for the PDHG algorithm.
Terminology
Summary
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. p. 0 We study the local convergence of the primal–dual hybrid gradient (PDHG) method applied to a standard primal–dual SDP pair. p. 0 We show that PDHG converges eventually (R-)linearly whenever the limiting KKT point satisfies either strict complementarity or primal–dual nondegeneracy. p. 0
Problem Formulation and Method Structure
The paper considers the primal–dual pair of semidefinite programs (SDPs) defined by minimizing a linear objective subject to linear equality constraints and positivity constraints on the variables. The PDHG algorithm is presented in its iteration form involving projections onto the PSD cone and applications of linear maps A and A∗. p. 0 The stepsizes are fixed throughout the paper and satisfy a specific condition related to the operator norm of A. p. 1 This simple structure makes PDHG attractive for large-scale SDPs. p. 1
Regularity Conditions and Theoretical Proofs
The local convergence theory is developed by viewing PDHG as a preconditioned proximal point method for the KKT inclusion. The authors obtain local error bounds under two classical regularity conditions: strict complementarity and primal–dual nondegeneracy. p. 1 Strict complementarity is spectral, giving an error bound through the local spectral geometry of the PSD cone. p. 1 Primal–dual nondegeneracy is variational, providing an error bound through strong regularity of the KKT mapping. p. 1 The paper shows that either mechanism is sufficient for local R-linear convergence of PDHG. p. 1
Convergence under Strict Complementarity
Under strict complementarity, the analysis relies on the fact that the PSD-cone projection is smooth near the limiting signed matrix and the local KKT set has a fixed face structure. The PDHG map is rewritten as a fixed-point iteration in a metric P, where R is shown to be firmly nonexpansive in the P-metric. p. 8 This allows for the differentiation of the map locally by differentiating the projection onto the positive semidefinite cone. p. 8 The resulting local linearization contracts all directions normal to the local KKT manifold. p. 9
Convergence under Primal–Dual Nondegeneracy
When the limit KKT point is primal–dual nondegenerate, the KKT mapping is strongly metrically subregular at the solution. This error bound bypasses the need to differentiate the PSD-cone projection and directly gives local Q-linear convergence to the KKT point. p. 5 The analysis shows that primal–dual nondegeneracy yields strong metric subregularity of the reduced KKT mapping FKKT. p. 6 This property is used to establish a contraction factor ρND in the P-metric, leading to Q-linear convergence. p. 3
Discussion and Limitations
The paper contrasts the behavior of PDHG with linear programming by noting that the PSD cone is nonpolyhedral, which prevents simple polyhedral geometry arguments. The authors present an SDP instance where both strict complementarity and primal–dual nondegeneracy fail, suggesting that without additional regularity, PDHG may fail to enter a local linear regime. p. 1 Furthermore, the paper discusses open questions regarding the parameter ranges of relaxed PDHG iterations and whether the distinction between ADMM and PDHG analyses is specific to these methods. p. 3 The numerical experiments confirm that local linear convergence is observed under different combinations of regularity conditions. p. 2
Conclusion
We established local linear convergence of the primal–dual hybrid gradient (PDHG) algorithm for semidefinite programming (SDP) under two regularity assumptions: if the limit KKT point of PDHG satisfies strict complementarity or primal–dual nondegeneracy, then the convergence is eventually (R-)linear. The proof leverages the interpretation of PDHG as a preconditioned proximal point method. p. 1 Under strict complementarity, the PSD-cone projection is smooth near the limiting signed matrix and the local KKT set has a fixed face structure. p. 3 Under primal–dual nondegeneracy, a local error bound follows from strong metric subregularity of the KKT mapping. p. 0 Combining these local properties with the descent property of PDHG gives the eventual linear rate. p. 1 Moreover, we constructed a small SDP instance for which a formal local reduction of the PDHG map predicts sublinear convergence when both regularity conditions fail. p. 1 The numerical behavior is consistent with this prediction, suggesting that the regularity assumptions used in the analysis cannot, in general, be dropped without changing the local convergence behavior. p. 1
References
[1] Jacob M. Aguirre et al. cuHALLaR: A GPU accelerated low-rank augmented lagrangian method for large-scale semidefinite programming. p. 3
[2] Farid Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. p. 0
[3] Farid Alizadeh et al. Complementarity and nondegeneracy in semidefinite programming. p. 0
[4] David Applegate et al. Practical large-scale linear programming using primal-dual hybrid gradient. p. 0
[5] David Applegate et al. PDLP: A practical first-order method for large-scale linear programming. p. 3
[6] David Applegate et al. Faster first-order primal-dual methods for linear programming using restarts and sharpness. p. 0
[7] Sebastian Banert et al. The Chambolle–Pock method converges weakly with θ > 1/2 and τσ∥L∥2 < 4/(1 + 2θ). p. 3
[8] Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. p. 0
[9] Stephen P. Boyd et al. Linear Matrix Inequalities in System and Control Theory. p. 1
[10] Stephen P. Boyd et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. p. 1
[11] Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. p. 0
[12] Samuel Burer and Renato D. C. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. p. 0
[13] Samuel Burer and Renato D. C. Monteiro. Local minima and convergence in low-rank semidefinite programming. p. 0
[14] Antonin Chambolle and Thomas Pock. p. 3 A first-order primal-dual algorithm for convex problems with applications to imaging. p. 3
[15] Antonin Chambolle and Thomas Pock. p. 3 On the ergodic convergence rates of a first-order primal–dual algorithm. p. 3
[16] Zi Xian Chan and Defeng Sun. Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming. p. 0
[17] Xiaokai Chang and Junfeng Yang. A golden ratio primal-dual algorithm for structured convex optimization. p. 0
[18] Kaihuang Chen et al. HPR-LP: An implementation of an HPR method for solving linear programming. p. 0
[19] Wei Deng and Wotao Yin. On the global and linear convergence of the generalized alternating direction method of multipliers. p. 1
[20] Lijun Ding et al. New understandings and computation on augmented lagrangian methods for low-rank semidefinite programming. p. 3
[21] Asen L. Dontchev and R. Tyrrell Rockafellar. p. 3 Regularity and conditioning of solution mappings in variational analysis. p. 1
[22] Dmitriy Drusvyatskiy and Adrian S. Lewis. Optimality, identifiability, and sensitivity. p. 7
[23] Jonathan Eckstein and Dimitri P. Bertsekas. On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. p. 3
[24] Ernie Esser et al. A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. p. 0
[25] Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. p. 3
[26] Pontus Giselsson and Stephen P. Boyd. Linear convergence and metric selection for Douglas–Rachford splitting and ADMM. p. 3
[27] Antoine Groudiev et al. cuADMM: GPU-accelerated first-order optimization for large-scale multi-block semidefinite programs. p. 0
[28] Deren Han et al. Linear rate convergence of the alternating direction method of multipliers for convex composite programming. p. 1
[29] Haoyu Han and Heng Yang. Building Rome with convex optimization. p. 0
[30] Qiushi Han et al. A low-rank ADMM splitting approach for semidefinite programming. p. 3
[31] Bingsheng He et al. A generalized primal-dual algorithm with improved convergence condition for saddle point problems. p. 3
[32] Bingsheng He and Xiaoming Yuan. Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective. p. 3
[33] Xin Jiang and Lieven Vandenberghe. p. 0 Bregman primal-dual first-order method and applications to sparse semidefinite programming. p. 0
[34] Xin Jiang and Lieven Vandenberghe. p. 0 Bregman three-operator splitting methods. p. 3
[35] Shucheng Kang et al. Local linear convergence of the alternating direction method of multipliers for semidefinite programming under strict complementarity. p. 1
[36] Shucheng Kang and Heng Yang. Local second-order limit dynamics of ADMM for SDP. p. 3
[37] Guanghui Lan and Tianjiao Li. Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliers. p. 1
[38] Jean B. Lasserre. Moments, Positive Polynomials and Their Applications. p. 0
[39] Adrian S. Lewis et al. Active sets, nonsmoothness, and sensitivity. p. 1
[40] Hongpei Li et al. D-PDLP: Scaling PDLP to distributed multi-GPU systems. p. 3
[41] Jingwei Liang et al. Local convergence properties of Douglas–Rachford and alternating direction method of multipliers. p. 1
[42] Zhenwei Lin et al. PDCS: A primal–dual large-scale conic programming solver with GPU enhancements. p. 0
[43] Haihao Lu and Jinwen Yang. cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. p. 0
[44] Haihao Lu and Jinwen Yang. On the geometry and refined rate of primal-dual hybrid gradient for linear programming. p. 0
[45] Yumin Ma et al. Understanding the convergence of the preconditioned PDHG method: A view of indefinite proximal ADMM. p. 1
[46] Anirudha Majumdar et al. Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. p. 0
[47] Renato D. C. Monteiro et al. A low-rank augmented lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach. p. 3
[48] Daniel O’Connor and Lieven Vandenberghe. On the equivalence of the primal-dual hybrid gradient method and Douglas–Rachford splitting. p. 3
Numerical Evidence
The numerical experiments support the theory on SDP instances from different regularity regimes. The experiments illustrate that PDHG exhibits a clear local linear convergence regime after a transient phase in all tested cases. p. 2 Specifically, the MaxCut SDP instance shows that strict complementarity and primal–dual nondegeneracy appear to hold numerically, leading to R-linear convergence. p. 3 Conversely, synthetic instances where SC fails but primal–dual ND holds also exhibit clear local linear convergence. p. 2 The experiments also document instances where PDHG has difficulty reaching high accuracy within a prescribed computational budget. p. 2
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Adaptive stepsize selection for PDHG can be improved by incorporating knowledge of local geometry to avoid sublinear convergence when strict complementarity fails, as suggested by Example 1 where
the mechanism is the nonlinear behavior of the PSD-cone projection at a singular matrix.
-
Implementation of rank identification should be made more robust by explicitly tracking the dual slack iterates Sk, as they
may not be positive semidefinite
and can fail to stabilize in rank even when strict complementarity holds, as shown in Example 2. -
The theoretical framework can be extended to handle larger stepsize ranges by investigating whether the present proof relies too heavily on the
preconditioned proximal point method interpretation of PDHG,
which is specific to fixed parameter ranges.
Sources
- cuHALLaR: A GPU Accelerated Low-Rank Augmented Lagrangian Method for Large-Scale Semidefinite Programming
- New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming
- Local Linear Convergence of the Alternating Direction Method of Multipliers for Semidefinite Programming under Strict Complementarity
- D-PDLP: Scaling PDLP to Distributed Multi-GPU Systems
- A Practical GPU-Enhanced Matrix-Free Primal-Dual Method for Large-Scale Conic Programs
- A preconditioned augmented Lagrangian method for solving semidefinite programming problems
- A Tuning-Free Primal-Dual Splitting Algorithm for Large-Scale Semidefinite Programming
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise