Accelerated Infeasibility Detection of Constrained Optimization and Fixed-Point Iterations

arXiv2303.15876MaRDI QIDQ6431107FDOQ6431107

Authors: Jisun Park, Ernest K. Ryu 

Publication date: 28 March 2023

Abstract: 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 $mathcalO(1/k^2)$ and $mathcalO(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 $mathcalO(1/k^2)$ and $ildemathcalO(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.

This page was built for publication: Accelerated Infeasibility Detection of Constrained Optimization and Fixed-Point Iterations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6431107)