Near boundary behavior of primal-dual potential reduction algorithms for linear programming

This paper is concerned with selection of the -parameter in the primal-dual potential reduction algorithm for linear programming. Chosen from , the level of determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant, must be set close to . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, the authors show that this is unnecessary. They find for any iterate that can be sometimes chosen in a wider range while still guaranteeing the currently best convergence rate of iterations. This finding is encouraging since in practice large values of have resulted in fast convergence rates. The present finding partially complements the recent result of Zhang, Tapia and Dennis concerning the local convergence rate of the algorithm.