Long steps with the logarithmic penalty barrier function in linear programming. (English) Zbl 0709.90076

Roos, Cornelis; Vial, Jean-Philippe

Economic decision-making: games, econometrics and optimization, Contrib. in Honour of J. H. Drèze, 433-441 (1990).

[For the entire collection see Zbl 0707.00031.]
This paper deals with a polynomial implementation of the classical logarithmic barrier function approach, applied to the linear programming problem. 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, where \(n\) denotes dimension of the decision vector and \(L\) the size of the problem.

Reviewer: Cornelis Roos

MSC:

90C05	Linear programming
90-08	Computational methods for problems pertaining to operations research and mathematical programming
49M30	Other numerical methods in calculus of variations (MSC2010)
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

logarithmic barrier function; long steps

Citations:

Zbl 0707.00031