A primal-dual variant of the Iri-Imai algorithm for linear programming

A local acceleration method for primal-dual potential-reduction algorithms is introduced. The method developed here uses modified Newton search direct ions to minimize the Tanabe-Todd-Ye (TTY) potential function, and can be re garded as a primal-dual variant df the Iri-Imai algorithm based on the mult iplicative analogue of Karmarkar's potential function. When iterates are cl ose to an optimal solution, the TTY potential function hits negative curvat ure along the generated search directions. Therefore, large reductions in t he potential function can be obtained, guaranteeing polynomial and quadrati c convergence to nondegenerate solutions.