
Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization
Curtis, F. E.; Robinson, D. P.; Royer, Clément; Wright, S. J. (2019), Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization, SIAM Journal on Optimization, 31, 1, p. 518-544. 10.1137/19M130563X
View/ Open
Type
Article accepté pour publication ou publiéDate
2019Journal name
SIAM Journal on OptimizationVolume
31Number
1Publisher
SIAM - Society for Industrial and Applied Mathematics
Pages
518-544
Publication identifier
Metadata
Show full item recordAuthor(s)
Curtis, F. E.Robinson, D. P.
Royer, Clément

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Wright, S. J.
Abstract (EN)
Worst-case complexity guarantees for nonconvex optimization algorithms have been a topic of growing interest. Multiple frameworks that achieve the best known complexity bounds among a broad class of first- and second-order strategies have been proposed. These methods have often been designed primarily with complexity guarantees in mind and, as a result, represent a departure from the algorithms that have proved to be the most effective in practice. In this paper, we consider trust-region Newton methods, one of the most popular classes of algorithms for solving nonconvex optimization problems. By introducing slight modifications to the original scheme, we obtain two methods---one based on exact subproblem solves and one exploiting inexact subproblem solves as in the popular “trust-region Newton-conjugate gradient” (trust-region Newton-CG) method---with iteration and operation complexity bounds that match the best known bounds for the aforementioned class of first- and second-order methods. The resulting trust-region Newton-CG method also retains the attractive practical behavior of classical trust-region Newton-CG, which we demonstrate with numerical comparisons on a standard benchmark test set.Subjects / Keywords
smooth nonconvex optimization; trust-region methods; Newton's method; conjugate gradient method; Lanczos method; worst-case complexity; negative curvatureRelated items
Showing items related by title and author.
-
Chan-Renous-Legoubin, Rémi; Royer, Clément W. (2022) Article accepté pour publication ou publié
-
Bergou, El Houcine; Diouane, Youssef; Kunc, Vladimir; Kungurtsev, Vyacheslav; Royer, Clément (2022) Article accepté pour publication ou publié
-
Matoussi, Anis; Possamaï, Dylan; Zhou, Chao (2021) Article accepté pour publication ou publié
-
Lions, Pierre-Louis (1989) Article accepté pour publication ou publié
-
Possamaï, Dylan; Piozin, Lambert; Matoussi, Anis (2014) Article accepté pour publication ou publié