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

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.