A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
From MaRDI portal
conjugate gradient methodfirst-order optimality conditionsNewton's methodsecond-order optimality conditionssmooth nonconvex optimizationunconstrained optimizationworst-case complexity
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.
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)
