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

双向研究街：优化中的几何算法和基于计算机的离散几何

基本信息

批准号：
1818969
负责人：
Jesus De Loera
金额：
$ 30.68万
依托单位：
University of California-Davis
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-07-01 至 2023-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1818969&HistoricalAwards=false
关键词：
Two Way Research Street Geometric

项目摘要

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.

在不断变化的社会（例如，无人驾驶汽车）的人工智能和数据科学进步的基础上，是优化的数学理论。例如，凸和非线性优化是非常成功的深神经网络核心的发动机。该项目的第一部分开发了解决优化理论挑战所需的数学（例如，大量数据，不确定的数据）并创建更快，更准确的优化算法。计算机也在改变数学研究和发现的性质。例如，计算机可以得出公式和证据自动，计算机可以搜索示例，现在由于机器学习，它们可以更轻松地提取模式。该项目的第二部分研究了使用人工智能和算法攻击数学问题的算法的使用，尤其是在几何学中。计算数学中的项目具有两个相互作用的组成部分：第一个组成部分是应用方法的方法，用于从CONVEX几何形状中，对数量的构图，数字和组合数的构建图，并在数量上开发新数字，并将其用于组合数字，并在数量的几何形式中进行编号，并在数量上进行综述，并在数量上进行数字，并将其构成数字，并构成数字，并构成了数字，并将其构成数字，并构成了数字，并将其构成数字，并构成了数字，并将其构成数字，以及构图，并将其构成数字，以及构图，以及构图的数量效果。科学，尤其是具有特殊条件的数据聚类。该项目还研究了整数和混合构成变量的增强算法（原始）算法，这些算法是概括用于单纯形方法的枢纽的算法。该项目的第二个组成部分研究了可与计算机一起研究的几何和组合问题。将强调凸几何形状中许多基本组合量的计算，包括锥体的整数caratheodory数字的确切值，定量的HELLY数字和整体ra rabon-tverberg数字。该项目提出了一种基于计算机的方法，以证明或反驳几种定理的几何形状。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响评估标准通过评估来获得支持的。