Journal article
ON THE PERFORMANCE OF KARMARKAR'S ALGORITHM OVER A SEQUENCE OF ITERATIONS
SIAM journal on optimization, Vol.1(1), pp.22-29
02/01/1991
DOI: 10.1137/0801003
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 >= 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/epsilon)) iterations to reduce the objective gap to a factor epsilon 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.
Details
- Title: Subtitle
- ON THE PERFORMANCE OF KARMARKAR'S ALGORITHM OVER A SEQUENCE OF ITERATIONS
- Creators
- Kurt M. Anstreicher - Yale University
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.1(1), pp.22-29
- Publisher
- Siam Publications
- DOI
- 10.1137/0801003
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Number of pages
- 8
- Language
- English
- Date published
- 02/01/1991
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380486002771
Metrics
7 Record Views