The evaluation complexity of finding high-order minimizers of nonconvex optimization
Summary: We introduce the concept of strong high-order approximate minimizers of nonconvex optimization problems. These apply in both standard smooth and composite nonsmooth settings, and additionally allow convex or inexpensive constraints. An adaptive regularization algorithm is then proposed to find such approximate minimizers. Under suitable Lipschitz continuity assumptions, the evaluation complexity of this algorithm is investigated. The bounds obtained not only provide, to the best of our knowledge, the first known result for (unconstrained or inexpensively-constrained) composite problems for optimality orders exceeding one, but also give the first sharp bounds for high-order strong approximate th order minimizers of standard (unconstrained and inexpensively constrained) smooth problems, thereby complementing known results for weak minimizers. For the entire collection see [Zbl 07816361].
- Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization
- Second-order optimality and beyond: characterization and evaluation complexity in convexly constrained nonlinear optimization
- Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
- Evaluation complexity of algorithms for nonconvex optimization. Theory, computation and perspectives
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A proximal method for composite minimization
- Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
- Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization
- An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Complexity of Partially Separable Convexly Constrained Optimization with Non-Lipschitzian Singularities
- Compressed sensing
- Convergence and evaluation-complexity analysis of a regularized tensor-Newton method for solving nonlinear least-squares problems
- Cubic regularization of Newton method and its global performance
- High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms
- scientific article; zbMATH DE number 3744430 (Why is no real title available?)
- scientific article; zbMATH DE number 1746287 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming
- On the use of third-order models with fourth-order regularization for unconstrained optimization
- Second-order optimality and beyond: characterization and evaluation complexity in convexly constrained nonlinear optimization
- Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
- Some function classes related to the class of convex functions
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
- Worst-case evaluation complexity of regularization methods for smooth unconstrained optimization using Hölder continuous gradients
This page was built for publication: The evaluation complexity of finding high-order minimizers of nonconvex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6200212)
