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

Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

124 Téléchargements (Pure)

Résumé

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.

langue originale	Anglais
Pages (de - à)	1349-1361
Nombre de pages	13
journal	Optimization
Volume	64
Numéro de publication	5
Les DOIs	https://doi.org/10.1080/02331934.2013.869809
Etat de la publication	Publié - 4 mai 2015

Accès au document

10.1080/02331934.2013.869809

Technical Reportmanuscrit soumis, 208 KB

Autres fichiers et liens

Link to publication in Scopus

19 Citations
11 Article
3 Papier de travail
1 Livre
1 Chapitre

Evaluation complexity of algorithms for nonconvex optimization
Cartis, C., Gould, N. I. M. & TOINT, P., juil. 2022, SIAM. 600 p. (SIAM-MOS Series on Optimization)
Résultats de recherche: Livre/Rapport/Revue › Livre
Adaptive regularization algorithms with inexact evaluations for nonconvex optimization
Bellavia, S., Gurioli, G., Morini, B. & Toint, P., 2 janv. 2020, Dans: SIAM Journal on Optimization. 29, 4, p. 2881-2915 35 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
42 Téléchargements (Pure)
Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models
Cartis, C., Gould, N. I. M. & Toint, P., juin 2019, Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Demetriou, I. & Pardalos, P. (eds.). Springer Heidelberg, p. 5-26 22 p. (Springer Optimization and Its Applications; Vol 145).
Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférence › Chapitre

2 Actif

Complexity in nonlinear optimization
Toint, P. (Co-investigateur), Gould, N. I. M. (Co-investigateur) & Cartis, C. (Co-investigateur)
1/11/08 → …
Projet: Recherche
ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire
Sartenaer, A. (Co-investigateur) & Toint, P. (Co-investigateur)
1/01/87 → …
Projet: Axe de recherche

4 Présentation orale
2 Recherche/Enseignement dans une institution externe
1 Discours invité
1 Visite à une institution académique externe

A path and some adventures in the jungle of high-order nonlinear optimization
Toint, P. (Orateur)
24 oct. 2017
Activité: Discours ou présentation › Discours invité
How much patience do you have? Issues in complexity for nonlinear optimization
Toint, P. (Orateur invité)
5 févr. 2016
Activité: Discours ou présentation › Présentation orale
Hong Kong Polytechnic University
Toint, P. (Chercheur visiteur)
31 janv. 2016 → 14 févr. 2016
Activité: Visite d'une organisation externe › Recherche/Enseignement dans une institution externe

Leverhulme Fellow
Toint, P. (Bénéficiaire), sept. 2015
Prix: Bourse attribuée par concours

Contient cette citation

@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

SN - 0233-1934

VL - 64

SP - 1349

EP - 1361

JO - Optimization

JF - Optimization

IS - 5

ER -

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

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

Projets

Activités

Prix

Contient cette citation