Interior point methods with self-regular proximities

An interesting problem in the theory of interior point methods is the investigation of the complexity of small-step and large-step methods. While small-step methods enjoy a better theoretical worst-case complexity, large-step methods perform better in practice. A significant breakthrough is due to Peng et al., who showed that large-step self-regular interior point methods can solve the linear optimization problem with accuracy ϵ in 𝒪(√n log n log(n/ϵ)) iterations. This improved the previous result of 𝒪(n log(n/ϵ)), but is still slightly worse than the 𝒪(√n log(n/ϵ)) iteration bound of small-step algorithms. In this paper we present a new and simplified analysis of the algorithm for monotone linear complementarity problems. Our results are based on a recent paper by Salahi and Terlaky.