A Polynomial Newton Method for Linear Programming

An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at most O(n(2)m(2)L) operations that there is no solution or, else, computes an exact solution in at most O(n(3)m(2)L) operations. The linear programming problem is treated as a parametrized feasibility problem and solved in at most O(n(3)m(2)L) operations.