A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization

DOI10.1007/S10107-019-01362-7MaRDI QIDQ2297654zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 20 February 2020

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.02924

zbMATH Keywords

conjugate gradient methodfirst-order optimality conditionsNewton's methodsecond-order optimality conditionssmooth nonconvex optimizationunconstrained optimizationworst-case complexity

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Methods of quasi-Newton type (90C53) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We consider minimization of a smooth nonconvex objective function using an iterative algorithm based on Newton's method and the linear conjugate gradient algorithm, with explicit detection and use of negative curvature directions for the Hessian of the objective function. The algorithm tracks Newton-conjugate gradient procedures developed in the 1980s closely, but includes enhancements that allow worst-case complexity results to be proved for convergence to points that satisfy approximate first-order and second-order optimality conditions. The complexity results match the best known results in the literature for second-order methods.

Review text

The authors deal with unconstrained optimization problems where the objective function is in general nonconvex and twice Lipschitz continuously differentiable. The aim of the paper is to develop a method that tracks the Newton-CG procedures but includes some safeguards and enhancements allowing worst-case complexity results to be proved for the convergence to points satisfying approximate first- and second-order necessary optimality conditions. The algorithm has two major components. In the first part, a linear CG method is used to solve a slightly damped Newton system. This process terminates either with an approximation to the Newton step or with a direction of negative curvature. The second part is called a ``minimum eigenvalue oracle and returns either a direction of sufficient negative curvature in a given symmetric matrix or a certificate that the matrix is almost positive definite. After that, a backtracking line search is used to identify a new iteration satisfying a sufficient decrease condition. It is shown that significant decrease in the objective function is attained at reasonable computational cost, i.e., in terms of the number of gradient evaluations or Hessian-vector products. A global worst-case complexity analysis of the algorithm is presented. Complexity results (bounds on the number of Hessian-vector products and gradient evaluations) for the convergence to points satisfying first- and second-order optimality conditions are proved. Elements of this analysis follow those presented in the earlier paper [\textit{C. W. Royer} and \textit{S. J. Wright}, SIAM J. Optim. 28, No. 2, 1448--1477 (2018; Zbl 1391.49055)].

Recommendations

• A log-barrier Newton-CG method for bound constrained optimization with complexity guarantees
• Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
• Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
• Linesearch Newton-CG methods for convex optimization with noise
• A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees

Cites work

• A nonmonotone truncated Newton-Krylov method exploiting negative curvature directions, for large scale unconstrained optimization
• A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization
• Accelerated methods for nonconvex optimization
• Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
• An inexact regularized Newton framework with a worst-case iteration complexity of \(\mathscr{O}(\varepsilon^{-3/2})\) for nonconvex optimization
• Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
• Complexity bounds for second-order optimality in unconstrained optimization
• Convex optimization: algorithms and complexity
• Cubic regularization of Newton method and its global performance
• Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Evaluating Derivatives
• Exploiting negative curvature directions in linesearch methods for unconstrained optimization
• Finding approximate local minima faster than gradient descent
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems
• The Conjugate Gradient Method and Trust Regions in Large Scale Optimization
• The use of quadratic regularization with a cubic descent condition for unconstrained optimization
• Truncated-Newton algorithms for large-scale unconstrained optimization
• Trust Region Methods
• Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using Hölder continuous gradients

Cited in

(40)

• Inexact derivative-free optimization for bilevel learning
• Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives
• Linesearch Newton-CG methods for convex optimization with noise
• Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
• Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence
• Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
• A log-barrier Newton-CG method for bound constrained optimization with complexity guarantees
• scientific article; zbMATH DE number 7366720 (Why is no real title available?)
• MINRES: from negative curvature detection to monotonicity properties
• Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
• First-Order Methods for Nonconvex Quadratic Minimization
• Convergence of Newton-MR under inexact Hessian information
• Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
• Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
• Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems
• A truncated three-term conjugate gradient method with complexity guarantees with applications to nonconvex regression problem
• A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees
• A nonlinear conjugate gradient method with complexity guarantees and its application to nonconvex regression
• A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees
• Inexact Newton-CG algorithms with complexity guarantees
• Parameter-free accelerated gradient descent for nonconvex minimization
• A hybrid inexact regularized Newton and negative curvature method
• Computing second-order points under equality constraints: revisiting Fletcher's augmented Lagrangian
• Nonlinear conjugate gradient for smooth convex functions
• An efficient hybrid conjugate gradient method with an adaptive strategy and applications in image restoration problems
• Complexity of a projected Newton-CG method for optimization with bounds
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
• Complexity guarantees for nonconvex Newton-MR under inexact Hessian information
• Homogeneous second-order descent framework: a fast alternative to Newton-type methods
• Beyond nonconvexity: a universal trust-region method with new analyses
• Gradient norm regularization second-order algorithms for solving nonconvex-strongly concave minimax problems
• On squared-variable formulations
• Yet another fast variant of Newton's method for nonconvex optimization
• Riemannian trust-region methods for strict saddle functions with complexity guarantees
• A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
• Riemannian adaptive regularized Newton methods with Hölder continuous Hessians
• Complexity analysis of inexact cubic-regularized primal-dual methods for finding second-order stationary points
• Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
• Exploiting negative curvature in conjunction with adaptive sampling: theoretical results and a practical algorithm
• Complexity guarantees of a class of three-term conjugate gradient algorithms for large-scale non-convex problems and applications

This page was built for publication: A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297654)