Constant potential primal-dual algorithms: A framework

The paper starts with a study of the primal-dual affine-scaling algorithms for linear programs. Using ideas from Kojima et al, Mizuno and Nagasawa, and new potential functions it establishes a framework for primal-dual algorithms that keep a potential function value fixed. The paper shows that if the potential function used in the algorithm is comparable with a corresponding neighborhood of the central path then the convergence proofs simplify greatly. The algorithms have the property that all the iterates can be kept in a neighborhood of the central path without using any centering in the search directions.