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:
[email protected]