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

107 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

Accès au document

10.1137/100812276

70755manuscrit soumis, 0,98 MB

Link to publication in Scopus

Empreinte digitale Examiner les sujets de recherche de « On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization ». Ensemble, ils forment une empreinte digitale unique.

Projets

2 Actif

Complexity in nonlinear optimization

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

1/11/08 → …

Projet: Recherche

ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire

SARTENAER, A. & TOINT, P.

1/01/87 → …

Projet: Axe de recherche

Activités

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

Philippe Toint (Orateur invité)

5 févr. 2016

Activité: Types de discours ou de présentation › Présentation orale

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

Philippe Toint (Orateur)

31 janv. 2016

Activité: Types de discours ou de présentation › Présentation orale

Polytechnic University of Hong Kong

Philippe Toint (Chercheur visiteur)

31 janv. 2016 → 14 févr. 2016

Activité: Types de Visite d'une organisation externe › Recherche/Enseignement dans une institution externe

Contient cette citation

Cartis, C., Gould, N. I. M., & Toint, P. (2012). On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization. SIAM Journal on Optimization, 22(1), 66-86. https://doi.org/10.1137/100812276

@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 = "1052-6234",

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

VL - 22

SP - 66

EP - 86

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 1

ER -