A simple complexity proof for a polynomial-time linear programming algorithm

In this article a polynomial-time algorithm for linear programming is proposed. This algorithm augments the objective by a logarithmic penalty function and then solves a sequence of quadratic approximations of this program. This algorithm has a complexity of O(m¹’/²L) iterations and O(m³’.⁵L) arithmetic operations, where m is the number of variables and L is the size of the problem encoding in binary. The novel feature of this algorithm is that it admits a very simple proof of its complexity, which makes it valuable both as a teaching and as a research tool. Moreover, its convergence can be accelerated by performing a line search and the line search stepsize is obtainable in a closed form. This algorithm maintains primal and dual feasibility at all iterations.