Asymptotic behavior of interior-point methods: A view from semi-infinite programming

Asymptotic behavior of interior-point methods: A view from semi-infinite programming

0.00 Avg rating0 Votes
Article ID: iaor20041212
Country: United States
Volume: 21
Issue: 2
Start Page Number: 354
End Page Number: 381
Publication Date: May 1996
Journal: Mathematics of Operations Research
Authors: ,
Keywords: interior point methods
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.