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.