An inner ellipsoid algorithm for linear programming

A interior point algorithm for linear programming is developed. At every step of the method a interior point to the polytope is available. With center at this point, an ellipsoid wholly included in the polytope is considered. The optimization of the linear objective over the ellipsoid is carried out through the solution of a least squares type system of equations. The resulting interior point is adopted for the next iteration. As a result of this work, two different methods have been proposed for solving the least square problem, each showing a considerable decrease in the number of operations required in every step. Lastly, a computer application was developed for the method, in the Fortran 77, for an IBM PC AT, to carry out an experimental study of the behaviour of the algorithm in comparison with the Simplex Method.