Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs

DOI10.1007/BF02206809zbMath0848.90084OpenAlexW2053624310WikidataQ124828843 ScholiaQ124828843MaRDI QIDQ1915903

Kojima, Masakazu

Publication date: 6 November 1996

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

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

zbMATH Keywords

step lengthsinitial pointsprimal-dual infeasible-interior-point algorithmnonlinear monotone complementaritypolynomial-time computational complexity

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items (7)

A predictor-corrector infeasible-interior-point algorithm for linear programming ⋮ An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming ⋮ An infeasible-interior-point algorithm using projections onto a convex set ⋮ Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming ⋮ Two new predictor-corrector algorithms for second-order cone programming ⋮ The complexity of self-regular proximity based infeasible IPMs ⋮ Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A little theorem of the big \({\mathcal M}\) in interior point algorithms
• Feasibility issues in a primal-dual interior-point method for linear programming
• Computational experience with a primal-dual interior point method for linear programming
• Interior path following primal-dual algorithms. I: Linear 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
• A primal-dual infeasible-interior-point algorithm for linear programming
• Global convergence in infeasible-interior-point algorithms
• Superlinear convergence of infeasible-interior-point methods for linear programming
• Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming
• Polynomiality of infeasible-interior-point algorithms for linear programming
• A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points
• An Extension of Karmarkar Type Algorithm to a Class of Convex Separable Programming Problems with Global Linear Rate of Convergence
• On the Implementation of a Primal-Dual Interior Point Method
• On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
• Infeasible-Interior-Point Primal-Dual Potential-Reduction Algorithms for Linear Programming
• A Surface of Analytic Centers and Primal-Dual Infeasible-Interior-Point Algorithms for Linear Programming

This page was built for publication: Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs