Polynomiality of infeasible-interior-point algorithms for linear programming

Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal-dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interior points, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. The paper shows that a modification of the Kojima-Megiddo-Mizuno algorithm ‘solves’ the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, it develops an O(nL)-iteration complexity result for a variant of the algorithm.