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

C. Cartis; Phillipe Rodrigues Sampaio; Ph L. Toint

doi:10.1080/02331934.2013.869809

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

C. Cartis, Phillipe Rodrigues Sampaio, Ph L. Toint

Namur Institute for Complex Systems

Research output: Contribution to journal › Article

85 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 language	English
Pages (from-to)	1349-1361
Number of pages	13
Journal	Optimization
Volume	64
Issue number	5
DOIs	https://doi.org/10.1080/02331934.2013.869809
Publication status	Published - 4 May 2015

Keywords

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

Access to Document

10.1080/02331934.2013.869809

Technical ReportSubmitted manuscript, 208 KB

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization'. Together they form a unique fingerprint.

Projects

2 Active

Complexity in nonlinear optimization

TOINT, P., Gould, N. I. M. & Cartis, C.

1/11/08 → …

Project: Research

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

SARTENAER, A. & TOINT, P.

1/01/87 → …

Project: Research Axis

Activities

4 Oral presentation
2 Research/Teaching in a external institution
1 Invited talk
1 Visiting an external academic institution

A path and some adventures in the jungle of high-order nonlinear optimization

Philippe Toint (Speaker)

24 Oct 2017

Activity: Talk or presentation types › Invited talk

How much patience do you have? Issues in complexity for nonlinear optimization

Philippe Toint (Invited speaker)

5 Feb 2016

Activity: Talk or presentation types › Oral presentation

How much patience do you have? Issues in complexity for nonlinear optimization

Philippe Toint (Speaker)

31 Jan 2016

Activity: Talk or presentation types › Oral presentation

Prizes

Leverhulme Fellow

TOINT, Philippe (Recipient), Sep 2015

Prize: Fellowship awarded competitively

Cite this

Cartis, C., Rodrigues Sampaio, P., & Toint, P. L. (2015). Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization. Optimization, 64(5), 1349-1361. https://doi.org/10.1080/02331934.2013.869809

@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 = may,

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",

}

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

AN - SCOPUS:84924237792

VL - 64

SP - 1349

EP - 1361

JO - Optimization

JF - Optimization

SN - 0233-1934

IS - 5

ER -