Topological Data Analysis in Optimization
Abstract
The purpose of this project is to apply computational techniques from topological data analysis (TDA) to solve optimization problems. TDA is a relatively nascent research area that allows one to describe geometric properties of a data set, such as connectivity, existence of holes, or clustering, in a way that imposes minimal assumptions on parametric structures like coordinate systems or forms of probability distributions. In recent years, TDA has been successfully applied to many different scientific domains, such as time series analysis, text mining, cancer biology, and materials science. To the best of our knowledge, this project will be the first to use TDA in the area of optimization. The basic principle that we will exploit is that TDA excels at identifying coarse features in datasets using a technique called persistence, and is not sensitive to more localized phenomena. This allows us to augment existing approaches to optimization in several ways:TDA-enhanced local search Local search algorithms are, by definition, focused only on local features of the solution to a problem. We propose a two-step process in which one gathers many local minimizers to a problem, then uses TDA to identify the coarse features of those minimizers. These features can then inform further iterations of local search, such as imposing a tabu list. TDA-enhanced branch-and-bound The key factor that determines the efficiency of the branch and- bound method for integer programs is the branching rule that decides which fractional variable should be rounded. This is generally performed in an ad hoc fashion that involves various attributes of that fractional value, such as how far it is from its nearest integer, the number of constraints it appears in, its objective coefficient, and so on. Recent research has demonstrated that machine learning techniques can find significantly better branching rules than those constructed by hand. We anticipate that TDA can also uncover features that lead to improved branching rules.TDA-enhanced neural networks Given a neural network with fixed topology and response functions at the nodes, the problem of selecting weights is often highly non-convex. Given a large set of initial starting points, iterative methods often converge to many different local minimizers. We are unaware of any work at present that studies the structure of these local minimizers, and we expect that there is much to be learned from it. One of the highest value potential applications would be to use TDA to influence the design of the networkarchitecture. If successful, the outcomes of this project will provide fundamental advancements to optimization theory and practice by leveraging topological shape information that has previously gone unexploited.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 15, 2021
- Source ID
- N000142112208
Entities
People
- John Gunnar Carlsson
Organizations
- Office of Naval Research
- United States Navy
- University of Southern California