On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems
From MaRDI portal
Publication:3083310
DOI10.1137/090774100zbMath1211.90225OpenAlexW2044207982MaRDI QIDQ3083310
No author found.
Publication date: 21 March 2011
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/56f4cdfe9a0fcc185a344307c12ac5ee2bbd5117
unconstrained optimizationNewton's methodnonlinear optimizationtrust-region methodsglobal rate of convergencesteepest-descent methodcubic regularizationglobal complexity bounds
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30) Numerical methods based on necessary conditions (49M05) Newton-type methods (49M15) Numerical methods based on nonlinear programming (49M37) Implicit function theorems; global Newton methods on manifolds (58C15)
Related Items
An incremental descent method for multi-objective optimization ⋮ Stochastic analysis of an adaptive cubic regularization method under inexact gradient evaluations and dynamic Hessian accuracy ⋮ Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization ⋮ Finding zeros of Hölder metrically subregular mappings via globally convergent Levenberg–Marquardt methods ⋮ On high-order model regularization for multiobjective optimization ⋮ Convergence guarantees for a class of non-convex and non-smooth optimization problems ⋮ A cubic regularization of Newton's method with finite difference Hessian approximations ⋮ A note about the complexity of minimizing Nesterov's smooth Chebyshev–Rosenbrock function ⋮ Co-design of linear systems using generalized Benders decomposition ⋮ Global complexity bound of the inexact Levenberg-Marquardt method ⋮ Complexity of the Newton method for set-valued maps ⋮ Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization ⋮ An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems ⋮ On the use of third-order models with fourth-order regularization for unconstrained optimization ⋮ The exact worst-case convergence rate of the gradient method with fixed step lengths for \(L\)-smooth functions ⋮ Lower bounds for non-convex stochastic optimization ⋮ Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization ⋮ Convergence and evaluation-complexity analysis of a regularized tensor-Newton method for solving nonlinear least-squares problems ⋮ A Newton-like method with mixed factorizations and cubic regularization for unconstrained minimization ⋮ On a global complexity bound of the Levenberg-marquardt method ⋮ A modified PRP-type conjugate gradient algorithm with complexity analysis and its application to image restoration problems ⋮ A nonlinear conjugate gradient method with complexity guarantees and its application to nonconvex regression ⋮ Inductive manifold learning using structured support vector machine ⋮ Global complexity bound analysis of the Levenberg-Marquardt method for nonsmooth equations and its application to the nonlinear complementarity problem ⋮ Fault Detection Based On Online Probability Density Function Estimation ⋮ On High-order Model Regularization for Constrained Optimization ⋮ Newton-type methods for non-convex optimization under inexact Hessian information ⋮ Lower bounds for finding stationary points I ⋮ Conditional gradient type methods for composite nonlinear and stochastic optimization ⋮ Improved optimization methods for image registration problems ⋮ Lower bounds for finding stationary points II: first-order methods ⋮ Complexity bounds for second-order optimality in unconstrained optimization ⋮ On the complexity of finding first-order critical points in constrained nonlinear optimization ⋮ Universal Regularization Methods: Varying the Power, the Smoothness and the Accuracy ⋮ Complexity of Partially Separable Convexly Constrained Optimization with Non-Lipschitzian Singularities ⋮ On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Condition ⋮ Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis ⋮ On High-Order Multilevel Optimization Strategies ⋮ Sub-sampled Newton methods ⋮ ARCq: a new adaptive regularization by cubics ⋮ On Regularization and Active-set Methods with Complexity for Constrained Optimization ⋮ Complexity Analysis of Second-Order Line-Search Algorithms for Smooth Nonconvex Optimization ⋮ Corrigendum to: ``On the complexity of finding first-order critical points in constrained nonlinear optimization ⋮ A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization ⋮ Policy Optimization for $\mathcal{H}_2$ Linear Control with $\mathcal{H}_\infty$ Robustness Guarantee: Implicit Regularization and Global Convergence ⋮ Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models ⋮ Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization ⋮ Updating the regularization parameter in the adaptive cubic regularization algorithm ⋮ Nonlinear stepsize control, trust regions and regularizations for unconstrained optimization ⋮ A classification of slow convergence near parametric periodic points of discrete dynamical systems ⋮ Unnamed Item ⋮ A Newton-like trust region method for large-scale unconstrained nonconvex minimization ⋮ Regional complexity analysis of algorithms for nonconvex smooth optimization ⋮ Second-order optimality and beyond: characterization and evaluation complexity in convexly constrained nonlinear optimization ⋮ A generalized worst-case complexity analysis for non-monotone line searches ⋮ Complexity of gradient descent for multiobjective optimization ⋮ Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization ⋮ Worst case complexity of direct search under convexity ⋮ Evaluation Complexity for Nonlinear Constrained Optimization Using Unscaled KKT Conditions and High-Order Models ⋮ On the use of iterative methods in cubic regularization for unconstrained optimization ⋮ On the Complexity of an Inexact Restoration Method for Constrained Optimization ⋮ A regularized Newton method without line search for unconstrained optimization ⋮ A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization ⋮ Worst case complexity of direct search ⋮ Large-scale unconstrained optimization using separable cubic modeling and matrix-free subspace minimization ⋮ Sharp Worst-Case Evaluation Complexity Bounds for Arbitrary-Order Nonconvex Optimization with Inexpensive Constraints ⋮ On the worst-case complexity of nonlinear stepsize control algorithms for convex unconstrained optimization ⋮ Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives ⋮ Trust-Region Methods Without Using Derivatives: Worst Case Complexity and the NonSmooth Case ⋮ A cubic regularization algorithm for unconstrained optimization using line search and nonmonotone techniques ⋮ Generalized uniformly optimal methods for nonlinear programming ⋮ On large-scale unconstrained optimization and arbitrary regularization ⋮ Iteration and evaluation complexity for the minimization of functions whose computation is intrinsically inexact ⋮ Oracle complexity of second-order methods for smooth convex optimization ⋮ Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization ⋮ On the Evaluation Complexity of Constrained Nonlinear Least-Squares and General Constrained Nonlinear Optimization Using Second-Order Methods ⋮ The Use of Quadratic Regularization with a Cubic Descent Condition for Unconstrained Optimization ⋮ Accelerated gradient methods for nonconvex nonlinear and stochastic programming
