IMPROVING THE RATE OF CONVERGENCE OF INTERIOR POINT METHODS FOR LINEAR-PROGRAMMING

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x(k)) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence (x(k)BAR). Under the suitable assumptions it is shown that the sequence (x(k)BAR) converges superlinearly faster to the solution than (x(k)). Application of the procedure to the projective and affine scaling algorithms is discussed and some computational illustration is provided.