Skip Navigation


IMA Journal of Numerical Analysis Advance Access originally published online on September 12, 2008
IMA Journal of Numerical Analysis 2008 28(4):711-720; doi:10.1093/imanum/drn008
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
28/4/711    most recent
drn008v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Burke, J. V.
Right arrow Articles by Overton, M. L.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The author 2008. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved.

The Speed of Shor's R-algorithm

J. V. Burke{dagger}

Department of Mathematics, University of Washington, Seattle, WA 98195, USA

A. S. Lewis{ddagger}

School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853, USA

M. L. Overton§

Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA

{dagger} Email: burke{at}math.washington.edu

{ddagger} Email: aslewis{at}orie.cornell.edu

§ Corresponding author. Email: overton{at}cs.nyu.edu

Received on 8 May 2007. Accepted for publication 4 December 2007.


  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.

Key Words: Shor's r-algorithm; space dilation; linear convergence; unconstrained optimization; nonsmooth optimization

Dedicated to M. J. D. Powell, master of convergence analysis for nonlinear optimization, on the occasion of his 70th birthday.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.