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

Coralia Cartis; N.I.M. Gould; Philippe Toint

doi:10.1137/100812276

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

Coralia Cartis, N.I.M. Gould, Philippe Toint

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

62 Téléchargements (Pure)

Résumé

The (optimal) function/gradient evaluations worst-case complexity analysis available for the adaptive regularization 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 [Worst Case Complexity of Direct Search, Technical report, Preprint 10-17, Department of Mathematics, University of Coimbra, Coimbra, Portugal, 2010] is also discussed, giving some theoretical insight into the relative merits of various methods in this popular class of algorithms. © 2012 Society for Industrial and Applied Mathematics.

langue originale	Anglais
Pages (de - à)	66-86
Nombre de pages	21
journal	SIAM Journal on Optimization
Volume	22
Numéro de publication	1
Les DOIs	https://doi.org/10.1137/100812276
Etat de la publication	Publié - 1 janv. 2012

SDG des Nations Unies

Ce résultat contribue à ou aux Objectifs de développement durable suivants

Accès au document

10.1137/100812276

70755manuscrit soumis, 0,98 MB

Autres fichiers et liens

Link to publication in Scopus

36 Citations
6 Article
3 Papier de travail
1 Livre

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
49 Téléchargements (Pure)
An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity
Gratton, S., Simon, E. & Toint, P., 21 janv. 2020, Dans: Mathematical Programming. 187, 1-2, p. 1-24 19 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
70 Téléchargements (Pure)

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

3 Présentation orale
1 Recherche/Enseignement dans une institution externe
1 Visite à une institution académique externe

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
How much patience do you have? Issues in complexity for nonlinear optimization
Toint, P. (Orateur)
31 janv. 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

Contient cette citation

@article{08432aa1d7be4cda8d19c710c3626e5a,

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

abstract = "The (optimal) function/gradient evaluations worst-case complexity analysis available for the adaptive regularization 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 [Worst Case Complexity of Direct Search, Technical report, Preprint 10-17, Department of Mathematics, University of Coimbra, Coimbra, Portugal, 2010] is also discussed, giving some theoretical insight into the relative merits of various methods in this popular class of algorithms. {\textcopyright} 2012 Society for Industrial and Applied Mathematics.",

keywords = " nonconvex optimization., finite-differences, oracle complexity, first-order methods, worst-case analysis, derivative free optimization",

author = "Coralia Cartis and N.I.M. Gould and Philippe Toint",

note = "Publication code : FP SB092/2010/03 ; SB04977/2010/03",

year = "2012",

month = jan,

day = "1",

doi = "10.1137/100812276",

language = "English",

volume = "22",

pages = "66--86",

journal = "SIAM Journal on Optimization",

issn = "1095-7189",

publisher = "Society for Industrial and Applied Mathematics",

number = "1",

}

TY - JOUR

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

AU - Cartis, Coralia

AU - Gould, N.I.M.

AU - Toint, Philippe

N1 - Publication code : FP SB092/2010/03 ; SB04977/2010/03

PY - 2012/1/1

Y1 - 2012/1/1

N2 - The (optimal) function/gradient evaluations worst-case complexity analysis available for the adaptive regularization 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 [Worst Case Complexity of Direct Search, Technical report, Preprint 10-17, Department of Mathematics, University of Coimbra, Coimbra, Portugal, 2010] is also discussed, giving some theoretical insight into the relative merits of various methods in this popular class of algorithms. © 2012 Society for Industrial and Applied Mathematics.

AB - The (optimal) function/gradient evaluations worst-case complexity analysis available for the adaptive regularization 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 [Worst Case Complexity of Direct Search, Technical report, Preprint 10-17, Department of Mathematics, University of Coimbra, Coimbra, Portugal, 2010] is also discussed, giving some theoretical insight into the relative merits of various methods in this popular class of algorithms. © 2012 Society for Industrial and Applied Mathematics.

KW - nonconvex optimization.

KW - finite-differences

KW - oracle complexity

KW - first-order methods

KW - worst-case analysis

KW - derivative free optimization

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

U2 - 10.1137/100812276

DO - 10.1137/100812276

M3 - Article

SN - 1095-7189

VL - 22

SP - 66

EP - 86

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 1

ER -

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

Résumé

SDG des Nations Unies

Accès au document

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

Projets

Activités

Contient cette citation