Cutting plane method vs. ellipsoid problem

Question

Why is cutting plane (centroid) algorithm an order of $n$ faster than the Ellipsoid method? I am referring to the number of iterations / queries to the separating oracle that they make. I know in ellipsoid it is $ O(n^2 * log(R/r)) $ while Cutting Plane makes $ O(n* log(R/r)) $ queries to the oracle. Why is it faster than Ellipsoid? They seem to work similarly.

Answer 1

In the ellipsoid method the constraint is always in the form of an ellipsoid, while in cutting plane methods, linear inequalities are used to form a polyhedral set. The algorithms are fundamentally different in that respect.

There are several different cutting plane methods depending on what point is used to determine the cut. Many of them, such as the widely used analytic center cutting plane method (ACCPM) and the maximum volume ellipsoid method also have the $n^{2}$ factor in the running time.

The center of gravity (CG) method mentioned in the Boyd lecture notes does reduce this to a factor of $n$, but finding the center of gravity isn't something that can actually be done in practice for problems of interesting dimension. This is discussed in Boyd's lecture notes.