A potential-reduction variant of Renegar's short-step path-following method for linear programming

DOI10.1016/0024-3795(91)90266-YzbMath0734.65050WikidataQ114852085 ScholiaQ114852085MaRDI QIDQ811094

Tamás Terlaky, Dick den Hertog, Cornelis Roos

Publication date: 1991

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

linear programmingiteration boundline searchNewton directionlarge-step pathfollowing methodpolynomial potential-reduction method

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items

Convergence property of the Iri-Imai algorithm for some smooth convex programming problems, Linear programming with entropic perturbation, A cutting plane algorithm for convex programming that uses analytic centers, Adaptive constraint reduction for convex quadratic programming, A survey of search directions in interior point methods for linear programming, Maintaining closeness to the analytic center of a polytope by perturbing added hyperplanes, Degeneracy in interior point methods for linear programming: A survey, Pivot rules for linear programming: A survey on recent theoretical developments, Differential-algebraic approach to linear programming, On the classical logarithmic barrier function method for a class of smooth convex programming problems

Cites Work

• A new polynomial-time algorithm for linear programming
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A survey of search directions in interior point methods for linear programming
• Large Step Path-Following Methods for Linear Programming, Part I: Barrier Function Method
• Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method
• Unnamed Item
• Unnamed Item