Issues Relating Linear Programming, Complexity Theory and Numeric Computation

主要目标是在由泛函分析而不是传统的由代数和组合学驱动的复杂性理论中开发和分析线性规划算法。特别关注有关计算机舍入误差和不精确数据的问题，例如如何使用关于待解问题结构的先验知识，以便使用比其他情况更低的计算精度有效地解决问题。使用迭代方法来解决应用方法时出现的方程进行了研究，因为算法是（接近）最优的可能性；通过近似理论研究了最优性。线性规划的摄动理论正在发展。某些在线性规划的背景下被证明有用的概念正在更一般的背景下被研究多元多项式。其目的是，所有的调查都将尽可能全面地进行；例如，定义非负性的锥体不需要是多面体。

The primary objectives concern the development and analysis of algorithms for linear programming within a complexity theory motivated by functional analysis rather than the traditional motivated by algebra and combinatorics. Special attention is given to issues concerning computer round-off error and inexact data, issues such as how one might use the prior knowledge one has regarding the structure of the problem to be solved in order to efficiently solve the problem using less computational precision than would be needed otherwise. The use of iterative methods for solving the equations that arise when applying methods is investigated, as is the possibility that the algorithms are (nearly) optimal; optimality is investigated via approximation theory. Perturbation theory for linear programming is being developed. Certain notions which have proven useful in the context of linear programming are being investigated in a more general context multi-variate polynomials. It is intended that all of the investigations will be carried out with as much generality as is possible; for example, the cones defining non-negativity will not be required to be polyhedral.