Local Linear Convergence of the Primal-Dual Hybrid Gradient Method for Semidefinite Programming
TL;DR
It is shown that PDHG converges eventually (R-)linearly whenever the limiting KKT point satisfies either strict complementarity or primal--dual nondegeneracy, and numerical experiments support the theory and identify difficult SDP instances where PDHG struggles to reach high accuracy.
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.