  


On the optimal order of worst case complexity of direct search
M. Dodangeh(dodangehmat.uc.pt) Abstract: The worst case complexity of directsearch methods has been recently analyzed when they use positive spanning sets and impose a sufficient decrease condition to accept new iterates. Assuming that the objective function is smooth, it is now known that such methods require at most O(n^2 epsilon^{2}) function evaluations to compute a gradient of norm below epsilon in (0,1), where n is the dimension of the problem. Such a maximal effort is reduced to O(n^2 epsilon^{1}) if the function is convex. The factor n^2 has been derived using the positive spanning set formed by the coordinate vectors and their negatives at all iterations. In this paper, we prove that such a factor of n^2 is optimal in these worst case complexity bounds, in the sense that no other positive spanning set will yield a better order of n. The proof is based on an observation that reveals the connection between cosine measure in positive spanning and sphere covering. Keywords: Direct search, worst case complexity, optimal order, sphere covering, positive spanning set, cosine measure. Category 1: Convex and Nonsmooth Optimization Category 2: Nonlinear Optimization Citation: Preprint 1438, Dept. Mathematics, Univ. Coimbra. Download: [PDF] Entry Submitted: 11/19/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  