Ellipsoidal approximations of convex sets based on the volumetric barrier

Let C subset of R-n be a convex set. We assume that \\x\\(infinity) less than or equal to 1 for all x is an element of C, and that C contains a ball of radius 1/R. For x is an element of R-n, r is an element of R, and B an n X n symmetric positive definite matrix, let E(x, B, r) = {y\(y - x)B-T(y - x) less than or equal to r(2)}. A beta-rounding of C is an ellipsoid E(x, B, r) such that E(x, B, r/beta) subset of C subset of E(x, B, r). In the case that C is characterized by a separation oracle, it is well known that an O(n(3/2))-rounding of C can be obtained using the shallow cut ellipsoid method in O(n(3) ln(nR)) oracle calls. We show that a modification of the volumetric cutting plane method obtains an O(n(3/2))-rounding of C in O(n(2) ln(nR)) oracle calls. We also consider the problem of obtaining an O(n)-rounding of C when C has an explicit polyhedral description. Our analysis uses a new characterization of circumscribing ellipsoids centered at, or near, the volumetric center of a polyhedral set.