Level-Set Geometry and the Theoretical Performance of PDHG for Conic Linear Optimization

Abstract

We consider solving (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG) -- with heuristic enhancements and GPU implementation -- has been very successful in solving huge-scale linear optimization problems (LPs). However, its application to more general conic convex optimization problems is not so well-studied. We analyze the theoretical performance of rPDHG for general (convex) conic linear optimization, and LP as a special case thereof. We show a relationship between the geometry of the primal-dual $\delta$-(sub-)level sets ${W}_\delta$ and the convergence rate of rPDHG. Specifically, we prove a bound on the convergence rate of rPDHG that improves when there is a primal-dual (sub-)level set ${W}_\delta$ for which (i) ${W}_\delta$ is close to the optimal solution set in Hausdorff distance, and (ii) the ratio of the diameter to the ``conic radius''of ${W}_\delta$ is small. And in the special case of LP, the performance of rPDHG is bounded only by this ratio applied to the (sub-)level set corresponding to the best non-optimal extreme point. Depending on the problem instance, this ratio can take on extreme values and can result in excellent or poor performance of rPDHG both in theory and in practice.