CONSTANT POTENTIAL PRIMAL-DUAL ALGORITHMS - A FRAMEWORK

We start 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 we establish a framework for primal-dual algorithms that keep a potential function value fixed. We show that if the potential function used in the algorithm is compatible with a cor responding neighborhood of the central path then the convergence proof s simplify greatly. Our algorithms have the property that all the iter ates can be kept in a neighborhood of the central path without using a ny centering in the search directions.