×

Large step path-following methods for linear programming. II: Potential reduction method. (English) Zbl 0754.90036

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.

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
PDFBibTeX XMLCite
Full Text: DOI