Long Steps with the Logarithmic Penalty Barrier Function in Linear Programming

摘要

The paper proposes a polynomial implementation of the classical logarithmic barrier function approach. A series of long steps are taken between successive reductions of the penalty parameter. The long steps aim at getting back to the vicinity of the trajectory of centers. The algorithm requires at most O(nL) iterations. (Copyright (c) 1989 by Faculty of Technical Mathematics and Informatics, Delft, The Netherlands.)