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 δ-(sub-)level sets Wδ 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δ for which (i) Wδ is close to the optimal solution set in Hausdorff distance, and (ii) the ratio of the diameter to the ``conic radius'' of Wδ 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.
Related
- Comparative Performance Analysis of Optimization Solvers for Linear Support Vector Machines: Impact of Preconditioning and Dimensionality An Empirical Study Using the Benchopt Framework
- Experimental and theoretical investigation of parameter-driven stability and chaos in a non-linear neuron circuit model
- A Theoretical Analysis of a Bilevel Optimization Formulation for Combined Local-Global Optical Flow Models
- Pfaffian Geometry and Indicial Singularities of Third-Order Linear ODEs
- Boundary geometry and linear accessibility of functions with positive real derivative
BibTeX
@misc{xiong2026levelset,
title = {{Level-Set Geometry and the Theoretical Performance of PDHG for Conic Linear Optimization}},
author = {Zikai Xiong and Robert M. Freund},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19097},
eprint = {2609.19097},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19097},
}
RIS
TY - UNPB
TI - Level-Set Geometry and the Theoretical Performance of PDHG for Conic Linear Optimization
AU - Zikai Xiong
AU - Robert M. Freund
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.19097
UR - https://arxiv.org/abs/2609.19097
AB - 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 δ-(sub-)level sets W_δ 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_δ for which (i) W_δ is close to the optimal solution set in Hausdorff distance, and (ii) the ratio of the diameter to the ``conic radius'' of W_δ 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.
ER -