Karmarkar's algorithm and the ellipsoid method (Q1095025): Difference between revisions

We show that Karmarkar's algorithm and the ellipsoid method are closely related. At each iteration, the potential function used to measure convergence of the primal solutions in Karmarkar's algorithm correctly characterizes the logarithmic volume of an ellipsoid that contains all of the optimal dual solutions. As the potential function declines, the volume of the ellipsoid monotonicly shrinks to zero. These ellipsoids can be used to determine the optimal basis for linear programming. Conversely, the relation of these two algorithms may lead to an efficient implementation for the ellipsoid method.