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

人工智能和数据科学的进步正在改变着社会(例如无人驾驶汽车)，其基础是最优化的数学理论。例如，凸优化和非线性优化是非常成功的深度神经网络的核心引擎。该项目的第一部分开发了解决优化理论挑战(例如，更大量的数据、不确定的数据)和创建更快、更准确的优化算法所需的数学知识。计算机也正在改变数学研究和发现的性质。例如，计算机可以自动得出公式和证明，计算机可以搜索例子，现在他们可以更容易地提取模式，这要归功于机器学习。该项目的第二部分研究了如何使用人工智能和算法来解决数学中的问题，特别是几何中的问题。这个计算数学项目有两个相互作用的部分：第一个部分是应用凸几何、代数几何、数几何和组合学的方法来开发新的算法来解决数据科学中出现的混合整数优化问题，特别是具有特殊条件的数据的聚类。该项目还研究了整数和混合整数变量的增广(原始)算法，这些算法推广了单纯形法使用的旋转。该项目的第二部分研究几何和组合问题，这些问题可以用计算机来研究。重点介绍凸几何中一些基本组合量的计算，包括圆锥的整数Caratheodory数、定量Helly数和积分Radon-Tverberg数的精确值。该项目提出了一种基于计算机的方法来证明或反驳离散几何中的几个定理。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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 indiscrete 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.