no. 16 · Tuesday 17 November 2026
Local linear convergence of the primal-dual hybrid gradient algorithm for semidefinite programming
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 explained by global convergence theory alone. We study the local convergence of the primal–dual hybrid gradient (PDHG) method for SDP. We first show that PDHG converges linearly, uniformly for all starting points near a KKT point, if and only if the KKT mapping is metrically subregular at that point. We then show that PDHG eventually converges linearly whenever the limit KKT point is strictly complementary, even with multiple solutions. The asymptotic rate admits a bound computable from the eigenvalues of the linearized PDHG map and matching the observed rates in our experiments. As a byproduct of the analysis, strict complementarity implies metric subregularity. Finally, we prove that PDHG can converge sublinearly even when started arbitrarily close to a solution, which cannot happen for linear programming. Numerical experiments support the theory and exhibit SDP instances on which PDHG struggles to reach high accuracy.
- fields
- Optimization and Control