Cubically convergent method for locating a nearby vertex in linear programming

Given a point sufficiently close to a nondegenerate basic feasible solutionx* of a linear program, we show how to generate a sequence {p ^k} that converges to the 0–1 vector sign(x*) at aQ-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 constructx* from this information.This research was supported in part by NSF Cooperative Agreement No. CCR-8809615, by AFOSR Grant No. 89-0363, and by DOE Grant No. DEFG05-86ER 25017. The authors would like to thank Bob Bixby for helpful discussions.