Details

Autor(en) / Beteiligte

• Alamo, Teodoro
• Krupa, Pablo
• Limon, Daniel

Titel

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.