On the finite convergence of interior-point algorithms for linear programming

It has been shown that numerous interior-point algorithms for linear programming (LP) generate solution sequences that converge to strict complementarity solutions, or interior solutions on the optimal face. This note further establishes a theoretical base for Gay’s test to identify the optimal face, and develops a new termination procedure to obtain an exact solution on the optimal face. It also reports some numerical results for solving a set of LP test problems, each of which has a highly degenerate and unbounded optimal face.