PRIMAL-DUAL METHODS FOR LINEAR-PROGRAMMING

Many interior-point methods for linear programming are based on the pr operties or the logarithmic barrier function, After a preliminary disc ussion of the convergence of the (primal) projected Newton barrier met hod, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal-dual, and may be derived from t he application of Newton's method to different variants of the same sy stem of nonlinear equations. A fourth variant of the same equations le ads to a new primal-dual method. In each of the methods discussed, con vergence is demonstrated without the need for a nondegeneracy assumpti on or a transformation that makes the provision of a feasible point tr ivial. In particular, convergence is established for a primal-dual alg orithm that allows a different step in the primal and dual variables a nd does not require primal and dual feasibility. Finally, a new method for treating free variables is proposed.