Theoretical convergence of large-step primal-dual interior point algorithms for linear programming
From MaRDI portal
Publication:2366605
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
global convergencepolynomial-time computational complexitygeneric primal-dual interior point methodlarge steps
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
