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.