Large step path-following methods for linear programming. I: Barrier function method. (English) Zbl 0754.90035

Gonzaga, Clovis C.

SIAM J. Optim. 1, No. 2, 268-279 (1991).

Summary: The algorithm proposed in this paper is the classical logarithmic barrier function method with Newton-Raphson steps for the internal minimization of the penalized function. Polynomial behavior is obtained by stopping each internal cycle when the iterates approach the central trajectory. Each master iteration updates the penalty parameter by a constant factor, and the overall complexity bound depends on this factor: \(O(nL)\) Newton iterations for an arbitrary constant, and \(O(\sqrt nL)\) iterations for a constant dependent on \(\sqrt n\).

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)

Keywords:

interior point methods; path following methods; logarithmic barrier function; Newton-Raphson steps