CAREER: On Using Condition Numbers, Approximate Data, Knowledge in the Complexity Theory of Linear Programming

本研究将形式化将知识纳入近似数据理论以确定算法复杂度。算法将使用关于实际问题实例的可行性、稀疏性和线性的知识来降低提供近似解决方案所需的数据准确性。这些技术将应用于数值问题，如线性规划、凸二次规划、正定规划，以及只给出实际问题实例数据近似值的线性互补问题。要开发的算法将是计算效率高的，并且将使用几乎最小的数据精度来衡量条件数。该研究将进一步探讨同时使用条件措施和知识的问题与实际的精确数据。这些结果将用于发展近似数据的统一理论。研究人员将开发一门新的优化研究生课程，并将继续开发工业工程和运筹学系列研讨会。传统的基于图灵机计算模型的复杂性理论存在一些局限性。首先，它假设问题数据是合理和准确的。其次，它根据输入的位长度来衡量算法的效率，而不考虑特定问题实例的内在难度。发展新的复杂性度量，以反映解决特定问题实例的内在困难，是计算科学的一个重要推动力。从这项研究中获得的理论见解有可能转化为数学规划和计算机科学的实际见解。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

9624022 Filipowski This research will formalize the inclusion of knowledge to the theory of approximate data for determination of algorithmic complexity. Algorithms will be constructed that use knowledge about the feasibility, sparsity, and linearity of actual problem instances to decrease the data accuracy necessary to provide approximate solutions. The techniques will be applied to numerical problems such as linear programs, convex quadratic programs, positive definite programs, and the linear complementary problem given only an approximation to the data of the actual problem instance. The algorithms to be developed will be computationally efficient and will use nearly minimal data precision as measured by a condition number. The research will further investigate the simultaneous use of condition measures and knowledge for problems specified with real exact data. The results will be used to develop a unified theory of approximate data. The investigator will develop a new graduate course on optimization and will continue the development of a seminar series in industrial engineering and operations research. Traditional complexity theory based on the Turing machine model of computation has several limitations. First, it assumes that problem data are rational and exact. Second, it measures the efficiency of an algorithm in terms of the bit length of the input, without consideration of the intrinsic difficulty of the particular problem instance. Developing new measures of complexity that reflect the intrinsic difficulty of solving particular problem instances represents an important thrust in computational science. The theoretical insights gained from this research have the potential to be translated into practical insights for mathematical programming and computer science.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.