Analysis of the heavy-ball algorithm using integral quadratic constraints

Apurva Badithela, Peter J Seiler Jr

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2019 American Control Conference, ACC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4081-4085
Number of pages5
ISBN (Electronic)9781538679265
StatePublished - Jul 1 2019
Event2019 American Control Conference, ACC 2019 - Philadelphia, United States
Duration: Jul 10 2019Jul 12 2019

Publication series

NameProceedings of the American Control Conference
Volume2019-July
ISSN (Print)0743-1619

Conference

Conference2019 American Control Conference, ACC 2019
CountryUnited States
CityPhiladelphia
Period7/10/197/12/19

Fingerprint

Linear matrix inequalities

Cite this

Badithela, A., & Seiler Jr, P. J. (2019). Analysis of the heavy-ball algorithm using integral quadratic constraints. In 2019 American Control Conference, ACC 2019 (pp. 4081-4085). [8814459] (Proceedings of the American Control Conference; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc..

Analysis of the heavy-ball algorithm using integral quadratic constraints. / Badithela, Apurva; Seiler Jr, Peter J.

2019 American Control Conference, ACC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 4081-4085 8814459 (Proceedings of the American Control Conference; Vol. 2019-July).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Badithela, A & Seiler Jr, PJ 2019, Analysis of the heavy-ball algorithm using integral quadratic constraints. in 2019 American Control Conference, ACC 2019., 8814459, Proceedings of the American Control Conference, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., pp. 4081-4085, 2019 American Control Conference, ACC 2019, Philadelphia, United States, 7/10/19.
Badithela A, Seiler Jr PJ. Analysis of the heavy-ball algorithm using integral quadratic constraints. In 2019 American Control Conference, ACC 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 4081-4085. 8814459. (Proceedings of the American Control Conference).
Badithela, Apurva ; Seiler Jr, Peter J. / Analysis of the heavy-ball algorithm using integral quadratic constraints. 2019 American Control Conference, ACC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 4081-4085 (Proceedings of the American Control Conference).
@inproceedings{0192e71e61084966a1ca9dc49df99070,
title = "Analysis of the heavy-ball algorithm using integral quadratic constraints",
abstract = "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.",
author = "Apurva Badithela and {Seiler Jr}, {Peter J}",
year = "2019",
month = "7",
day = "1",
language = "English (US)",
series = "Proceedings of the American Control Conference",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "4081--4085",
booktitle = "2019 American Control Conference, ACC 2019",

}

TY - GEN

T1 - Analysis of the heavy-ball algorithm using integral quadratic constraints

AU - Badithela, Apurva

AU - Seiler Jr, Peter J

PY - 2019/7/1

Y1 - 2019/7/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85072288125&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85072288125&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85072288125

T3 - Proceedings of the American Control Conference

SP - 4081

EP - 4085

BT - 2019 American Control Conference, ACC 2019

PB - Institute of Electrical and Electronics Engineers Inc.

ER -