New algorithms for linear optimization in infinite-dimensional spaces

无限维空间中的线性问题是一种比一般有限维线性问题灵活得多的建模工具。这样做的代价是这些问题比有限维线性问题要困难得多。例如，随时间流动的最小代价问题，实际上是希尔伯特空间中的一个线性问题，是np困难的。该项目的主要目标是为广泛的无限维线性问题开发有效的算法，包括诸如随时间流动问题和连续线性规划等重要问题类别。新的算法将有保证的性能特征，在计算模型组成的操作特定于希尔伯特空间。在有限维空间中，任何具有这种特征的算法都必须同时是线性规划的多项式算法。另一方面，在无限维情况下，与许多传统的离散化方法相比，新算法将在问题的原始空间中工作。

Linear problems in infinite-dimensional spaces are a much more flexible modeling tool than usual finite-dimensional linear problems. The payment for this is that these problems are much more difficult than finite-dimensional linear problems. For instance, the minimum-cost flow over time problem, which is in fact a linear problem in a Hilbert space, is NP-hard. The main objective of this project is to develop efficient algorithms for a wide spectrum of infinite-dimensional linear problems including such important problem classes as flow over time problems and continuous linear programs. The new algorithms will have guaranteed performance characteristics in terms of a model of computation consisting of operations specific to Hilbert spaces. In the case of finite-dimensional spaces, any algorithm with such characteristics must be at the same time a polynomial algorithm for linear programming. On the other hand, in the infinite-dimensional case, the new algorithms will work in the original space of the problem, in contrast to many traditional discretization methods.