Large-Update Infeasible Interior-Point Methods for Linear Optimization

Abstract

Recently, C. Roos proposed a full-Newton step infeasible interior-point method (IIPM) for linear optimization (LO). Shortly afterwards, Mansouri and Roos presented a variant of this algorithm and Gu et al. a version with a simplified analysis. Roos' algorithm is a path-following method. It uses the so-called homotopy path as a guideline to an optimal solution. The algorithm has the advantage that it uses only full Newton steps (the step size is always 1, hence requires no computation), and its convergence rate is O(n), which coincides with the best known convergence rate for IIPMs. Apart from these nice features, the algorithm has the deficiency that it is a small-update method and hence it is too slow for practical purposes. In this thesis we design a large-update version of Roos' algorithm. We present a practically efficient implementation of (a variant of) the algorithm and compare its performance with that of the well- known LIPSOL package. The numerical results are promising as the iteration numbers of our algorithm are close to those of LIPSOL; in a few cases they outperform LIPSOL. Not surprisingly, as in large-update feasible interior-point methods (FIPMs), there is a gap between the practical and the theoretical behavior of our large-update IIPM. To be more precise, its theoretical convergence rate is O(n?n (log n)³) which is worse than the convergence rate of its full-Newton step variant. This phenomenon is well-known in the field of IPMs, and has been called the irony of IPMs: small-update methods have the best complexity results and are slow in practice, whereas large-update methods have worse complexity results and excellent performance in practice. For example, large-update FIPMs are by a factor $O(\log n)$ worse than that of the full-Newton step FIPMs, i.e., O(?nlogn) versus O(?n). The thesis also contains a survey of IIPMs that have been presented by several authors in last two decades. It covers a wide range of methods, starting from Lustig's algorithm, to the infeasible potential-reduction methods of Mizuno, Kojima and Todd. We focus on convergence properties and polynomiality of the IIPMs presented in our survey.