On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions

Etienne De Klerk, François Glineur, Adrien B. Taylor

Research output: Contribution to journalArticleScientificpeer-review

31 Citations (Scopus)
37 Downloads (Pure)

Abstract

We consider the gradient (or steepest) descent method with exact line search applied to a strongly convex function with Lipschitz continuous gradient. We establish the exact worst-case rate of convergence of this scheme, and show that this worst-case behavior is exhibited by a certain convex quadratic function. We also give the tight worst-case complexity bound for a noisy variant of gradient descent method, where exact line-search is performed in a search direction that differs from negative gradient by at most a prescribed relative tolerance. The proofs are computer-assisted, and rely on the resolutions of semidefinite programming performance estimation problems as introduced in the paper (Drori and Teboulle, Math Progr 145(1–2):451–482, 2014).
Original languageEnglish
Pages (from-to)1185–1199
Number of pages15
JournalOptimization Letters
Volume11
Issue number7
DOIs
Publication statusPublished - 2016

Keywords

  • Gradient method
  • Steepest descent
  • Semidefinite programming
  • Performance estimation problem

Fingerprint

Dive into the research topics of 'On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions'. Together they form a unique fingerprint.

Cite this