Path-Following Methods for Linear Programming

Abstract

In this paper a unified treatment of algorithms is described for linear programming methods based on the central path. This path is a curve along which the cost decreases, and that stays always far from the boundary of the feasible set. Several parameterizations of this curve are described in primal and primal-dual problems, and it is shown how different algorithms are obtained by following the curve using different parameterizations. Polynomial algorithms are obtained by following the curve approximately, and this concept becomes precise by using explicit rules for measuring the proximity of a point in relation to the central path.