### 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 |

State | Published - Jul 1 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 | United States |

City | Philadelphia |

Period | 7/10/19 → 7/12/19 |

### Fingerprint

### Cite this

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

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

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

}

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 -