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

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

5 Téléchargements (Pure)

Résumé

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.

langue originale	Anglais
Pages (de - à)	451-457
Nombre de pages	7
journal	Optimization Methods and Software
Volume	28
Numéro de publication	3
Les DOIs	https://doi.org/10.1080/10556788.2012.722632
Etat de la publication	Publié - 1 juin 2013

Empreinte digitale

Contient cette citation

Cartis, C., Gould, N. I. M., & Toint, P. L. (2013). A note about the complexity of minimizing Nesterov's smooth Chebyshev-Rosenbrock function. Optimization Methods and Software, 28(3), 451-457. https://doi.org/10.1080/10556788.2012.722632

@article{53354db12c8843d8be7ec140b0c43392,

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, nonconvex optimization, worst-case analysis",

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

issn = "1055-6788",

publisher = "Taylor & Francis",

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 - nonconvex optimization

KW - worst-case analysis

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

U2 - 10.1080/10556788.2012.722632

DO - 10.1080/10556788.2012.722632

M3 - Article

AN - SCOPUS:84878316454

VL - 28

SP - 451

EP - 457

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 3

ER -

Accès au document

10.1080/10556788.2012.722632

NTR 20 2011manuscrit soumis, 643 KB

Link to publication in Scopus

Contenu connexe

Projets

Complexity in nonlinear optimization

Projet: Recherche

ADALGOPT - Algorithmes avancés en optimisation non-linéaire

Projet: Axe de recherche

Résultat de recherche

Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models

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

Optimality of orders one to three and beyond: Characterization and evaluation complexity in constrained nonconvex optimization

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

On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods

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

Improved worst-case evaluation complexity for potentially rank-deficient nonlinear least-Euclidean-norm problems using higher-order regularized models

Résultats de recherche: Papier de travail › Article de travail

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférence › Chapitre

Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using Hölder continuous gradients

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

Second-order optimality and beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

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

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

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

Prix

Leverhulme Fellow

Prix: Bourse attribuée par concours

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

Résumé

Empreinte digitale

Contient cette citation

Accès au document

Contenu connexe

Activités

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

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

Oxford University

Polytechnic University of Hong Kong

University of Oxford

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

Projets

Complexity in nonlinear optimization

ADALGOPT - Algorithmes avancés en optimisation non-linéaire

Résultat de recherche

Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models

Optimality of orders one to three and beyond: Characterization and evaluation complexity in constrained nonconvex optimization

On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods

Improved worst-case evaluation complexity for potentially rank-deficient nonlinear least-Euclidean-norm problems using higher-order regularized models

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

An example of slow convergence for Newton's method on a function with globally Lipschitz continuous Hessian

Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization

Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using Hölder continuous gradients

Second-order optimality and beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Prix

Leverhulme Fellow