Optimization Online


Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization

Frank E. Curtis (frank.e.curtis***at***gmail.com)
Daniel P. Robinson (daniel.p.robinson***at***gmail.com)
Clément W. Royer (clement.royer***at***dauphine.psl.eu)
Stephen J. Wright (swright***at***cs.wisc.edu)

Abstract: 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.

Keywords: smooth nonconvex optimization, trust-region methods, Newton’s method, conjugate gradient method, Lanczos method, worst-case complexity, negative curvature

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: Lehigh ISE Technical Report 19T-028

Download: [PDF]

Entry Submitted: 12/09/2019
Entry Accepted: 12/09/2019
Entry Last Modified: 08/02/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society