Projets par an
Résumé
We establish or refute the optimality of inexact secondorder methods for unconstrained nonconvex optimization from the point of view of worstcase evaluation complexity, improving and generalizing our previous results. To this aim, we consider a new general class of inexact secondorder algorithms for unconstrained optimization that includes regularization and trustregion variations of Newton’s method as well as of their linesearch variants. For each method in this class and arbitrary accuracy threshold ∊ 2 (0; 1), we exhibit a smooth objective function with bounded range, whose gradient is globally Lipschitz continuous and whose Hessian is αHölder continuous (for given α 2 [0; 1]), for which the method in question takes at least b∊(2+α)/(1+α^{)}c function evaluations to generate a first iterate whose gradient is smaller than ∊ in norm. Moreover, we also construct another function on which Newton’s takes b∊^{2}c evaluations, but whose Hessian is Lipschitz continuous on the path of iterates. These examples provide lower bounds on the worstcase evaluation complexity of methods in our class when applied to smooth problems satisfying the relevant assumptions. Furthermore, for α = 1, this lower bound is of the same order in ∊ as the upper bound on the worstcase evaluation complexity of the cubic regularization method and other algorithms in a class of methods recently proposed by Curtis, Robinson and Samadi or by Royer and Wright, thus implying that these methods have optimal worstcase evaluation complexity within a wider class of secondorder methods, and that Newton’s method is suboptimal.
langue originale  Anglais 

titre  Invited Lectures 
rédacteurs en chef  Boyan Sirakov, Paulo Ney de Souza, Marcelo Viana 
Editeur  World Scientific Publishing Co Pte Ltd 
Pages  37293768 
Nombre de pages  40 
ISBN (Electronique)  9789813272934 
Etat de la publication  Publié  1 janv. 2018 
Evénement  2018 International Congress of Mathematicians, ICM 2018  Rio de Janeiro, Brésil Durée: 1 août 2018 → 9 août 2018 
Série de publications
Nom  Proceedings of the International Congress of Mathematicians, ICM 2018 

Volume  4 
Une conférence
Une conférence  2018 International Congress of Mathematicians, ICM 2018 

Pays  Brésil 
La ville  Rio de Janeiro 
période  1/08/18 → 9/08/18 
Empreinte digitale Examiner les sujets de recherche de « Worstcase evaluation complexity and optimality of secondorder methods for nonconvex smooth optimization ». Ensemble, ils forment une empreinte digitale unique.
Projets
 2 Actif

Complexity in nonlinear optimization
TOINT, P., Gould, N. I. M. & Cartis, C.
1/11/08 → …
Projet: Recherche

ADALGOPT: ADALGOPT  Algorithmes avancés en optimisation nonlinéaire
1/01/87 → …
Projet: Axe de recherche