Primal-Dual Methods for Linear Programming
Many interior-point methods for linear programming are based on the
properties of the logarithmic barrier function. After a preliminary
discussion of the convergence of the (primal) projected Newton barrier
method, three types of barrier method are analyzed. These methods may
be categorized as primal, dual and primal-dual, and may be derived
from the application of Newton's method to different variants of the
same system of nonlinear equations. A fourth variant of the same
equations leads to a new primal-dual method.
In each of the methods discussed, convergence is demonstrated without the need
for a nondegeneracy assumption or a transformation that makes the provision of
a feasible point trivial. In particular, convergence is established for a
primal-dual algorithm that allows a different step in the primal and dual
variables and does not require primal and dual feasibility.
Finally, a new method for treating free variables is proposed.