Ellipsoidal Approximations of Convex Sets Based on the Volumetric Barrier

Let C ⊂Rⁿ be a convex set. We assume that ‖x‖_∞ ≤ 1 for all x ∈ C, and that C contains a ball of radius 1/R. For x ∈ Rⁿ, r ∈ R, and B and n × n symmetric positive definite matrix, let E(x, B, r) = {y|(y − x)^TB(y − x) ≤ r²}. A β-rounding of C is an ellipsoid E(x, B, r) such that E(x, B, r/β) ⊂ C ⊂ 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³ 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² 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.