On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms

Recently, Mehrotra proposed a predictor-corrector primal-dual interior-point algorithm for linear programming. At each iteration, this algorithm utilizes a combination of three search directions: the predictor, the corrector and the centering directions, and requires only one matrix factorization. At present, Mehrotra’s algorithmic framework is widely regarded as the most practically efficient one and has been implemented in the highly successful interior-point code OB1. In this paper, the authors study the theoretical convergence properties of Mehrotra’s interior-point algorithmic framework. For generality, they carry out the present analysis on a horizontal linear complementarity problem that includes linear and quadratic programming, as well as the standard linear complementarity problem. Under the monotonicity assumption, the authors establish polynomial complexity bounds for two variants of the Mehrotra-type predictor-corrector interior-point algorithms. These results are summarized in the last section in a table.