Open Collections

Sun, Scholar

University of British Columbia

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.

Text

2025-07-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/91522

Mathematics

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/