Optimization Online


On the optimal order of worst case complexity of direct search

M. Dodangeh(dodangeh***at***mat.uc.pt)
L. N. Vicente(lnv***at***mat.uc.pt)
Z. Zhang(zaikun.zhang***at***irit.fr)

Abstract: The worst case complexity of direct-search 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 14-38, Dept. Mathematics, Univ. Coimbra.

Download: [PDF]

Entry Submitted: 11/19/2014
Entry Accepted: 11/21/2014
Entry Last Modified: 11/19/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society