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

A variant of Karmarkar's polynomial-time algorithm for linear programming is given. A logarithmic penalty function is attached to the objective function and the resulting nonlinear problem is solved by using a sequence of quadratic approximations. There is a simple proof of complexity of \(O(m^{1/2}L)\) iterations and \(O(m^{3,5}L)\) arithmetic operations, where m is the number of variables and L is the size of the problem encoded in binary.