Docs / Ellipsoid

The ellipsoid method

The ellipsoid method never looks for a good point. It keeps a set that provably still contains the optimum, asks one question about the point in the middle of it, and throws away the half of the set that the answer rules out. In lpviz that set is drawn on the canvas, so you can watch the search space itself collapse onto the answer.

The idea

lpviz solves maximize cᵀx s.t. Ax ≤ b. The ellipsoid method attacks it with a localizing set E and a separation oracle:

• E is maintained as an invariant: it contains every feasible point at least as good as the incumbent (the best feasible point found so far). At the start E is big enough to contain the whole drawn region, so the invariant holds trivially.
• The oracle is asked about one point — the center x_k of E. It answers with a separating hyperplane: a half-space known to contain everything worth keeping, and to exclude the center.
• E is replaced by the minimum-volume ellipsoid containing E ∩ (that half-space). The invariant survives, and the volume shrinks by a fixed factor.

Nothing here needs the objective to be linear, or the constraints to be few; the method only needs to be able to cut. That generality is why the ellipsoid method matters historically: Khachiyan used it in 1979 to prove that linear programming is solvable in polynomial time, the first such proof, and it remains the standard tool for showing that an optimization problem is tractable whenever you can separate over it.

It is also famously not competitive in practice, and lpviz shows you why: the volume guarantee is worst-case, dimension-driven, and completely indifferent to how easy your particular polygon is. Simplex would finish this drawing in a handful of pivots.

What one iteration does

The ellipsoid is stored as a center x_k and a symmetric shape matrix P, meaning E = { x : (x − x_k)ᵀP⁻¹(x − x_k) ≤ 1 }. Each iteration:

1. Ask the oracle. Find the constraint the center violates most. If there is one, that constraint is the cut — everything feasible lies on its far side. This is a feasibility cut.
2. Otherwise cut with the objective. A feasible center is a new incumbent, so every point with cᵀx ≤ (incumbent value) can be discarded: they cannot beat what is already in hand. This is the sliding objective variant — the objective cut slides upward as the incumbent improves.
3. Update. Replace E by the minimum-volume ellipsoid containing the retained piece. In two variables that costs a handful of arithmetic operations; there is no linear system to solve.

The update has a closed form that is worth internalizing, because it explains the shape of everything you see. For a cut through the center in n = 2 variables, the new ellipse has semi-axis ²⁄₃ along the cut normal and ²⁄_√3 ≈ 1.155 across it. The area falls to about 77% — but the axis across the cut grows by 15%. Successive ellipses therefore do not nest; they become longer and thinner, tilted away from the cut just made. That elongation rotates the direction of the next cut, and the rotation is what makes the path spiral.

ρ, and how a run stops

The reported convergence measure is

ρ = √( cᵀPc )

the ellipsoid's half-width in the objective direction: how much objective value could still be hiding inside it. Because the ellipsoid contains the optimum, cᵀx_k + ρ is a genuine upper bound on the optimal value, while the incumbent is a lower bound. lpviz stops when the two brackets close:

cᵀx_k + ρ − (incumbent) ≤ 10⁻⁵ · (1 + |incumbent|)

and the center is itself feasible, so that the point marked as the answer really is a point of your region. This certificate is sharper than ρ alone and closes sooner. Two other endings deserve a mention, and the log names them: the cuts can consume the entire ellipsoid, which means nothing better than the incumbent remains and the incumbent is optimal; or the method can converge to a point sitting on the boundary of the initial ellipsoid, which means the objective is unbounded over your region and the answer is an artifact of where the search was fenced in. lpviz says so explicitly rather than reporting a number.

In the 3D view the path is lifted to cᵀx_k + ρ — the certified upper bound — so the trajectory visibly descends onto the objective plane as the bound tightens, instead of climbing it the way the other solvers' paths do.

The controls

Deep cuts greys out unless the query point is Ellipsoid: it describes how the ellipsoid update reshapes itself, and the other three query points never build an ellipsoid to reshape. Their cuts are already as deep as the oracle can make them, since a polyhedron can simply store the violated constraint itself. Ray shoot applies to all four.

