A Two-Way Research Street: Geometric Algorithms in Optimization and Computer-Based Discrete Geometry

University Of California-Davis, Davis CA

Investigators

Abstract

At the foundation of the progress in artificial intelligence and data science that is changing society (e.g., driverless cars) is the mathematical theory of optimization. For example, convex and non-linear optimization is the engine at the core of the very successful deep neural-networks. The first part of the project develops the mathematics necessary to solve optimization theory challenges (e.g., larger amounts of data, uncertain data) and to create faster, more accurate optimization algorithms. Computers are changing the nature of mathematical research and discovery too. For instance, computers can derive formulas and proofs automaticaly, computers can search for examples, and now they can more easily extract patterns thanks to machine learning. The second part of the project investigates the use of algorithms from artificial intelligence and algorithms to attack problems in mathematics, especially in geometry. This project in computational mathematics has two interacting components: The first component is to apply methods from convex geometry, algebraic geometry, geometry of numbers, and combinatorics to develop new algorithms for mixed-integer optimization problems arising in data science, especially the clustering of data with special conditions. The project also studies augmentation (primal) algorithms for integer and mixed-integer variables, these are algorithms that generalize the pivoting used for the simplex method. The second component of the project investigates geometric and combinatorial problems amenable to be investigated with computers. The computation of a number of fundamental combinatorial quantities in convex geometry, including the exact value of integer Caratheodory numbers for cones, quantitative Helly numbers, and integral Radon-Tverberg numbers, will be emphasized. The project presents a computer-based approach to prove or disprove several theorems in discrete geometry. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.