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

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

103 Downloads (Pure)

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. © 2012 Society for Industrial and Applied Mathematics.

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 - 1 Jan 2012

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

Keywords

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

Access to Document

10.1137/100812276

70755Submitted manuscript, 0.98 MB

Cite this

@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 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, 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 - https://www.scopus.com/pages/publications/84861621132

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

Abstract

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Evaluation complexity of algorithms for nonconvex optimization

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

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

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

Polytechnic University of Hong Kong

Cite this

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

Abstract

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Research output

Projects

Activities

Cite this