Ellipsoidal Approximations of Convex Sets Based on the Volumetric Barrier

Kurt M. Anstreicher

Let $\Ccal\subset\Re^n$ be a convex set. We assume that $\infnorm{x}\le 1$ for all $x\in\Ccal$, and that $\Ccal$ contains a ball of radius $1/R$. For $x\in\Re^n$, $r\in\Re$, and $B$ an $n\times n$ positive definite matrix, let $E(x,B,r)=\set{y\suchthat (y-x)\tran B (y-x)\le r^2}$. A $\beta$-{\it rounding} of $\Ccal$ is an ellipsoid $E(x,B,r)$ such that $E(x,B,r/\beta)\subset\Ccal\subset E(x,B,r)$. In the case that $\Ccal$ is characterized by a separation oracle, it is well known that an $O(n^{3/2})$-rounding of $\Ccal$ 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 $\Ccal$ in $O(n^2\ln(nR))$ oracle calls. We also consider the problem of obtaining an $O(n)$-rounding of $\Ccal$ when $\Ccal$ 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.

Contact: kurt-anstreicher@uiowa.edu