Initial ellipsoid size

This is the most counter-intuitive control on the panel, because it looks like a speed control and is not one. The ellipsoid method's guarantee is that volume falls by a constant factor per iteration, so the number of iterations needed depends on the logarithm of the initial volume. Starting 16× tighter buys you about ten iterations — once, at the beginning. Cut depth, by contrast, multiplies: it changes the factor itself, and therefore every iteration after it.

Treat it as a framing control. Small values put the whole picture on screen at once and make the early ellipses easy to compare with the region; large values are useful for watching the method spend its first iterations doing nothing but discovering where your region is. On an unbounded region the setting matters in a different way: it is the fence that keeps the search finite, and a point that converges onto it is what lpviz reports as unboundedness.

Deep cuts

A cut only has to exclude the center to guarantee progress, and the textbook method asks for nothing more. But the oracle usually knows more than that. When the center violates constraint i, the whole slab between the center and that constraint is infeasible too, so the plane can be moved out to the constraint itself. When the center is feasible and the incumbent is already better than it, the objective cut can be raised to the incumbent's level. Both are free: no extra work, no risk of losing the optimum.

The payoff compounds, because cut depth changes the shrink factor rather than the starting volume. On a square region the same solve takes 72 iterations with deep cuts and 97 without. Turning them off is the way to see the classical, pessimistic version of the algorithm — and to watch the ellipse take the full lazy 0.77 step every single iteration.

Ray shoot

When the center lands inside the region, the objective cut through it discards only the points worse than the center. But from a feasible point you can do better for free: slide along c until a constraint blocks the way, and that boundary point is feasible and strictly better. Adopting it as the incumbent moves the objective cut out to the shaded line, discarding the whole band in between.

It is worth 1.65 to 2.4× fewer iterations on the regions in lpviz's preset gallery, which is why it is on by default. It also changes what the final answer looks like: the incumbent is usually a point on the boundary rather than any ellipsoid center, so the last row of the log — the point lpviz marks as the answer — is not the last point the method queried. That row is appended deliberately; without it the marker would sit on a query point that merely happened to be last.

Query point

This is the setting that changes the algorithm rather than tuning it. The ellipsoid method's defining move is to query the center of a covering ellipsoid, which is a crude proxy for "deep inside the region still under consideration". It is crude because an ellipsoid is a lossy summary: after a few cuts, the real region under consideration is a polyhedron, and the ellipsoid drawn around it can be far larger and shaped quite differently.

The other three settings keep the polyhedron. They accumulate cuts exactly as before — same oracle, same incumbent handling, same ray shoot, same initial bounding box — and differ only in which interior point of it they ask about next.

Ellipsoid

The method proper. The query point is the center of the covering ellipsoid, and is a function of the ellipsoid's own history rather than of the polyhedron.

Chebyshev

The center of the largest ball that fits inside the polyhedron, computed as one small LP. Fast and robust on round regions; the worst of the three on slivers, for the obvious reason that a ball is a poor model of a thin region and its center can be pushed nearly anywhere along the sliver's length.

Analytic

The ACCPM point: the minimizer of the log barrier −Σ log(b_i − a_iᵀx), found by damped Newton. Unlike a ball, the barrier sees the shape of the set, so the point adapts to anisotropy — the same object that governs the central path, used here as a notion of "middle" rather than as a path to follow.

Volumetric

Vaidya's point: the minimizer of ½ log det H(x), where H is the barrier Hessian. It weights each face by its leverage score, so nearly-redundant cuts stop dragging the query point around. It also drops cuts whose leverage falls below a threshold, which is what keeps the constraint count — and the per-iteration cost — bounded as the run goes on. Dropping a cut only ever enlarges the localizing set, so it can never lose the optimum.

Mean iterations to a 10⁻⁶ gap, averaged over 12 objective directions:

Two things stand out. The ellipsoid method costs three to five times as many iterations as any of the polyhedral query points — the price of summarizing the localizing set by an ellipsoid. And Chebyshev, the cheapest and generally the fastest, is the one that falls apart on Needle: 16.1 iterations against 11.5 for the two barrier-based points, which barely notice the geometry. That is the whole argument for analytic and volumetric centers in one row of a table.

