The speed of Shor's R-algorithm

J. V. Burke, A. S. Lewis, M. L. Overton

Research output: Contribution to journalArticle

Abstract

Shor's r-algorithm is an iterative method for unconstrained optimization, designed for minimizing nonsmooth functions, for which its reported success has been considerable. Although some limited convergence results are known, nothing seems to be known about the algorithm's rate of convergence, even in the smooth case. We study how the method behaves on convex quadratics, proving linear convergence in the two-dimensional case and conjecturing that the algorithm is always linearly convergent, with an asymptotic convergence rate that is independent of the conditioning of the quadratic being minimized.

Original languageEnglish (US)
Pages (from-to)711-720
Number of pages10
JournalIMA Journal of Numerical Analysis
Volume28
Issue number4
DOIs
StatePublished - Oct 2008

Keywords

  • Linear convergence
  • Nonsmooth optimization
  • Shor's r-algorithm
  • Space dilation
  • Unconstrained optimization

ASJC Scopus subject areas

  • Mathematics(all)
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The speed of Shor's R-algorithm'. Together they form a unique fingerprint.

  • Cite this