Polynomiality of infeasible-interior-point algorithms for linear programming
type: Item
instance of: scholarly article
title: Polynomiality of infeasible-interior-point algorithms for linear programming
zbMATH Open document ID: 0828.90086
DOI: 10.1007/BF01582216
author: Shinji Mizuno
published in: Mathematical Programming. Series A. Series B
publication date: 1994-12-11T00:00:00Z
review text: An infeasible interior point algorithm for solving a primal-dual pair of linear programming problems finds approximate optimal solutions of the pair if both problems have interior points and detects infeasibility when the sequence of iterates diverges. Polynomial-time convergence of this algorithm under the assumption that both primal and dual problems have feasible points are proved. The author shows that a modification of the infeasible interior point algorithm ``solves'' the pair of problems in polynomial time, without assuming the existence of the LP solution. Furthermore, he develops an \(O(nL)\)-iteration complexity result for a variant of the algorithm.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 700817
zbMATH Keywords: infeasible interior point algorithm
zbMATH Keywords: primal-dual pair of linear programming problems
reviewed by: Maxim Ivanov Todorov
MaRDI profile type: Publication
cites work: A primal-dual infeasible-interior-point algorithm for linear programming
cites work: Q3491304
cites work: A polynomial-time algorithm for a class of linear complementarity problems
cites work: Feasibility issues in a primal-dual interior-point method for linear programming
cites work: Computational experience with a primal-dual interior point method for linear programming
cites work: Q4206561
cites work: On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
cites work: Interior path following primal-dual algorithms. I: Linear programming
cites work: Interior path following primal-dual algorithms. II: Convex quadratic programming
cites work: An Infeasible-Interior-Point Predictor-Corrector Algorithm for Linear Programming
cites work: Q3804467
cites work: On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
full work available at URL: https://doi.org/10.1007/bf01582216
OpenAlex ID: W1985332751
description: scientific article; zbMATH DE number 700817