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

Research output: Contribution to journalArticle

32 Downloads (Pure)

Abstract

The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth non-convex 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 (Formula presented.) function and gradient evaluations, where (Formula presented.) is the user-defined accuracy threshold on the gradient norm.

Original languageEnglish
Pages (from-to)1349-1361
Number of pages13
JournalOptimization
Volume64
Issue number5
DOIs
Publication statusPublished - 4 May 2015

Fingerprint

Unconstrained Optimization
Gradient
Evaluation
Critical point
First-order
Steepest Descent
Line Search
Objective function
Cover
Iteration
Norm
Unknown

Keywords

  • evaluation complexity
  • linesearch algorithms
  • non-linear optimization
  • non-monotone methods
  • worst-case analysis

Cite this

@article{118202766bd64eb68138a70e864855f9,
title = "Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization",
abstract = "The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth non-convex 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 (Formula presented.) function and gradient evaluations, where (Formula presented.) is the user-defined accuracy threshold on the gradient norm.",
keywords = "evaluation complexity, linesearch algorithms, non-linear optimization, non-monotone methods, worst-case analysis",
author = "C. Cartis and {Rodrigues Sampaio}, Phillipe and Toint, {Ph L.}",
year = "2015",
month = "5",
day = "4",
doi = "10.1080/02331934.2013.869809",
language = "English",
volume = "64",
pages = "1349--1361",
journal = "Optimization",
issn = "0233-1934",
publisher = "Taylor & Francis",
number = "5",

}

Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization. / Cartis, C.; Rodrigues Sampaio, Phillipe; Toint, Ph L.

In: Optimization, Vol. 64, No. 5, 04.05.2015, p. 1349-1361.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Cartis, C.

AU - Rodrigues Sampaio, Phillipe

AU - Toint, Ph L.

PY - 2015/5/4

Y1 - 2015/5/4

N2 - The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth non-convex 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 (Formula presented.) function and gradient evaluations, where (Formula presented.) is the user-defined accuracy threshold on the gradient norm.

AB - The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth non-convex 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 (Formula presented.) function and gradient evaluations, where (Formula presented.) is the user-defined accuracy threshold on the gradient norm.

KW - evaluation complexity

KW - linesearch algorithms

KW - non-linear optimization

KW - non-monotone methods

KW - worst-case analysis

UR - http://www.scopus.com/inward/record.url?scp=84924237792&partnerID=8YFLogxK

U2 - 10.1080/02331934.2013.869809

DO - 10.1080/02331934.2013.869809

M3 - Article

VL - 64

SP - 1349

EP - 1361

JO - Optimization

JF - Optimization

SN - 0233-1934

IS - 5

ER -