Please use this identifier to cite or link to this item:
Title: Worst case complexity of direct search
Authors: Vicente, Luís Nunes 
Issue Date: 2013
Publisher: Springer-Verlag
Project: PEst-C/MAT/UI0324/2011 
Serial title, monograph or event: EURO Journal on Computational Optimization
Volume: 1
Issue: 1-2
Abstract: 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.
DOI: 10.1007/s13675-012-0003-7
Rights: embargoedAccess
Appears in Collections:I&D CMUC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat
complex.pdf243.7 kBAdobe PDFView/Open
Show full item record


checked on Jun 25, 2019

Page view(s) 50

checked on Oct 15, 2019


checked on Oct 15, 2019

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.