Optimization Online


The Speed of Shor's R-Algorithm

James V. Burke(burke***at***math.washington.edu)
Adrian S. Lewis(aslewis***at***orie.cornell.edu)
Michael L. Overton(overton***at***cs.nyu.edu)

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.

Keywords: Shor's r-algorithm, space dilation, linear convergence, unconstrained optimization, nonsmooth optimization

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Submitted to IMA J. Numer. Anal.

Download: [PDF]

Entry Submitted: 05/08/2007
Entry Accepted: 05/08/2007
Entry Last Modified: 05/08/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society