Why is the Ellipsoid Method of polynomial complexity?

Question

We know that the ellipsoid method is proven to be of polynomial complexity.

However, as far as I can tell we may need to add exponentially many feasibility cuts in order to solve the LP (or prove no solution exists), which results in a non-polynomial amount of calculations, which is the method is inefficient in practice.

Is the method considered polynomial simply because we measure P-hardness as a function of the number of variables, or is there also a polynomial bound on the number of constraints that we need to add?

Answer 1

The ellipsoid method is polynomial for the same reason that you cannot fold a piece of paper 103 times: exponential growth! Because the formal proof is already in Khachiyan (1980), I will try to give a more informal and intuitive explanation. Please forgive my simplifications for the sake of clarity.

Consider a linear program. That is, we want to minimize a linear function over a polyhedron.

Bounding the polyhedron

If the polyhedron is not bounded, we will cut off a region to make it bounded. If the region that we cut off is far away, this probably doesn't matter anyways.$^1$ Hence, we may assume that the feasible region is a polytope.

Observation

Given a point in the polytope, we can split the polytope in a 'good side' and a 'bad side'. In the good side, all objective values are better or equal. In the bad side, all objective values are worse. This follows from the linear objective function.

Center of gravity method

The center of gravity method is related to the ellipsoid method, but is not polynomial. The idea is simple:

1. Calculate the center of gravity of the current polytope.
2. Throw away the 'bad side'.
3. Repeat Steps 1 and 2 until the current polytope is small.

Note that Step 2 always halves the volume of the current polytope, because we use the center of gravity. Hence, the volume of the current polytope decreases exponentially. This means that in a polynomial number of steps you will have an exponentially small area that contains an optimal solution.

There is only one problem: calculating the center of gravity for an arbitrary polytope is difficult.

Ellipsoid method

The ellipsoid method solves this problem in a clever way: calculating the center of gravity of ellipsoids is almost trivial, so let's just pretend that our polytope is an ellipsoid. We start with an ellipsoid that contains the polytope completely.

1. Calculate the center of gravity of the current ellipsoid.
2. Throw away the 'bad side'.
3. Put the 'good side' in a smaller ellipsoid, which becomes the current ellipsoid.
4. Repeat Steps 1 to 3 until the current ellipsoid is small.

In Step 2, if it happens to be that the center of gravity of the current ellipsoid is feasible for the original LP, then we throw away the bad side as before. If the center of gravity is not feasible, there is still a bad side: it is the half of the ellipsoid that is completely infeasible. Make a sketch to convince yourself this is true. In both cases, the result is that the bad side does not contain the optimum.

In Step 2, half of the current ellipsoid is removed. In Step 3, we create a new ellipsoid that is smaller than the current ellipsoid. It turns out you can do this in such a way that the new volume is bounded by some factor between 0.5 and 1 of the previous ellipsoid. Hence, we again get exponential decrease!

As a result, after a polynomial amount of work, we know the optimal solution to exponential precision. We do not need explicit feasibility cuts, just ellipsoids.

Final thoughts

Basically, knowing the optimal solution to exponential precision is good enough to find an exact solution, because all input values have only so many digits. In the paper by Khachiyan, technical details like this are discussed properly.

$^1$ It really does not matter, see Lemma 1 (Khachiyan, 1980).