# Accelerated Infeasibility Detection of Constrained Optimization and Fixed-Point Iterations

arXiv: https://arxiv.org/abs/2303.15876 · HTML: https://mlsanity.com/paper/2303.15876/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2023.

## Built on by (most cited first, 2 of 2)

- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [Batched First-Order Methods for Parallel LP Solving in MIP](https://mlsanity.com/paper/2601.21990/) (2026)

## Abstract (arXiv)

As first-order optimization methods become the method of choice for solving large-scale optimization problems, optimization solvers based on first-order algorithms are being built. Such general-purpose solvers must robustly detect infeasible or misspecified problem instances, but the computational complexity of first-order methods for doing so has yet to be formally studied. In this work, we characterize the optimal accelerated rate of infeasibility detection. We show that the standard fixed-point iteration achieves a O(1/k2) and O(1/k) rates, respectively, on the normalized iterates and the fixed-point residual converging to the infimal displacement vector, while the accelerated fixed-point iteration achieves O(1/k2) and tildeO(1/k2) rates. We then provide a matching complexity lower bound to establish that Theta(1/k2) is indeed the optimal accelerated rate.