Ill-Posedness and Finite Precision Arithmetic: A Complexity Analysis for Interior Point Methods

In this paper we analyze the effect of ill-posedness measures on the computational complexity of an interior point algorithm for solving a linear or a quadratic programming problem when finite precision arithmetic is used. The complexity is analyzed from the point of view of the number of iterations required to achieve an approximately optimal solution, as well as from the point of view of the numerical precision required in the computations. This work gives a view of computational complexity based on more “natural” properties of the problem instance.