The Ellipsoid Method

Every airline schedule, every factory production plan, every portfolio allocation — at their mathematical core they are all linear programs: maximize (or minimize) a linear objective subject to linear constraints. The simplex method had been solving these in practice since the 1940s, and it was blazingly fast. But nobody could prove it was theoretically efficient. In the worst case, simplex visits exponentially many vertices.

For decades the question sat open: is linear programming (LP) in P — solvable in polynomial time? Then in 1979 a Soviet mathematician, Leonid Khachiyan, answered yes, using an idea borrowed from geometry. Instead of walking along the edges of a polytope the way simplex does, his algorithm wraps an ellipsoid around the feasible region and shrinks it, step by step, until it collapses onto a solution.

The algorithm was slower than simplex in every practical test, but that was beside the point. It settled a fundamental theoretical question: LP is in P. And the ideas it introduced — separation oracles, volumetric arguments, and solving problems implicitly — went on to shape modern optimization.

The demo below runs the ellipsoid algorithm on a small 2D linear program. The blue region is the feasible polytope — the set of points satisfying all constraints. The algorithm starts with a large ellipse guaranteed to contain the optimum and, at each step, cuts the ellipse in half with the most-violated constraint, then replaces it with the smallest ellipse containing the surviving half.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="340" height="280"></canvas>
<div class="info" id="info">{{press_to_start_html}}</div>
<div class="btns">
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnRun"  type="button">{{btn_run}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
         background: #f8fafc; max-width: 100%; }
.info  { font-size: .9rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.info.done { color: #0a7d33; }
.btns  { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice two things. First, the ellipse always contains at least one optimal point — the algorithm never misses the target. Second, each iteration shrinks the volume by a fixed factor, so after polynomially many steps the ellipse is too small to hold anything except (approximately) the optimum. The red dot marks the current center; when it lands inside the feasible region it becomes the candidate solution.

What did Khachiyan actually prove, and why does it matter?

• LP is in P. The ellipsoid method runs in time polynomial in the number of variables, constraints, and the bit-length of the input — specifically $O(n^{6} L^{2})$ bit operations, where n is the number of variables and L is the encoding length. This is the first polynomial-time LP algorithm.
• Volume shrinks by a constant factor each step. The key lemma: when you cut an ellipsoid in half with a hyperplane and take the smallest enclosing ellipsoid of the surviving half, its volume drops by a factor of at least $e^{-1/2n}$. After $O(n^{2} L)$ iterations, the ellipse is too small to contain a feasible point of any meaningful size.
• Separation oracle model. The method only needs to test whether a point is feasible (and if not, find a violated constraint). This abstraction let it solve problems with exponentially many constraints efficiently — as long as violations can be found quickly.
• Slower than simplex in practice. Despite its theoretical superiority, the ellipsoid method is rarely used directly. The constant factors are large and the algorithm is numerically sensitive. It was superseded by interior-point methods (Karmarkar, 1984), which are both polynomial and fast in practice.
• Theoretical legacy. The ellipsoid method remains central to complexity theory. It proves linear programming is in P, solves problems in combinatorial optimization (like the ellipsoid-plus-separation-oracle approach for max-weight matching), and shows that many problems previously thought hard are actually polynomial.

The ellipsoid method's theoretical influence extends far beyond linear programs:

• Combinatorial optimization: problems with exponentially many constraints (like the max-weight perfect matching polytope or the stable-set polytope of perfect graphs) can be solved in polynomial time whenever a separation oracle exists — even though you could never list all the constraints explicitly.
• Semidefinite programming (SDP): SDPs generalize LP by replacing linear inequalities with matrix positive-semidefiniteness. The ellipsoid method (and its successor, interior-point SDP solvers) made SDP tractable and powered decades of advances in approximation algorithms.
• Game theory: the ellipsoid method can compute Nash equilibria in zero-sum games and other structured games in polynomial time, connecting optimization to Nash equilibrium theory.
• Separation = optimization: the deep insight is that for convex problems, testing feasibility and optimizing are equivalent in polynomial time. If you can separate, you can optimize. This principle drives modern convex optimization.
• Interior-point methods: Karmarkar's 1984 algorithm shares the ellipsoid method's polynomial guarantee but is practical. Today's commercial LP solvers use interior-point methods for large instances — the direct descendant of Khachiyan's theoretical breakthrough.

The ellipsoid method answered a question that had haunted optimization for decades: linear programming is in P. It did so by replacing the combinatorial edge-walking of simplex with a purely geometric idea — shrink an ellipsoid by a fixed volumetric factor at every step, and after polynomially many steps nothing remains except the answer.

In practice, engineers kept using simplex (and later Karmarkar's interior-point method). But in theory, the ellipsoid method was a watershed: it introduced the separation oracle model, showed that optimization and feasibility testing are equivalent for convex problems, and planted the seeds for semidefinite programming and a generation of approximation algorithms.

Sometimes the best proof is not the fastest algorithm, but the one that finally shows something is possible at all. For LP, that proof was an ellipsoid, shrinking.