Within a unified framework made possible by the homotopy principle, this project is to formulate, implement and analyse new interior point algorithms for linear programming. Two broad classes of algorithms are distinguished. The first class of algorithms path-follow using Euler predictor and Newton corrector steps, and develop nonmonotonic iterates. Here the emphasis is on basic formulation, implementation and analysis. The second class of algorithms utilize restarts of the homotopy. They develop monotonic iterates, correspond to affine rescaling variants of Karmarkar's projective algorithm, and mesh well with the simplex algorithm. This project will develop an explicit null-space affine rescaling approach in which search directions are computed inexactly. An iterative method is the primary technique used to solve associated linear systems.
