How did Leonid Khachiyan’s ellipsoid method differ from the simplex method?

Leonid Khachiyan’s ellipsoid method differed from the simplex method primarily in its computational complexity and practical efficiency.

The simplex method, developed by George Dantzig, operates by moving between extreme points of a feasible region to find an optimal solution. While it is highly efficient in practice, its theoretical worst-case performance can grow exponentially with the number of variables.12

In 1979, Khachiyan introduced the ellipsoid method, which was the first polynomial-time algorithm for linear programming. This means the number of computational steps required grows as a power of the number of variables rather than exponentially, theoretically allowing for the solution of problems that were previously inaccessible.1

Despite this theoretical advantage, the ellipsoid method proved to be slower than the simplex method when applied to practical, real-world problems. It was not until the 1984 discovery of the interior point method by Narendra Karmarkar that a polynomial-time algorithm became truly competitive with the simplex method in practice.1