Document Type
Discussion Paper
Publication Date
2-1-1988
CFDP Number
861
CFDP Pages
40
Abstract
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 ( /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.
Recommended Citation
Todd, Michael J. and Ye, Yinyu, "A Centered Projective Algorithm for Linear Programming" (1988). Cowles Foundation Discussion Papers. 1104.
https://elischolar.library.yale.edu/cowles-discussion-paper-series/1104