Optimization Online


Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization

Coralia Cartis(coralia.cartis***at***ed.ac.uk)
Phillipe Sampaio(phillipe.sampaio***at***fundp.ac.be)
Philippe L. Toint(philippe.toint***at***fundp.ac.be)

Abstract: The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth nonconvex and unconstrained problems is investigated. The analysis covers a practical linesearch implementation of these popular methods, allowing for an unknown number of evaluations of the objective function (and its gradient) per iteration. It is shown that this class of methods shares the known complexity properties of a simple steepest-descent scheme and that an approximate first-order critical point can be computed in at most $O(\epsilon^{-2}$) function and gradient evaluations, where $\epsilon > 0$ is the user-defined accuracy threshold on the gradient norm.

Keywords: Nonlinear optimization, evaluation complexity, linesearch algorithms

Category 1: Nonlinear Optimization (Unconstrained Optimization )

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

Citation: Report NAXYS-02-2013, Namur Center for Complex Systems University of Namur, Namur, Belgium

Download: [PDF]

Entry Submitted: 03/12/2013
Entry Accepted: 03/12/2013
Entry Last Modified: 03/12/2013

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 Optimization Society