Afterimage Slow Regions in First-Order Methods for Linear Conic Programming
Abstract
First-order methods for linear conic programming often stall on long plateaus. Existing analyses characterize when during a run or on which problem instances slow convergence occurs; we instead ask where in the state space slow convergence is present. We introduce the slow region family for parameterized averaged fixed-point iterations. On a slow region, one step moves the state by only a small fraction of its distance to the fixed-point set, so an orbit starting there keeps almost its initial distance for arbitrarily many iterations. We then develop the afterimage principle to construct them. A center family and a nearby petal family share the same limit parameter, so their residual fields become close, while their fixed-point sets or forward drifts stay far apart. The petal geometry then certifies a slow region for the center. We verify the standing assumptions for ADMM, sGS-ADMM, and PDHG, and give an LP, SOCP, and SDP gallery showing how varied slow regions can be.
Related
- PDLP: a practical first-order method for large-scale linear programming
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Recent Developments in HPR Methods for Large-Scale Linear Programming
- Dataset Pruning from First Principles: A Label-Free Linear Programming Approach
- On the Local Linear Convergence of Operator Splitting Methods for Conic Programming
BibTeX
@misc{kang2026afterimage,
title = {{Afterimage Slow Regions in First-Order Methods for Linear Conic Programming}},
author = {Shucheng Kang and Heng Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09449},
eprint = {2609.09449},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09449},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Afterimage Slow Regions in First-Order Methods for Linear Conic Programming
AU - Shucheng Kang
AU - Heng Yang
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09449
UR - https://arxiv.org/abs/2609.09449
AB - First-order methods for linear conic programming often stall on long plateaus. Existing analyses characterize when during a run or on which problem instances slow convergence occurs; we instead ask where in the state space slow convergence is present. We introduce the slow region family for parameterized averaged fixed-point iterations. On a slow region, one step moves the state by only a small fraction of its distance to the fixed-point set, so an orbit starting there keeps almost its initial distance for arbitrarily many iterations. We then develop the afterimage principle to construct them. A center family and a nearby petal family share the same limit parameter, so their residual fields become close, while their fixed-point sets or forward drifts stay far apart. The petal geometry then certifies a slow region for the center. We verify the standing assumptions for ADMM, sGS-ADMM, and PDHG, and give an LP, SOCP, and SDP gallery showing how varied slow regions can be.
ER -