Research on primal-dual interior point algorithms for mathematical programming. Final technical report, August 1991--August 1993.

摘要

Today interior-point methods of choice for general linear programming are primal-dual infeasible interior-point algorithms. There is a big gap between theoretical algorithms and practical algorithms. Major goals of the project were to narrow the gaps between theory and practice of primal-dual interior-point methods. The PI (principal investigator) played a leading role in joint work with Richard Tapia on constructing the first superlinear and polynomial primal-dual algorithm. PI's recent work on infeasible interior-point methods established the first polynomial result for today's interior-point methods of device. More recently, PI established polynomial complexities for Mehrotra-type predictor-corrector methods which have been widely regarded today as the most practically efficient methods. This work has laid a solid theoretical foundation for these methods.