Primal-Dual Methods for Linear Programming

Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. We first give a convergence proof for the primal projected Newton barrier method. We then analyze three types of barrier method that can be categorized as primal, dual and primal-dual. All three approaches may be derived from the application of Newtons method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal-dual algorithm. In each of the methods discussed, covergence is demonstrated without the need for a nondegeneracy assumption. In particular, convergence is established for a primal-dual algorithm that allows a different step in the primal and dual variables. Finally, we describe a new method for treating free variables.