A Caltech Library Service

Analysis of the Heavy-ball Algorithm using Integral Quadratic Constraints

Badithela, Apurva and Seiler, Peter (2019) Analysis of the Heavy-ball Algorithm using Integral Quadratic Constraints. In: 2019 American Control Conference (ACC). IEEE , Piscataway, NJ, pp. 4081-4085. ISBN 978-1-5386-7926-5.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


In this paper, we analyze the convergence rate of the Heavy-ball algorithm applied to optimize a class of continuously differentiable functions. The analysis is performed with the Heavy-ball tuned to achieve the best convergence rate on the sub-class of quadratic functions. We review recent work to characterize convergence rate upper bounds for optimization algorithms using integral quadratic constraints (IQC). This yields a linear matrix inequality (LMI) condition which is typically solved numerically to obtain convergence rate bounds. We construct an analytical solution for this LMI condition using a specific “weighted off-by-one” IQC. We also construct a specific objective function such that the Heavy-ball algorithm enters a limit cycle. These results demonstrate that IQC condition is tight for the analysis of the tuned Heavy-ball, i.e. it yields the exact condition ratio that separates global convergence from non-global convergence for the algorithm.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2019 AACC. This work was supported by the National Science Foundation under Grant No. NSF-CMMI-1254129 entitled CAREER: Probabilistic Tools for High Reliability and Monitoring and Control of Wind Farms.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20190905-155006075
Persistent URL:
Official Citation:A. Badithela and P. Seiler, "Analysis of the Heavy-ball Algorithm using Integral Quadratic Constraints," 2019 American Control Conference (ACC), Philadelphia, PA, USA, 2019, pp. 4081-4085. URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98464
Deposited By: Tony Diaz
Deposited On:05 Sep 2019 23:03
Last Modified:03 Oct 2019 21:41

Repository Staff Only: item control page