AF: Small: Algorithms March on through Continuous and Combinatorial Methods

本项目将继续探索算法设计中连续与组合方法的结合。连续方法类似于高中微积分，其中函数导数的概念用于寻找问题的精确，最优解，例如游过流动小溪的最短路径。组合方法的一个例子是乘法，人们按照简单的一步一步的方法（算法）来计算乘积。在优化中，这两种技术都被用来计算许多问题的最优解。一个这样的例子是航空公司调度，它结合了员工调度，路线规划，甚至利润最大化的各个方面。最近，优化方面的一项突破将这些方法在较低层次上结合起来。组合问题（如调度人员）转化为连续问题（如多变量实数函数优化）。基于对原始问题的理解，重新引入组合结构，以加快基于微积分的方法。这导致了在为基本问题（如线性系统的解）生成理论上快速算法方面的显著突破。这些算法适用于气候建模、天气预测和石油勘探等领域。该技术还在线性规划领域取得了令人兴奋的进展，例如，在前面提到的航空公司调度的应用中使用了线性规划。在这个项目中，研究了“预调节”函数的想法，以允许连续（“基于微积分的”）优化技术运行得更快。一个例子是在一行上生成函数的插值。函数的值是在特定的点上指定的，人们希望在直线上的许多点上产生“最平滑”的插值。这可以看作是一个多变量问题，其中每个点的值是一个变量，但失去了线的结构。将这种结构重新整合到多变量优化技术中产生了非常快的算法。这种简单的直觉已经应用于更复杂的情况，包括凸优化中的非常普遍的问题，并且正在取得成果。本项目将尝试进一步理解和扩展这些技术的适用性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project will continue the exploration of the combination of continuous and combinatorial methods for algorithm design. Continuous methods are similar to high school calculus, where the notion of the derivative of a function is used to find exact, optimal solutions to problems such as the shortest way to swim across a moving creek. An example of a combinatorial method is multiplication, where one follows a simple step-by-step method (algorithm) to compute a product. In optimization, both techniques have been used to compute the optimal solutions for many problems. One such example is airline scheduling, which combines aspects of staff scheduling, route planning, and even profit maximization. Recently, a breakthrough in optimization has combined these approaches at a lower level. Combinatorial problems (e.g., scheduling staff) are translated to continuous ones (e.g., multi-variable real number function optimization). Combinatorial structure is re-imposed, based on understanding of the original problem, to speed up calculus-based methods. This has led to remarkable breakthroughs in producing theoretically fast algorithms for basic problems such as the solution of linear systems. Such algorithms are applicable, for example, in climate modelling, weather predictions, and oil exploration. The technique is also making exciting inroads into the area of linear programming, which is used, for example, in the previously mentioned application of airline scheduling.In this project, the idea of "pre-conditioning" a function is studied to allow for continuous ("calculus-based") optimization techniques to run faster. One example is producing an interpolation of a function on a line. The value of the function is specified at particular points, and one wishes to produce the "smoothest" interpolation on the many points on the line. This can be viewed as a multi-variable problem where the value of each point is a variable, but one loses the structure of the line. Re-incorporating this structure into the multi-variable optimization techniques produces very fast algorithms. This simple intuition has been applied to more complicated situations, ranging to very general problems in convex optimization, and is yielding fruit. This project will attempt to further understand and extend the applicability of these techniques.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.