Issues Relating Linear Programming, Complexity Theory and Numeric Computation

线性规划、复杂性理论和数值计算相关问题

• 批准号: 9403580
• 负责人: James Renegar
• 金额: $ 12.21万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-07-01 至 1999-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9403580&HistoricalAwards=false
• 关键词: Issues; Relating; Linear; Programming; Complexity

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.

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