On the Minimum Volume Covering Ellipsoid of Ellipsoids

E. Alper Yildirim (yildirimbilkent.edu.tr)

Abstract: 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.

Keywords: Minimum volume covering ellipsoids, Lowner ellipsoid, core sets, approximation algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: SIAM Journal on Optimization, 17 (3) pp. 621-641 (2006)

Download:

Entry Submitted: 01/14/2005
Entry Accepted: 01/14/2005
Entry Last Modified: 05/04/2007

Modify/Update this entry