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.