Thesis Defence: On the Computation of the Cosine Measure in High Dimensions
June 9 at 1:00 pm - 5:00 pm
Scholar Sun, supervised by Dr. Warren Hare, will defend their thesis titled “On the Computation of the Cosine Measure in High Dimensions” in partial fulfillment of the requirements for the degree of Master of Science in Mathematics.
An abstract for Scholar Sun’s thesis is included below.
Defences are open to all members of the campus community as well as the general public. Registration is not required for in-person defences.
Abstract
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.
