Worst case complexity of direct search

By Luís Nunes Vicente. 2013

96 citations recorded by the source corpus.

In this paper, we prove that the broad class of direct-search methods of directional type based on imposing sufficient decrease to accept new iterates shares the worst case complexity bound of steepest descent for the unconstrained minimization of a smooth function, more precisely 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 squared. In direct-search methods, the objective function is evaluated, at each iteration, at a finite number of points. No derivatives are required. The action of declaring an iteration successful (moving into a point of lower objective function value) or unsuccessful (staying at the same iterate) is based on objective function value comparisons. Some of these methods are directional in the sense of moving along predefined directions along which the objective function will eventually decrease for sufficiently small step sizes. The worst case complexity bounds derived measure the maximum number of iterations as well as the maximum number of objective function evaluations required to find a point with a required norm of the gradient of the objective function, and are proved for such directional direct-search methods when a sufficient decrease condition based on the size of the steps is imposed to accept new iterates.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming (2013, background): “However, only few complexity results are available for these types of methods, mostly for convex programming (e.g., [24, 28]) and deterministic nonconvex programming problems (e.g., [3, 9, 28, 40]).”
Complexity and global rates of trust-region methods based on probabilistic models (2018, background): “Since interpolation techniques can ensure κ−1 d = O( √ n) with at most O(n) evaluations per iteration, one recovers the bounds O(n −2) for iterations and O(n2 −2) for function evaluations, a result also derived for direct search [27].”
On the Oracle Complexity of First-Order and Derivative-Free Algorithms for Smooth Nonconvex Minimization (2012, methodology): “(5) Note that the use of this inequality as a stopping criterion is not explicitly covered in Vicente (2010), but may nevertheless be constructed by using the stepsizes at unsuccessful iterations.”
Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization (2013, methodology): “Given the (first order) continuously differentiable nature of the objective function, one could work with a single positive spanning set throughout all the iterations, but the analysis of both global convergence [25] and worst case complexity [34] (in the case where a sufficient decrease condition i”