On the Performance of Karmarkar’s Algorithm over a Sequence of Iterations
Author:
- Kurt M. AnstreicherKAKurt M. Anstreicher
- 1 February 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 1 (1) , 22-29
Abstract
Karmarkar’s projective algorithm for linear programming is considered with real arithmetic and exact linesearch of the potential function. It is shown that for every $n\geqq 3$ there is a linear program, with n variables, such that the algorithm obtains a potential reduction of about 1.3 on each iteration. For the same problems the algorithm requires $\Theta (\ln (n/\varepsilon ))$ iterations to reduce the objective gap to a factor $\varepsilon $ of its initial value. It is thus proved that in the worst case the convergence of Karmarkar’s algorithm, with exact linesearch, cannot be independent of n, and moreover, potential reduction may be a poor indicator of algorithm performance.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Karmarkar's linear programming algorithm and Newton's methodMathematical Programming, 1991
- Asymptotic behaviour of Karmarkar's method for linear programmingMathematical Programming, 1990
- On the improvement per iteration in Karmarkar's algorithm for linear programmingMathematical Programming, 1990
- The Worst-Case Step in Karmarkar's AlgorithmMathematics of Operations Research, 1989
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984