On the Local Linear Convergence of Operator Splitting Methods for Conic Programming
Abstract
Operator-splitting methods such as the primal-dual hybrid gradient method (PDHG) and the alternating direction method of multipliers (ADMM) often exhibit linear convergence on conic programs, although general theory guarantees only sublinear rates. We identify two geometric conditions -- strict complementarity and quadratic facial violation -- that explain this local behavior: under these conditions, PDHG and ADMM converge linearly to an optimal solution when initialized sufficiently close to the converging strictly complementary solution. We establish this result through a unified and verifiable primal-dual error-bound framework. First, we show that strict complementarity, together with a quadratic facial-violation property of the associated complementary faces, implies uniform quadratic growth of both the primal and dual augmented Lagrangians near a strictly complementary solution. Second, we prove the local equivalence of three regularity conditions: uniform quadratic growth of the augmented Lagrangians, quadratic growth of a localized smoothed primal-dual gap, and metric subregularity of the saddle-point mapping. This equivalence clarifies the relationship among previously proposed conditions for local linear convergence. Third, using a unified formulation, we give a concise analysis showing that these equivalent conditions yield local linear convergence of PDHG and ADMM. We verify the quadratic facial-violation property for standard polyhedral and symmetric cones, as well as relevant faces of exponential and power cones, and show that it is preserved under Cartesian products. We also obtain an improved local rate using a restarted Halpern scheme. Finally, we extend the framework to convex composite optimization through a quadratic subdifferential-violation condition, which generalizes the quadratic facial-violation.
Related
- Operator Splitting Methods with Online Scaling
- Hopf Algebra of Graphs for Operator Splitting Methods
- A Triangular Log-Det PDHG for Semidefinite Programming: Complementarity Selection and Global Linear Convergence
- Operator splitting methods for non-autonomous evolution equations comprising three parts, with application to the Bloch-Torrey equation of MRI
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
BibTeX
@misc{ding2026local,
title = {{On the Local Linear Convergence of Operator Splitting Methods for Conic Programming}},
author = {Lijun Ding and Haihao Lu and Jinwen Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.16054},
eprint = {2608.16054},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.16054},
}
RIS
TY - UNPB
TI - On the Local Linear Convergence of Operator Splitting Methods for Conic Programming
AU - Lijun Ding
AU - Haihao Lu
AU - Jinwen Yang
PY - 2026
DA - 2026/10/31
PB - arXiv
DO - 10.48550/arxiv.2608.16054
UR - https://arxiv.org/abs/2608.16054
AB - Operator-splitting methods such as the primal-dual hybrid gradient method (PDHG) and the alternating direction method of multipliers (ADMM) often exhibit linear convergence on conic programs, although general theory guarantees only sublinear rates. We identify two geometric conditions -- strict complementarity and quadratic facial violation -- that explain this local behavior: under these conditions, PDHG and ADMM converge linearly to an optimal solution when initialized sufficiently close to the converging strictly complementary solution. We establish this result through a unified and verifiable primal-dual error-bound framework. First, we show that strict complementarity, together with a quadratic facial-violation property of the associated complementary faces, implies uniform quadratic growth of both the primal and dual augmented Lagrangians near a strictly complementary solution. Second, we prove the local equivalence of three regularity conditions: uniform quadratic growth of the augmented Lagrangians, quadratic growth of a localized smoothed primal-dual gap, and metric subregularity of the saddle-point mapping. This equivalence clarifies the relationship among previously proposed conditions for local linear convergence. Third, using a unified formulation, we give a concise analysis showing that these equivalent conditions yield local linear convergence of PDHG and ADMM. We verify the quadratic facial-violation property for standard polyhedral and symmetric cones, as well as relevant faces of exponential and power cones, and show that it is preserved under Cartesian products. We also obtain an improved local rate using a restarted Halpern scheme. Finally, we extend the framework to convex composite optimization through a quadratic subdifferential-violation condition, which generalizes the quadratic facial-violation.
ER -