Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
From MaRDI portal
Publication:6046826
nonconvex optimizationnonlinear optimizationtrust-region methodsworst-case evaluation complexityworst-case iteration complexity
Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)
Abstract: An algorithm for solving nonconvex smooth optimization problems is proposed, analyzed, and tested. The algorithm is an extension of the Trust Region Algorithm with Contractions and Expansions (TRACE) [Math. Prog. 162(1):132, 2017]. In particular, the extension allows the algorithm to use inexact solutions of the arising subproblems, which is an important feature for solving large-scale problems. Inexactness is allowed in a manner such that the optimal iteration complexity of for attaining an -approximate first-order stationary point is maintained while the worst-case complexity in terms of Hessian-vector products may be significantly improved as compared to the original TRACE. Numerical experiments show the benefits of allowing inexact subproblem solutions and that the algorithm compares favorably to a state-of-the-art technique.
Recommendations
- A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization
- An inexact regularized Newton framework with a worst-case iteration complexity of \(\mathscr{O}(\varepsilon^{-3/2})\) for nonconvex optimization
- An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity
- Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
- An inexact proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth optimization problems
Cites work
- A Newton-CG algorithm with complexity guarantees for smooth 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
- Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
- An inexact regularized Newton framework with a worst-case iteration complexity of \(\mathscr{O}(\varepsilon^{-3/2})\) for nonconvex optimization
- ARC\(_q\): a new adaptive regularization by cubics
- Benchmarking optimization software with performance profiles.
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Computing a Trust Region Step
- Concise complexity analyses for trust region methods
- Cubic regularization of Newton method and its global performance
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Evaluation complexity of algorithms for nonconvex optimization. Theory, computation and perspectives
- scientific article; zbMATH DE number 3725604 (Why is no real title available?)
- scientific article; zbMATH DE number 1568981 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Inexact Newton Methods
- On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems
- On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization
- On the generalized Lanczos trust-region method
- Probabilistic Bounds on the Extremal Eigenvalues and Condition Number by the Lanczos Algorithm
- Solving the trust-region subproblem by a generalized eigenvalue problem
- Solving the Trust-Region Subproblem using the Lanczos Method
- The Conjugate Gradient Method and Trust Regions in Large Scale Optimization
- The convergence of the generalized Lanczos trust-region method for the trust-region subproblem
- The use of quadratic regularization with a cubic descent condition for unconstrained optimization
- Trust Region Methods
- Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
- Updating the regularization parameter in the adaptive cubic regularization algorithm
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
Cited in
(10)- An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization
- An inexact regularized Newton framework with a worst-case iteration complexity of \(\mathscr{O}(\varepsilon^{-3/2})\) for nonconvex optimization
- Beyond nonconvexity: a universal trust-region method with new analyses
- Yet another fast variant of Newton's method for nonconvex optimization
- Complexity of zeroth- and first-order stochastic trust-region algorithms
- Riemannian trust-region methods for strict saddle functions with complexity guarantees
- A Hessian-free inexact regularized Newton method for composite convex optimization
- A Homogeneous Tensor Framework for High-Order Trust-Region and Spherical Polynomial Optimization
This page was built for publication: Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046826)
