201. On the computation of the cosine measure in high dimensions.
Invited abstract in session MB-1: Advances in Large-Scale Derivative-Free Optimization , stream Zeroth and first-order optimization methods.
Monday, 10:30-12:30Room: B100/1001
Authors (first author is the speaker)
| 1. | Scholar Sun
|
| Mathematics, University of British Columbia |
Abstract
In derivative free optimization, the cosine measure is a value that quantifies the uniform density of a set of vectors. This value often arises in the convergence analysis of direct search methods, whereby choosing a set of search directions with a greater cosine measure can often yield better performance. Given the increasing interest in tackling high-dimensional DFO problems, it is valuable to be able to compute the cosine measure in this setting. However the cosine measure is computed as the solution to a minimax problem and has recently been shown to be NP-hard, making it difficult to scale into higher dimensions. We propose a new formulation of the problem and heuristic to tackle this problem in higher dimensions and compare it with existing algorithms in the literature. In addition, new theorems are presented to facilitate the construction of sets with specific cosine measures, allowing for the creation of a test-set to benchmark the algorithms with.
Keywords
- Derivative-free optimization
- Black-box optimization
- Global optimization
Status: accepted
Back to the list of papers