Restart of Accelerated First-Order Methods With Linear Convergence Under a Quadratic Functional Growth Condition

• 成果类型: Article
• 署名作者: Alamo, Teodoro; Krupa, Pablo; Limon, Daniel
• 署名单位: University of Sevilla
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3146054
• 发表日期: 2023
• 页码: 612-619
• 关键词: Accelerated first-order methods (AFOMs); Convex Optimization; linear convergence; restart schemes

摘要

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.