Journal article
A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm
Mathematical programming, Vol.47(1-3), pp.337-351
08/01/1990
DOI: 10.1007/BF01580868
Abstract
In his original analysis of the projective algorithm for linear programming, Karmarkar proposed a "modified method" which improved the worst-case arithmetic complexity of the original algorithm by a factor of {Mathematical expression}. Karmarkar's analysis of the {Mathematical expression} improvement is based on a primal-dual formulation, and requires that small steps be taken on each iteration. However, in practice the original algorithm can be easily applied to standard form problems, and is considerably improved by performing a linesearch on each iteration, generally leading to much larger steps. We show here that by incorporating a simple safeguard, a linesearch may be performed in the modified algorithm while retaining the {Mathematical expression} complexity improvement over the original algorithm. We then show that the modified algorithm, with safeguarded linesearch, can be applied directly to a standard form linear program with unknown optimal objective value. The resulting algorithm enjoys a {Mathematical expression} complexity advantage over standard form variants of the original algorithm. © 1990 The Mathematical Programming Society, Inc.
Details
- Title: Subtitle
- A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm
- Creators
- Kurt M. Anstreicher - Yale University
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.47(1-3), pp.337-351
- DOI
- 10.1007/BF01580868
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Language
- English
- Date published
- 08/01/1990
- Academic Unit
- Business Analytics; Industrial and Systems Engineering; Computer Science
- Record Identifier
- 9984380457402771
Metrics
3 Record Views