Back to search

University of British Columbia

On the computation of the cosine measure in high dimensions

Abstract

dc:description

Direct search methods are an important class of algorithms to solve derivative-free optimization problems. These methods use a set of vectors known as search directions to compute trial points in order to seek function value decrease. Often, the convergence rate of these methods depend on a value known as the cosine measure, which describes how uniformly and densely a set of vectors spans a space. The cosine measure is defined as the solution to a minimax optimization problem. Currently, few algorithms have been proposed to solve the cosine measure optimization problem, and none have discussed solving the problem in higher dimensional spaces. To address this gap, we first introduce a useful reformulation of the cosine measure problem. Based on this reformulation, we propose new algorithms that scale effectively with dimension. Since this problem has recently been shown to be NP-Hard, the proposed algorithms are heuristic in nature. Additionally, we provide theorems to construct sets with nearly arbitrary cosine measures, allowing for the creation of a robust test set consisting of sets with varying structures. Using this test set, we demonstrate the effectiveness of our newly proposed algorithms compared to those in the existing literature.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sun, Scholar
Contributors dc:contributor
  • Hare, Warren

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/91522

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Sun, Scholar. On the computation of the cosine measure in high dimensions. master's thesis, University of British Columbia, 2025. http://hdl.handle.net/2429/91522