ISSN:
1436-4646
Keywords:
Linear programming
;
Karmarkar's algorithm
;
projective algorithm
;
modified method
;
standard form
;
rank-one updates
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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 $$\sqrt n $$ . Karmarkar's analysis of the $$\sqrt n $$ 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 $$\sqrt n $$ 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 $$\sqrt n $$ complexity advantage over standard form variants of the original algorithm.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01580868
Permalink
