A note about the complexity of minimizing Nesterov's smooth Chebyshev-Rosenbrock function

Coralia Cartis; Nicholas I. M. Gould; Philippe L. Toint

doi:10.1080/10556788.2012.722632

A note about the complexity of minimizing Nesterov's smooth Chebyshev-Rosenbrock function

Coralia Cartis^*, Nicholas I. M. Gould, Philippe L. Toint

^*Corresponding author for this work

School of Mathematics

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

Abstract / Description of output

This short note considers and resolves the apparent contradiction between known worst-case complexity results for first- and second-order methods for solving unconstrained smooth nonconvex optimization problems and a recent note by Jarre [On Nesterov's smooth Chebyshev-Rosenbrock function, Optim. Methods Softw. (2011)] implying a very large lower bound on the number of iterations required to reach the solution's neighbourhood for a specific problem with variable dimension.

Original language	English
Pages (from-to)	451-457
Number of pages	7
Journal	Optimization Methods & Software
Volume	28
Issue number	3
DOIs	https://doi.org/10.1080/10556788.2012.722632
Publication status	Published - 1 Jun 2013

Keywords / Materials (for Non-textual outputs)

evaluation complexity
worst-case analysis
nonconvex optimization
90C30
65K05
90C60
68Q25
UNCONSTRAINED OPTIMIZATION

Access to Document

10.1080/10556788.2012.722632

Optimal Newton-Type Algorithms for Large-Scale Nonlinear Optimization
Cartis, C.
EPSRC
1/09/11 → 30/09/13
Project: Research

Cite this

@article{fb059c9ba1674113aedfa8f988413372,

title = "A note about the complexity of minimizing Nesterov's smooth Chebyshev-Rosenbrock function",

abstract = "This short note considers and resolves the apparent contradiction between known worst-case complexity results for first- and second-order methods for solving unconstrained smooth nonconvex optimization problems and a recent note by Jarre [On Nesterov's smooth Chebyshev-Rosenbrock function, Optim. Methods Softw. (2011)] implying a very large lower bound on the number of iterations required to reach the solution's neighbourhood for a specific problem with variable dimension.",

keywords = "evaluation complexity, worst-case analysis, nonconvex optimization, 90C30, 65K05, 90C60, 68Q25, UNCONSTRAINED OPTIMIZATION",

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

year = "2013",

month = jun,

day = "1",

doi = "10.1080/10556788.2012.722632",

language = "English",

volume = "28",

pages = "451--457",

journal = "Optimization Methods & Software",

issn = "1055-6788",

publisher = "Taylor and Francis Ltd.",

number = "3",

}

TY - JOUR

T1 - A note about the complexity of minimizing Nesterov's smooth Chebyshev-Rosenbrock function

AU - Cartis, Coralia

AU - Gould, Nicholas I. M.

AU - Toint, Philippe L.

PY - 2013/6/1

Y1 - 2013/6/1

N2 - This short note considers and resolves the apparent contradiction between known worst-case complexity results for first- and second-order methods for solving unconstrained smooth nonconvex optimization problems and a recent note by Jarre [On Nesterov's smooth Chebyshev-Rosenbrock function, Optim. Methods Softw. (2011)] implying a very large lower bound on the number of iterations required to reach the solution's neighbourhood for a specific problem with variable dimension.

AB - This short note considers and resolves the apparent contradiction between known worst-case complexity results for first- and second-order methods for solving unconstrained smooth nonconvex optimization problems and a recent note by Jarre [On Nesterov's smooth Chebyshev-Rosenbrock function, Optim. Methods Softw. (2011)] implying a very large lower bound on the number of iterations required to reach the solution's neighbourhood for a specific problem with variable dimension.

KW - evaluation complexity

KW - worst-case analysis

KW - nonconvex optimization

KW - 90C30

KW - 65K05

KW - 90C60

KW - 68Q25

KW - UNCONSTRAINED OPTIMIZATION

U2 - 10.1080/10556788.2012.722632

DO - 10.1080/10556788.2012.722632

M3 - Article

SN - 1055-6788

VL - 28

SP - 451

EP - 457

JO - Optimization Methods & Software

JF - Optimization Methods & Software

IS - 3

ER -

A note about the complexity of minimizing Nesterov's smooth Chebyshev-Rosenbrock function

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

Optimal Newton-Type Algorithms for Large-Scale Nonlinear Optimization

Cite this