The Speed of Shor's R-Algorithm

James V. Burke(burkemath.washington.edu)
Adrian S. Lewis(aslewisorie.cornell.edu)
Michael L. Overton(overtoncs.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