ASYMPTOTIC-BEHAVIOR OF INTERIOR-POINT METHODS - A VIEW FROM SEMIINFINITE 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 differen t point of view and investigate what happens when n is infinite. Motiv ated by this approach, we study the limits of search directions, poten tial functions and central paths. We also suggest that the complexity of some linear programming problems may depend on the smoothness of th e given problem rather than the number of variables. We prove that whe n n is infinite, for some subclasses of problems, one can still obtain a bound on the number of iterations required in terms of the smoothne ss of the problem and the desired accuracy.