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

Coralia Cartis; Nicholas I M Gould; Philippe L Toint

doi:10.1137/100812276

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

Coralia Cartis, Nicholas I M Gould, Philippe L Toint

School of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract / Description of output

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.

Original language	English
Pages (from-to)	66-86
Number of pages	21
Journal	Siam journal on optimization
Volume	22
Issue number	1
DOIs	https://doi.org/10.1137/100812276
Publication status	Published - 2012

Access to Document

10.1137/100812276

Cite this

@article{26d50bb29b894ff5816eb308a00e4004,

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

author = "Coralia Cartis and Gould, {Nicholas I M} and Toint, {Philippe L}",

year = "2012",

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

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, Nicholas I M

AU - Toint, Philippe L

PY - 2012

Y1 - 2012

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.

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.

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

U2 - 10.1137/100812276

DO - 10.1137/100812276

M3 - Article

SN - 1052-6234

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

Abstract / Description of output

Access to Document

Other files and links

Fingerprint

Cite this