Analysis of the heavy-ball algorithm using integral quadratic constraints

Apurva Badithela, Peter Seiler

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

1 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 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
DOIs
StatePublished - Jul 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

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 apurva@caltech.edu 2P. Seiler is with Faculty of Aerospace Engineering and Mechanics, University of Minnesota, Twin-Cities, USA seile017@umn.edu

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

Fingerprint Dive into the research topics of 'Analysis of the heavy-ball algorithm using integral quadratic constraints'. Together they form a unique fingerprint.

Cite this