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

Research output: Contribution to journalArticlepeer-review


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 languageEnglish
Pages (from-to)451-457
Number of pages7
JournalOptimization Methods & Software
Issue number3
Publication statusPublished - 1 Jun 2013


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

Cite this