Journal
EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION
Volume 1, Issue 1-2, Pages 143-153Publisher
ELSEVIER
DOI: 10.1007/s13675-012-0003-7
Keywords
Derivative-free optimization; Direct search; Worst case complexity; Sufficient decrease
Categories
Funding
- FCT [PTDC/MAT/098214/2008]
- Fundação para a Ciência e a Tecnologia [PTDC/MAT/098214/2008] Funding Source: FCT
Ask authors/readers for more resources
In this paper, we prove that the broad class of direct-search methods of directional type based on imposing sufficient decrease to accept newiterates 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 thesemethods 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 directsearch methods when a sufficient decrease condition based on the size of the steps is imposed to accept new iterates.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available