Asymptotic Behavior of Interior-Point Methods: A View From Semi-Infinite Programming

We study the asymptotic behavior of interior-point methods for linear programming problems. Attempts to solve larger problems using interior-point methods lead to the question of how these algorithms behave as n (the number of variables) goes to infinity. Here, we take a different point of view and investigate what happens when n is infinite. Motivated by this approach, we study the limits of search directions, potential functions and central paths. We also suggest that the complexity of some linear programming problems may depend on the smoothness of the given problem rather than the number of variables. We prove that when n is infinite, for some subclasses of problems, one can still obtain a bound on the number of iterations required in terms of the smoothness of the problem and the desired accuracy.