Projects per year
Abstract
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.
Original language  English 

Title of host publication  Invited Lectures 
Editors  Boyan Sirakov, Paulo Ney de Souza, Marcelo Viana 
Publisher  World Scientific Publishing Co Pte Ltd 
Pages  37293768 
Number of pages  40 
ISBN (Electronic)  9789813272934 
Publication status  Published  1 Jan 2018 
Event  2018 International Congress of Mathematicians, ICM 2018  Rio de Janeiro, Brazil Duration: 1 Aug 2018 → 9 Aug 2018 
Publication series
Name  Proceedings of the International Congress of Mathematicians, ICM 2018 

Volume  4 
Conference
Conference  2018 International Congress of Mathematicians, ICM 2018 

Country  Brazil 
City  Rio de Janeiro 
Period  1/08/18 → 9/08/18 
Keywords
 Nonlinear optimization
 Evaluation complexity
 Regularization methods
Fingerprint
Dive into the research topics of 'Worstcase evaluation complexity and optimality of secondorder methods for nonconvex smooth optimization'. Together they form a unique fingerprint.Projects
 2 Active

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