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

Valery Ugrinovskii, Iman Shames, Ian R. Petersen

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

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?)
• Title not available (Why is that?)
• Nonlinear systems.
• 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

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)