Boundary behavior of interior point algorithms in linear programming

Abstract

This paper studies the boundary behavior of some interior point algorithms for linear programming. The algorithms considered are Karmarkar's projective rescaling algorithm, the linear rescaling algorithm which was proposed as a variation on Karmarkar's algorithm, and the logarithmic barrier technique. The study includes both the continuous trajetories of the vector fields induced by these algorithms and also the discrete orbits. It is shown that, although the algorithms are defined on the interior of the feasible polyhedron, they actually determine differentiable vector fields on the closed polyhedron. Conditions are given under which a vector field gives rise to trajectories that each visit the neighborhoods of all the vertices of the Klee-Minty cube. The linear rescaling algorithm satisfies these conditions.