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

DOI10.1016/J.AUTOMATICA.2023.111129zbMATH Open1520.93117arXiv2305.06593OpenAlexW4380201355MaRDI QIDQ6110012FDOQ6110012

Authors: Valery Ugrinovskii, Ian R. Petersen, Iman Shames 

Publication date: 31 July 2023

Published in: Automatica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (3)

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

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)