Gonzaga, Clovis C. Large step path-following methods for linear programming. II: Potential reduction method. (English) Zbl 0754.90036 SIAM J. Optim. 1, No. 2, 280-292 (1991). Summary: The algorithm proposed in this paper in the affine polynomial potential reduction method, with new procedures for updating the lower bounds for an optimal solution of the linear programming problem. A method is developed for updating the lower bounds by large steps, with strict control over the duality gaps associated with each iterate. Two algorithms are obtained by this approach: the first one has complexity \(O(nL)\) iterations, and a very simple updating procedure; the second one updates the lower bounds at points very near the central trajectory and achieves a complexity of \(O(\sqrt nL)\) iterations. Cited in 1 ReviewCited in 15 Documents MSC: 90C05 Linear programming 90-08 Computational methods for problems pertaining to operations research and mathematical programming 90C60 Abstract computational complexity for mathematical programming problems Keywords:interior point methods; Karmarkar’s algorithm; affine polynomial potential reduction method; lower bounds PDFBibTeX XMLCite \textit{C. C. Gonzaga}, SIAM J. Optim. 1, No. 2, 280--292 (1991; Zbl 0754.90036) Full Text: DOI