A Cubically Convergent Method for Locating a Nearby Vertex in Linear Programming
RICE UNIV HOUSTON TX DEPT OF MATHEMATICAL SCIENCES
Pagination or Media Count:
Given a point sufficiently close to a nondegenerate basic feasible solution x of a linear program, we show how to generate a sequence p-superscript-k that converges to the 0-1 vector signx at a Q-cubic rate. This extremely fast convergence enables us to determine, with a high degree of certainty, which variables will be zero and which will be nonzero at optimality and then construct x from this information.
- Operations Research