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.
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:
- Calculate the center of gravity of the current polytope.
- Throw away the 'bad side'.
- 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.
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.
- Calculate the center of gravity of the current ellipsoid.
- Throw away the 'bad side'.
- Put the 'good side' in a smaller ellipsoid, which becomes the current ellipsoid.
- 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.
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).