Polynomiality of infeasible-interior-point algorithms for linear programming (Q1340070)

An infeasible interior point algorithm for solving a primal-dual pair of linear programming problems finds approximate optimal solutions of the pair if both problems have interior points and detects infeasibility when the sequence of iterates diverges. Polynomial-time convergence of this algorithm under the assumption that both primal and dual problems have feasible points are proved. The author shows that a modification of the infeasible interior point algorithm ``solves'' the pair of problems in polynomial time, without assuming the existence of the LP solution. Furthermore, he develops an \(O(nL)\)-iteration complexity result for a variant of the algorithm.