Gonzaga, Clovis C. Large step path-following methods for linear programming. I: Barrier function method. (English) Zbl 0754.90035 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\). Cited in 19 Documents 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 × Cite Format Result Cite Review PDF Full Text: DOI