Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Explicit stabilised gradient descent for faster strongly convex optimisation
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2021 (English)In: BIT Numerical Mathematics, ISSN 0006-3835, E-ISSN 1572-9125, Vol. 61, p. 119-139Article in journal (Refereed) Published
Abstract [en]

This paper introduces the Runge-Kutta Chebyshev descent method (RKCD) for strongly convex optimisation problems. This new algorithm is based on explicit stabilised integrators for stiff differential equations, a powerful class of numerical schemes that avoid the severe step size restriction faced by standard explicit integrators. For optimising quadratic and strongly convex functions, this paper proves that RKCD nearly achieves the optimal convergence rate of the conjugate gradient algorithm, and the suboptimality of RKCD diminishes as the condition number of the quadratic function worsens. It is established that this optimal rate is obtained also for a partitioned variant of RKCD applied to perturbations of quadratic functions. In addition, numerical experiments on general strongly convex problems show that RKCD outperforms Nesterov's accelerated gradient descent.

Place, publisher, year, edition, pages
Springer, 2021. Vol. 61, p. 119-139
Keywords [en]
Runge-Kutta methods, Strongly convex optimization, Accelerated gradient descent
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-173636DOI: 10.1007/s10543-020-00819-yISI: 000545282100001Scopus ID: 2-s2.0-85087566688OAI: oai:DiVA.org:umu-173636DiVA, id: diva2:1455036
Available from: 2020-07-21 Created: 2020-07-21 Last updated: 2021-07-02Bibliographically approved

Open Access in DiVA

fulltext(4918 kB)393 downloads
File information
File name FULLTEXT02.pdfFile size 4918 kBChecksum SHA-512
39ef104fb87da4d2a8d52fade3e7035c249615af61f5c02cdab3e6595eefbfc2499ee83cc3a19ee486c5882686dc5bd272a8e00d69b67dc147b33b2474cf1004
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Eftekhari, Armin

Search in DiVA

By author/editor
Eftekhari, Armin
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
BIT Numerical Mathematics
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 504 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 543 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf