A robust control approach to asymptotic optimality of the heavy ball method for optimization of quadratic functions

DOI10.1016/J.AUTOMATICA.2023.111129MaRDI QIDQ6110012zbMATH OpenOpenAlexFDO

Authors Valery Ugrinovskii, Ian R. Petersen, Iman Shames

Publication date 31 July 2023

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.06593

zbMATH Keywords

optimization methodsanalysis of systems with uncertaintiesheavy ball method

Mathematics Subject Classification ID

Quadratic programming (90C20) Sensitivity (robustness) (93B35) Feedback control (93B52) Linear systems in control theory (93C05)

Abstract: Among first order optimization methods, Polyak's heavy ball method has long been known to guarantee the asymptotic rate of convergence matching Nesterov's lower bound for functions defined in an infinite-dimensional space. In this paper, we use results on the robust gain margin of linear uncertain feedback control systems to show that the heavy ball method is provably worst-case asymptotically optimal when applied to quadratic functions in a finite dimensional space.

Recommendations

• Convergence rates of the heavy ball method for quasi-strongly convex optimization
• Stochastic heavy ball
• Optimisation and asymptotic stability
• scientific article; zbMATH DE number 165426
• Non-monotone Behavior of the Heavy Ball Method

Cites work

• scientific article; zbMATH DE number 53439 (Why is no real title available?)
• Interpolation of rational matrix functions
• Iterative Solution of Nonlinear Equations in Several Variables
• Lectures on convex optimization
• Non-Euclidian metrics and the robust stabilization of systems with parameter uncertainty
• Nonlinear dynamical systems and control. A Lyapunov-based approach
• Nonlinear systems.
• On the oracle complexity of smooth strongly convex minimization
• Some methods of speeding up the convergence of iteration methods

Cited in

(3)

• Uniting Nesterov and heavy ball methods for uniform global asymptotic stability of the set of minimizers
• Optimisation and asymptotic stability
• Convergence rates of the heavy ball method for quasi-strongly convex optimization

This page was built for publication: A robust control approach to asymptotic optimality of the heavy ball method for optimization of quadratic functions

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