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 Netwon 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.