A Centered Projective Algorithm for Linear Programming
Michael J. Todd, Yinyu Ye · Mathematics of Operations Research · 1990
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 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.
Cited by 152 works. doi:10.1287/moor.15.3.508
Authors
References
- A new polynomial-time algorithm for linear programming
- Nonlinear Programming: Sequential Unconstrained Minimization Techniques
- A Primal-Dual Interior Point Algorithm for Linear Programming
- Pathways to the Optimal Set in Linear Programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Interior path following primal-dual algorithms. part I: Linear programming
- An "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming
- An implementation of Karmarkar's algorithm for linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- An extension of Karmarkar's algorithm for linear programming using dual variables