Restart of Accelerated First-Order Methods With Linear Convergence Under a Quadratic Functional Growth Condition
From MaRDI portal
Publication:6137550
DOI10.1109/TAC.2022.3146054arXiv2102.12387OpenAlexW4210785829MaRDI QIDQ6137550FDOQ6137550
T. Alamo, Pablo Krupa, Daniel Limon
Publication date: 4 September 2023
Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)
Abstract: Accelerated first order methods, also called fast gradient methods, are popular optimization methods in the field of convex optimization. However, they are prone to suffer from oscillatory behaviour that slows their convergence when medium to high accuracy is desired. In order to address this, restart schemes have been proposed in the literature, which seek to improve the practical convergence by suppressing the oscillatory behaviour. This paper presents a restart scheme for accelerated first order methods for which we show linear convergence under the satisfaction of a quadratic functional growth condition, thus encompassing a broad class of non-necessarily strongly convex optimization problems. Moreover, the worst-case convergence rate is comparable to the one obtained using a (generally non-implementable) optimal fixed-rate restart strategy. We compare the proposed algorithm with other restart schemes by applying them to a model predictive control case study.
Full work available at URL: https://arxiv.org/abs/2102.12387
Cited In (2)
This page was built for publication: Restart of Accelerated First-Order Methods With Linear Convergence Under a Quadratic Functional Growth Condition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6137550)
