9305760 Potra The investigator studies the computational complexity and superlinear convergence of interior point algorithms for linear programming, quadratic programming, linear complementarity problems, and some classes of nonlinear programming problems. Both problems with feasible and infeasible starting points are considered. In order to better characterize algorithms with good practical performance, worst case computational aomplexity results are complemented, whenever possible, by probabilistic complexity results. The goal of this study is to better understand practical performance of interior point methods and eventually to develop new interior point algorithms with superior numerical efficiency. The advent of interior point methods has revolutionized the field of mathematical programming. On the theoretical side, interior point methods have been used to prove that some important classes of optimization problems have polynomial complexity, which means that such problems are computationally tractable even when a large number of variables are involved. On the practical side, interior point methods have been implemented in several very efficient codes capable of solving large scale problems arising in economics, science, and technology that cannot be solved with classical methods. The purpose of the present proposal is to extend interior point methods to new classes of problems and to investigate their properties in a systematic way both from a deterministic and a probabilistic point of view. Successful completion of the research will contribute to new advances in the theory of interior point methods with a positive impact on the design of efficient practical algorithms.
