On the computation of cosine measures in high dimensions

In derivative free optimization (DFO), the cosine measure is a value that often arises in the convergence analysis of direct search methods. Given the increasing interest in high-dimensional DFO problems, it is valuable to compute the cosine measure in this setting; however, this has recently been shown to be NP-hard. We propose a new formulation and heuristics to tackle the cosine measure problem in high dimensions. We establish new results that enable the construction of sets with prescribed cosine measures, providing a systematic way to generate test instances for comparing algorithms that compute the cosine measure. Finally, we compare the algorithms proposed in this paper with some existing algorithms from the literature.