New complexity results for the Iri-Imai method

DOI10.1007/BF02206829zbMath0848.90091MaRDI QIDQ1915925

Shu-Zhong Zhang, Jos F. Sturm

Publication date: 24 October 1996

Published in: Annals of Operations Research (Search for Journal in Brave)

zbMATH Keywords

primal-dual potential function; Iri-Imai algorithm

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C05: Linear programming

Related Items

An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming, Value estimation approach to the Iri-Imai method for constrained convex optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• A multiplicative barrier function method for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• Interior point algorithms for linear programming with inequality constraints
• A combined phase I-phase II scaled potential algorithm for linear programming
• A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start
• A proof of the polynomiality of the Iri-Imai method
• Convergence property of the Iri-Imai algorithm for some smooth convex programming problems
• Polynomial affine algorithms for linear programming
• Potential reduction method for harmonically convex programming
• A Centered Projective Algorithm for Linear Programming
• Path-Following Methods for Linear Programming