Optimization Online


On the Minimum Volume Covering Ellipsoid of Ellipsoids

E. Alper Yildirim (yildirim***at***bilkent.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)


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society