We study the problem of computing a $(1+\eps)$-approximation to the minimum volume covering ellipsoid of a given set $\cS$ of the convex hull of $m$ full-dimensional ellipsoids in $\R^n$. We extend the first-order algorithm of Kumar and \Yildirim~that computes an approximation to the minimum volume covering ellipsoid of a finite set of points in $\R^n$, which, in turn, is a modification of Khachiyan’s algorithm. For fixed $\eps > 0$, we establish a polynomial-time complexity, which is linear in the number of ellipsoids $m$. In particular, the iteration complexity of our algorithm is identical to that for a set of $m$ points. The main ingredient in our analysis is the extension of polynomial-time complexity of certain subroutines in the algorithm from a set of points to a set of ellipsoids. As a byproduct, our algorithm returns a finite “core” set $\cX \subseteq \cS$ with the property that the minimum volume covering ellipsoid of $\cX$ provides a good approximation to that of $\cS$. Furthermore, the size of $\cX$ depends only on the dimension $n$ and $\eps$, but not on the number of ellipsoids $m$. We also discuss the extent to which our algorithm can be used to compute the minimum volume covering ellipsoid of the convex hull of other sets in $\R^n$. We adopt the real number model of computation in our analysis.
Citation
SIAM Journal on Optimization, 17 (3) pp. 621-641 (2006)