Using Computational Geometry to Solve Hard Mathematical Optimization Problems

这个项目的目的是使用计算几何中的算法来解决数学优化中的问题，并应用优化中的概念来解决计算几何中的问题。虽然几何和优化领域有着悠久的异花授粉历史，但这个项目将专门关注历史上没有从几何分析中受益的无限维优化。作为本研究重点的研究问题，可以应用于地理空间分析、交通运输理论、生态保护、机制设计、政治学等多个领域的各种问题。该项目包括一个广泛的外展计划，利用与行业、政府和代表性不足群体的现有关系，作为与高中、本科生和研究生级别的学生实践活动的基础。通过让这些合作者参与，这个项目将允许学生了解实践者和学术界的关切，从而确保我们的工作将具有智力和社会效益。本研究的关键主题是使用一个领域的知识，即计算几何或无限维优化，来解决另一个领域的问题。例如，无限维优化问题可能有无限维变量空间、无限维约束空间，或者两者都有。当这些空间中的一个具有与之相关的适当的几何结构时，我们已经证明了有时可以将无限维集归结为有限的集；人们可以利用欧几里德距离函数的凸性或单调性来识别足以满足整个问题的可行性的有限的“瓶颈点”集，从而降低其复杂性。作为第二个例子，计算几何中的许多问题都涉及到“均匀”形状的构造，即具有(例如)相等的面积、质量、周长或体积的形状。我们已经确定了问题属性，其中某些“公平”约束实际上等价于凸优化问题的最优性条件，这再次降低了原始问题的复杂性。因此，这项研究中介绍的问题和方法代表了一套新的工具，这些工具补充了现代运筹学研究人员和计算几何学家的武器库，综合了这两个领域的元素。

The purpose of this project is to use algorithms from computational geometry to solve problems in mathematical optimization and to apply concepts from optimization to solve problems in computational geometry. Although the fields of geometry and optimization have enjoyed a long history of cross-pollination, this project will specifically focus on infinite-dimensional optimization, which has not historically benefited from geometric analysis. The research problems that are the focus of this study can be applied to a variety of problems across many domains, such as geospatial analysis, transportation theory, ecological conservation, mechanism design, and political science. This project includes an extensive outreach program that leverages existing relationships with industry, government, and underrepresented groups as a basis for hands-on activities with students at the high school, undergraduate, and graduate levels. By involving these collaborators, this project will allow students to understand the concerns of practitioners in addition to those of academics, thus ensuring that our work will have both an intellectual and social benefit.The key theme of this research is the use of knowledge in one field, namely computational geometry or infinite-dimensional optimization, to solve a problem in the other. For example, an infinite-dimensional optimization problem might have an infinite-dimensional variable space, an infinite-dimensional constraint space, or both. When one of these spaces has an appropriate geometric structure associated with it, we have shown that it is sometimes possible to reduce an infinite-dimensional set to one that is finite; one might use convexity or monotonicity properties of the Euclidean distance function to identify a finite set of "bottleneck points" that are sufficient for feasibility of the entire problem, thereby reducing its complexity. As a second example, many problems in computational geometry are concerned with the construction of "equitable" shapes, meaning shapes that have (for example) equal area, mass, perimeter, or volume. We have identified problem attributes in which certain "equity" constraints are actually equivalent to the optimality conditions of a convex optimization problem, which again reduces the complexity of the original problem. The problems and methods introduced in this research are therefore representative of a new set of tools that complement the arsenal of modern operations researchers and computational geometers, synthesizing elements from both fields.