A polynomial Newton method for linear programming (Q1094330)

A method for solving systems of affine equations on the nonnegative orthant is proposed. The problem is reduced to the (equivalent) nonlinear programming problem with the cost function in the form of a sum of logarithms. A Newton-like method, based on the second-order approximation of a log-function, is proposed for solving the latter problem. The basic steps of the method are the projection of the vector on the null space of the equation and the one-dimensional search. The procedure computes an exact solution in at most \(0(n^ 3m^ 2L)\) operations (here L is the size of the problem).