Local linear convergence of the primal-dual hybrid gradient algorithm for semidefinite programming

summary

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…

In short

This study investigates when the primal-dual hybrid gradient (PDHG) method converges locally at a linear rate for large-scale semidefinite programming (SDP). The authors prove that PDHG achieves eventual R-linear convergence if the solution satisfies either strict complementarity or primal-dual nondegeneracy. This provides a theoretical guarantee for the algorithm's performance under specific regularity conditions.

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 used across episodes

This episode discusses

The paper

Local linear convergence of the primal-dual hybrid gradient algorithm for semidefinite programming · Read on arXiv

Xin Jiang

University of Houston

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.

More episodes

← Home