Why the ellipsoid method spirals

Run the ellipsoid method on a pentagon and the path visibly winds: measured over 53 steps, the mean turn is 120° per step with zero turn-direction reversals — not a wobble but a clean precession. The mechanism is the update formula. Each minimum-volume ellipsoid is elongated perpendicular to the cut just made, so the next cut, chosen against that elongated shape, points in a rotated direction; near the optimum the method settles into a cycle of objective cut → active constraint A → active constraint B, three cuts about 120° apart, forever tightening. The other three query points show nothing of the sort: their turn angles decay and their direction alternates, because the point they query is defined by the polyhedron itself and not by an ellipsoid carrying the memory of the last cut.

The spiral is worth watching with Trace on. It is the clearest picture in lpviz of a method that is provably converging and visibly wasteful at the same time.

What the drawn ellipse means

lpviz draws an ellipse for every iterate of this mode, and the ellipse means opposite things depending on the query point. Users notice this, usually as a suspected bug, so it is worth stating plainly:

• Ellipsoid: the ellipse is the localizing set — a covering ellipsoid. Everything still under consideration is inside it, and successive centers are therefore always inside it too.
• Chebyshev, analytic, volumetric: the ellipse is inscribed at the query point — the Dikin ellipsoid of the barrier there, or Chebyshev's inscribed ball. It is a local measure of elbow room, not a bound on anything, so the next query point routinely lands outside it. That is expected.

For those three the region actually under consideration is the polyhedron of accumulated cuts, and lpviz will draw it: hover a row in the iteration log (or scrub the replay) and its localizing polyhedron appears as a thin outline. It is drawn one at a time on purpose — they nest, they are many-sided, and unlike the ellipses they do not shrink smoothly, so drawing them all at once buries the picture. The invariant that does hold, and that hovering successive rows makes visible, is that the polyhedron only ever shrinks.

Reading the log

 Iter        x        y        Obj     Infeas          ρ
    1     0.50     0.50    1.4e+0    2.1e+0    1.1e+1
    2     4.83    -1.24    4.1e+0    0.0e+0    6.2e+0

• x, y: the point queried this iteration — the ellipsoid center, or the polyhedron's Chebyshev/analytic/volumetric center.
• Obj: its objective value. It does not increase monotonically: the query point is chosen for its position in the localizing set, not for its objective, and it is often infeasible.
• Infeas: the largest constraint violation at that point, which is zero exactly when the oracle returned an objective cut instead of a feasibility cut.
• ρ: the objective half-width of the localizing set — how much better than the current point anything still under consideration could be. This is the number that has to reach zero.
• The final row is the incumbent, the point actually returned. With the ray shoot on it is usually a boundary point that no iteration queried.

Behavior to watch for

• The set is the story. Every other solver in lpviz draws a sequence of points that approach the answer. This one draws a sequence of regions that contain it. Watching an ellipse that still contains the optimum shrink around it is a different mental model of "solving" than watching an iterate converge.
• Dimension, not geometry. Switch between Pentagon and Many Facets: the count does not grow with the number of edges — 48.3 on the pentagon against 34.7 on the far more constrained region — because the shrink factor depends on the number of variables and nothing else. Simplex pivot counts track the number of edges walked; the ellipsoid method does not care how many edges there are.
• Cheap guarantees are expensive. Compare against IPM with α_max ≈ 0.99 on the same drawing: a dozen Newton steps against dozens of cuts. The ellipsoid method asks less of the problem — one separating hyperplane per iteration — and pays for it in iterations.
• Turn the options off one at a time. Deep cuts off, ray shoot off, query point Ellipsoid: that is Khachiyan's algorithm as published, and the ellipse takes the full lazy step every iteration. Switching each one back on is a compact tour of how the method was made practical enough to teach.
• Unbounded regions are a real case. Leave the region open in the objective direction and the method still terminates — on the initial ellipsoid's boundary, which lpviz reports as unboundedness rather than as an answer. Widening Initial ellipsoid size moves the fence, and the reported point moves with it.