COWLES FOUNDATION FOR RESEARCH IN ECONOMICS
AT YALE UNIVERSITY

Box 208281
New Haven, CT 06520-8281

COWLES FOUNDATION DISCUSSION PAPER NO. 861

"A Centered Projective Algorithm"

Michael J. Todd and Yinyu Ye

February 1988

We describe a projective algorithm for linear programming that shares features with Karmarkar’s projective algorithm and its variants and with the path-following methods of Gonzaga, Kojima-Mizuno-Yoshise, Monteiro-Adler, Renegar, Vaidya and Ye. It operates in a primal-dual setting, stays close to the central trajectories, and converges in O(square root of n x L) iterations like the latter methods. (Here n is the number of variables and L the input size of the problem). However, it is motivated by seeking reductions in a suitable potential function as in projective algorithms, and the approximate centering is an automatic byproduct of our choice of potential function.

JEL Classification: 213

Keywords: Linear programming, Karmarkar’s algorithm, algorithm