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 language | English |
---|---|
Pages (from-to) | 699-708 |
Number of pages | 10 |
Journal | Optimization Letters |
Volume | 10 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1 Apr 2016 |
Externally published | Yes |
Keywords
- Cosine measure
- Direct search
- Optimal order
- Positive spanning set
- Sphere covering
- Worst case complexity
ASJC Scopus subject areas
- Control and Optimization