  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 $\mathcal{O}(1/k^2)$
and $\mathcal{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 $\mathcal{O}(1/k^2)$ and
$\tilde{\mathcal{O}}(1/k^2)$ rates. We then provide a matching complexity lower
bound to establish that $\Theta(1/k^2)$ is indeed the optimal accelerated rate.
