Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Restart of Accelerated First-Order Methods With Linear Convergence Under a Quadratic Functional Growth Condition
Ist Teil von
IEEE transactions on automatic control, 2023-01, Vol.68 (1), p.612-619
Ort / Verlag
New York: IEEE
Erscheinungsjahr
2023
Quelle
IEEE Electronic Library (IEL)
Beschreibungen/Notizen
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 behavior 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 behavior. This article 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 an (generally nonimplementable) optimal fixed-rate restart strategy. We compare the proposed algorithm with other restart schemes by applying them to a model predictive control case study.