| Boundary Behavior Of Interior Point Algorithms In Linear Programming (1986) | |||||||||||||||
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 trajectories 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. Thus, limits of such trajectories, obtained when a starting point is pushed to the boundary, may have an exponential number of breakpoints. It is shown that limits of projecti... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||