-

 

 

 




Optimization Online





 

On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization

Coralia Cartis(coralia.cartis***at***ed.ac.uk)
Nick Gould(nick.gould***at***sftc.ac.uk)
Philippe Toint(philippe.toint***at***fundp.ac.be)

Abstract: The (optimal) function/gradient evaluations worst-case complexity analysis available for the Adaptive Regularizations algorithms with Cubics (ARC) for nonconvex smooth unconstrained optimization is extended to finite-difference versions of this algorithm, yielding complexity bounds for first-order and derivative free methods applied on the same problem class. A comparison with the results obtained for derivative-free methods by Vicente (2010) is also discussed, giving some theoretical insight on the relative merits of various methods in this popular class of algorithms.

Keywords: oracle complexity, worst-case analysis, finite-differences, first-order methods, derivative free optimization, nonconvex optimization.

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation: @techreport{CartGoulToin10d, author= {C. Cartis and N. I. M. Gould and Ph. L. Toint}, title = {On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization}, institution = {University of Namur}, address = {61, rue de Bruxelles, 5000 Namur, Belgium}, number = {NAXYS-02-2010}, year = 2010}

Download: [PDF]

Entry Submitted: 10/19/2010
Entry Accepted: 10/19/2010
Entry Last Modified: 10/19/2010

Modify/Update this entry


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

 

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