Analysis of the heavy-ball algorithm using integral quadratic constraints

Apurva Badithela; Peter Seiler

doi:10.23919/acc.2019.8814459

Analysis of the heavy-ball algorithm using integral quadratic constraints

Apurva Badithela
, Peter Seiler

Aerospace Engineering and Mechanics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

12 Scopus citations

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 language	English (US)
Title of host publication	2019 American Control Conference, ACC 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4081-4085
Number of pages	5
ISBN (Electronic)	9781538679265
DOIs	https://doi.org/10.23919/acc.2019.8814459
State	Published - Jul 2019
Event	2019 American Control Conference, ACC 2019 - Philadelphia, United States Duration: Jul 10 2019 → Jul 12 2019

Publication series

Name	Proceedings of the American Control Conference
Volume	2019-July
ISSN (Print)	0743-1619

Conference

Conference	2019 American Control Conference, ACC 2019
Country/Territory	United States
City	Philadelphia
Period	7/10/19 → 7/12/19

Bibliographical note

Funding Information:
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 1A. Badithela is a graduate student at California Institute of Technology, Pasadena, USA [email protected] 2P. Seiler is with Faculty of Aerospace Engineering and Mechanics, University of Minnesota, Twin-Cities, USA [email protected]

Funding Information:
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

Publisher Copyright:
© 2019 American Automatic Control Council.

Publisher link

10.23919/acc.2019.8814459

Find It

Find It at U of M Libraries

Cite this

Analysis of the heavy-ball algorithm using integral quadratic constraints. / Badithela, Apurva; Seiler, Peter.
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 proceeding › Conference contribution

Badithela, A & Seiler, P 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. https://doi.org/10.23919/acc.2019.8814459

@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 Peter Seiler",

note = "Funding Information: 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 1A. Badithela is a graduate student at California Institute of Technology, Pasadena, USA [email protected] 2P. Seiler is with Faculty of Aerospace Engineering and Mechanics, University of Minnesota, Twin-Cities, USA [email protected] Funding Information: 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 Publisher Copyright: {\textcopyright} 2019 American Automatic Control Council.; 2019 American Control Conference, ACC 2019 ; Conference date: 10-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

doi = "10.23919/acc.2019.8814459",

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, Peter

N1 - Funding Information: 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 1A. Badithela is a graduate student at California Institute of Technology, Pasadena, USA [email protected] 2P. Seiler is with Faculty of Aerospace Engineering and Mechanics, University of Minnesota, Twin-Cities, USA [email protected] Funding Information: 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 Publisher Copyright: © 2019 American Automatic Control Council.

PY - 2019/7

Y1 - 2019/7

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 - https://www.scopus.com/pages/publications/85072288125

UR - https://www.scopus.com/pages/publications/85072288125#tab=citedBy

U2 - 10.23919/acc.2019.8814459

DO - 10.23919/acc.2019.8814459

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.

T2 - 2019 American Control Conference, ACC 2019

Y2 - 10 July 2019 through 12 July 2019

ER -

Analysis of the heavy-ball algorithm using integral quadratic constraints

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this