Worst case complexity of direct search under convexity
This paper considers directional direct-search methods applied to the unconstrained minimization of a real-valued, convex, and continuously differentiable objective function \(f\). It is proved that the direct-search methods of directional type, based on imposing sufficient decrease to accept new iterates, have the same worst case complexity bound and global rate of the gradient method for the unconstrained minimization of a convex and smooth function. The presented results are derived for convex functions where the supreme distance between any point in the initial level set and the solutions set is bounded. Such property is satisfied when the solutions set is bounded, but it is also met in several instances where the solutions sets are unbounded. It is shown that the number of iterations needed to reduce the norm of the gradient of the objective function below a certain threshold is at most proportional to the inverse of the threshold. It is also shown that the absolute error in the function values decay at a sublinear rate proportional to the inverse of the iteration counter. Finally, it is proved that the sequence of absolute errors of function values and iterates converges \(r\)-linearly in the strongly convex case.
- On the optimal order of worst case complexity of direct search
- Worst case complexity of direct search
- Worst-case complexity bounds of directional direct-search methods for multiobjective optimization
- On the worst-case evaluation complexity of non-monotone line search algorithms
- Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization
- STACS 2005
- On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions
- Complexity of multilinear problems in the worst case setting
- scientific article; zbMATH DE number 509206
- scientific article; zbMATH DE number 1512702
- Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
- Convex Analysis
- Cubic regularization of Newton method and its global performance
- CUTEr and SifDec
- Efficiency of coordinate descent methods on huge-scale optimization problems
- scientific article; zbMATH DE number 2002582 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Introduction to Derivative-Free Optimization
- Introductory lectures on convex optimization. A basic course.
- On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems
- On the Local Convergence of Pattern Search
- On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization
- Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
- Random gradient-free minimization of convex functions
- Recursive Trust-Region Methods for Multiscale Nonlinear Optimization
- Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization
- Worst case complexity of direct search
- On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions
- On the worst-case evaluation complexity of non-monotone line search algorithms
- An indicator for the switch from derivative-free to derivative-based optimization
- Worst-case complexity bounds of directional direct-search methods for multiobjective optimization
- Efficient unconstrained black box optimization
- On the optimal order of worst case complexity of direct search
- A second-order globally convergent direct-search method and its worst-case complexity
- On the worst-case complexity of nonlinear stepsize control algorithms for convex unconstrained optimization
- Trust-region methods without using derivatives: worst case complexity and the nonsmooth case
- scientific article; zbMATH DE number 1512702 (Why is no real title available?)
- Stochastic three points method for unconstrained smooth minimization
- A note on the worst-case complexity of nonlinear stepsize control methods for convex smooth unconstrained optimization
- Derivative-free optimization methods
- Direct search based on probabilistic descent
- On the worst-case inefficiency of CGKA
- Worst-case evaluation complexity of a derivative-free quadratic regularization method
- Worst case complexity bounds for linesearch-type derivative-free algorithms
- Stochastic zeroth order descent with structured directions
- Direct-search methods in the year 2025: theoretical guarantees and algorithmic paradigms
- A subspace inertial method for derivative-free nonlinear monotone equations
- Worst case complexity of direct search
This page was built for publication: Worst case complexity of direct search under convexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962720)
