PRIMAL DUAL ALGORITHMS FOR LINEAR-PROGRAMMING BASED ON THE LOGARITHMIC BARRIER METHOD

In this paper, we deal with primal-dual interior point methods for sol ving the linear programming problem. We present a short-step and a lon g-step path-following primal-dual method and derive polynomial-time bo unds for both methods. The iteration bounds are as usual in the existi ng literature, namely O(square-root nL) iterations for the short-step variant and O(nL) for the long-step variant. In the analysis of both v ariants, we use a new proximity measure, which is closely related to t he Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual s earch directions form a descent direction for the so-called primal-dua l logarithmic barrier function.