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

17 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

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.

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

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

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

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

Résumé

Accès au document

Complexity in nonlinear optimization

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

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

Polytechnic University of Hong Kong

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

Contient cette citation