A Mehrotra-type predictor-corrector algorithm with polynomiality and Q-subquadratic convergence

Mehrotra’s predictor-corrector algorithm is currently considered to be one of the most practically efficient interior-point methods for linear programming. Recently, Zhang and Zhang studied the global convergence properties of the Mehrotra-type predictor-corrector approach and established polynomial complexity bounds for two interior-point algorithms that use the Mehrotra predictor-corrector approach. In this paper, the authors study the asymptotic convergence rate for the Mehrotra-type predictor-corrector interior-point algorithms. In particular, they construct an infeasible-interior-point algorithm and show that while retaining a complexity bound of O(n¹’.⁵t)-iterations, under certain conditions the algorithm also possesses a Q-subquadratic convergence, i.e., a convergence of Q-order 2 with an unbounded Q-factor.