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

13 Downloads (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
état	Publié - 1 janv. 2012

Empreinte digitale

Nonconvex Minimization

Derivative-free Methods

Derivative-free

First-order

Derivatives

Direct Search

Worst-case Analysis

Algorithm Complexity

Complexity Analysis

Unconstrained Optimization

Adaptive algorithms

Applied mathematics

Regularization

Finite Difference

Gradient

Evaluation

Class

Citer ceci

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

Cartis, Coralia ; Gould, N.I.M. ; Toint, Philippe. / On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization. Dans: SIAM Journal on Optimization. 2012 ; Vol 22, Numéro 1. p. 66-86.

@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. {\circledC} 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 = "1",

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

}

Cartis, C, Gould, NIM & Toint, P 2012, 'On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization', SIAM Journal on Optimization, VOL. 22, Numéro 1, p. 66-86. https://doi.org/10.1137/100812276

On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization. / Cartis, Coralia; Gould, N.I.M.; Toint, Philippe.

Dans: SIAM Journal on Optimization, Vol 22, Numéro 1, 01.01.2012, p. 66-86.

Résultats de recherche: Contribution à un journal/une revue › Article

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