In this paper we present an infeasible interior-point algorithm for solving linear optimization problems. This algorithm is obtained by modifying the search direction in the algorithm [C. Roos, A full-Newton step ${O}(n)$ infeasible interior-point algorithm for linear optimization, 16(4) 2006, 1110-1136.]. The analysis of our algorithm is much simpler than that of the Roos’s algorithm at some places. The iteration bound of the algorithm is as good as the best known iteration bound $O(n\log \frac{1}{\varepsilon})$ for IIPMs.
Citation
Manuscript. Delft University of Technology. P.O. Box 5031, 2600 GA Delft, The Netherlands. May 2007.