Primal-Dual Algorithms for Linear Programming Based on the Logarithmic BarrierMethod

摘要

Primal-dual interior point methods for solving the linear programming problem areaddressed. A short step and a long step path following primal-dual method is presented and polynomial time bounds for both methods are derived. The iteration bounds are as usual in the existing literature, namely O((the square root of n)(L)) iterations for the short step, and O(nL) for the long step variant. In the analysis of both variants, a proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors is used. The analysis of the long step method strongly depends on the fact that the (usual) search directions form a descent direction for the so called primal-dual logarithmic barrier function.