Combining phase I and phase II in a potential reduction algorithm for linear programming

This paper describes an affine potential reduction algorithm for linear programming that simultaneously seeks feasibility and optimality. The algorithm is closely related to a similar method of Anstreicher. The new features are that the paper uses a two-dimensional programming problem to derive better lower bounds than Anstreicher, that the present direction-finding subproblem treats phase I and phase II more symmetrically, and that it does not need an initial lower bound. The method also allows for the generation of a feasible solution (so that phase I is terminated) during the course of the iterations, and the paper describes two ways to encourage this behavior.