Theoretical convergence of large-step primal-dual interior point algorithms for linear programming

DOI10.1007/BF01581234zbMath0780.90063OpenAlexW1992241390MaRDI QIDQ2366605

Shinji Mizuno, Nimrod Megiddo, Kojima, Masakazu

Publication date: 30 August 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581234

zbMATH Keywords

global convergencepolynomial-time computational complexitygeneric primal-dual interior point methodlarge steps

Mathematics Subject Classification ID

Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A globally convergent primal-dual interior point algorithm for convex programming, Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems, Primal-dual methods for linear programming, Regularization techniques in interior point methods, A quadratically convergent polynomial long-step algorithm for A class of nonlinear monotone complementarity problems^*, A Primal-dual affine scaling algorithm with necessary centering as a safeguard, A little theorem of the big \({\mathcal M}\) in interior point algorithms, Convergence behavior of interior-point algorithms, Long-step interior-point algorithms for a class of variational inequalities with monotone operators, Solving quadratically constrained convex optimization problems with an interior-point method, Degeneracy in interior point methods for linear programming: A survey, On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP, On the convergence of a predictor-corrector variant algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A modification of Karmarkar's linear programming algorithm
• Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• A polynomial-time algorithm for a class of linear complementarity problems
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• An interior point potential reduction algorithm for the linear complementarity problem
• Near boundary behavior of primal-dual potential reduction algorithms for linear programming
• An implementation of Karmarkar's algorithm for linear programming
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
• AN O(n^3L) ALGORITHM USING A SEQUENCE FOR A LINEAR COMPLEMENTARITY PROBLEM
• A Centered Projective Algorithm for Linear Programming
• PRACTICAL POLYNOMIAL TIME ALGORITHMS FOR LINEAR COMPLEMENTARITY PROBLEMS
• Homotopy Continuation Methods for Nonlinear Complementarity Problems
• On the Implementation of a Primal-Dual Interior Point Method
• A Polynomial-Time Predictor-Corrector Algorithm for a Class of Linear Complementarity Problems
• Algorithmic Enhancements to the Method of Centers for Linear Programming Problems
• On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
• An Implementation of a Primal-Dual Interior Point Method for Linear Programming
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• On the Superlinear Convergence of Interior-Point Algorithms for a General Class of Problems