Ellipsoidal approximations of convex sets based on the volumetric barrier

Let C [included] R[exp.n] be a convex set. We assume that [norm.x][infinity]≤1for all x [belong] C; and that C contains a ball of radius 1/R. For x [belong] R[exp.n] , r [belong] R, and B an nxn positive definite matrix, let E (x,B,r) ={y|(y - x) [exp.t] B(y - x) ≤ r[exp.2]}. A [bêta] -rounding of C is an ellipsoid E(x, B, r/[bêta][included]C[included]E(x, B, r).In the case that C is characterized by a separation oracle, it is well known that an O(n[exp.3/2] ) -rounding of C can be obtained using the shallow cut ellipsoid method in O(n[exp.3] ln(nR)) oracle calls. We show that a modification of the volumetric cutting plane method obtains an O(n[exp.3/2]) -rounding of C in O(n2 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.