On the optimal order of worst case complexity of direct search

M. Dodangeh, L. N. Vicente, Zaikun Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)

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. For smooth unconstrained optimization, it is now known that such methods require at most (Formula presented.) function evaluations to compute a gradient of norm below  (Formula presented.) , where n is the dimension of the problem. Such a maximal effort is reduced to (Formula presented.) if the function is convex. The factor (Formula presented.) 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 (Formula presented.) 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.
Original languageEnglish
Pages (from-to)699-708
Number of pages10
JournalOptimization Letters
Volume10
Issue number4
DOIs
Publication statusPublished - 1 Apr 2016
Externally publishedYes

Keywords

  • Cosine measure
  • Direct search
  • Optimal order
  • Positive spanning set
  • Sphere covering
  • Worst case complexity

ASJC Scopus subject areas

  • Control and Optimization

Cite this