Convergence Analysis of Inexact Infeasible-Interior-Point Algorithms for Solving Linear Programming Problems
Author:
- Janos KorzakJKJanos Korzak
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 11 (1) , 133-148
Abstract
In this paper we present a convergence analysis for some inexact (polynomial) variants of the infeasible-interior-point algorithm of Kojima, Megiddo, and Mizuno. For this analysis we assume that the iterates are bounded. The new variants allow the use of search directions that are calculated from the defining linear system with only moderate accuracy, e.g., via the use of Krylov subspace methods like CG or QMR. Furthermore, some numerical results for the proposed methods are given.Keywords
This publication has 8 references indexed in Scilit:
- The role of linear objective functions in barrier methodsMathematical Programming, 1999
- Convergence of a Class of Inexact Interior-Point Algorithms for Linear ProgramsMathematics of Operations Research, 1999
- An infeasible-interior-point algorithm using projections onto a convex setAnnals of Operations Research, 1996
- Computational experience with a globally convergent primal—dual predictor—corrector algorithm for linear programmingMathematical Programming, 1994
- A primal—dual infeasible-interior-point algorithm for linear programmingMathematical Programming, 1993
- On the Implementation of a Primal-Dual Interior Point MethodSIAM Journal on Optimization, 1992
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear ProgrammingSIAM Journal on Optimization, 1992
- A Characterization of Stability in Linear ProgrammingOperations Research, 1977