Centered Projective Algorithm for Linear Programming

摘要

We describe a projective algorithm for linear programming that shares featureswith Karmarkar's projective algorithm and its variants and with the path-following methods of Gonzaga, Kojima-Mizuno-Uoshise, Monteiro-Adler, Renegar, Vaidva and Ye. It operates in a primal-dual setting, stays close to the central trajectories, and converges in square root of nL 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 byproduce of our choice of potential function. Keywords: Reprints. (kr) (Author)