On the computation of the cosine measure in high dimensions

2025/06/24 by Warren Hare, Hare, Warren, Sun, Scholar · 1 citation
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Mathematical Modeling in Engineering #FOS: Mathematics #Optimization and Control (math.OC) #Stochastic processes and financial applications #advanced mathematical theories

paper · pdf · doi:10.48550/arxiv.2506.19723

openalex publication_date 2025/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In derivative-free optimization, the cosine measure is a value that often arises in the convergence analysis of direct search methods. Given the increasing interest in high-dimensional derivative-free optimization problems, it is valuable to compute the cosine measure in this setting; however, it has recently been shown to be NP-hard. 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 results 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.

Citations

• The cosine measure relative to a subspace
• Using orthogonally structured positive bases for constructing positive k-spanning sets with cosine measure guarantees
• Nicely structured positive bases with maximal cosine measure
• A deterministic algorithm to compute the cosine measure of a finite\n positive spanning set
• Spherical Discrepancy Minimization and Algorithmic Lower Bounds for\n Covering the Sphere
• Theory of Positive Linear Dependence

Cited by

• Complexity guarantees and polling strategies for Riemannian direct-search methods

Related

• A deterministic algorithm to compute the cosine measure of a finite\n positive spanning set
• A scaled conjugate gradient based direct search algorithm for high dimensional box constrained derivative free optimization
• Scalable Derivative-Free Optimization Algorithms with Low-Dimensional Subspace Techniques
• Learning to Guide Random Search
• Efficient approaches for escaping higher order saddle points in non-convex optimization