PARAMETER α VERSUS NUMBER OF ITERATIONS IN KARMARKAR'S ALGORITHM FOR LP

摘要

Karmarkar's projective transformation algorithm for solving a linear program (LP) is the first polynomial time algorithm which was published in 1984. This algorithm implemented in Mathematica in this article has used a real parameter 0 < α < 1 whose value affects its convergence. That is, for different values of α, the number of iterations required to obtain a desired accuracy will be different. We study here if, for a given LP, there is an optimal a for which the number of iterations will be minimum subject to the precision of the computer. Also we investigate how α behaves from one LP to another.