Optimization Online


On Khachiyan's Algorithm for the Computation of Minimum Volume Enclosing Ellipsoids

Michael J. Todd (miketodd***at***cs.cornell.edu)
E. Alper Yildirim (yildirim***at***bilkent.edu.tr)

Abstract: Given $\cA := \{a^1,\ldots,a^m\} \subset \R^d$ whose affine hull is $\R^d$, we study the problems of computing an approximate rounding of the convex hull of $\cA$ and an approximation to the minimum volume enclosing ellipsoid of $\cA$. In the case of centrally symmetric sets, we first establish that Khachiyan's barycentric coordinate descent (BCD) method is exactly the polar of the deepest cut ellipsoid method using two-sided symmetric cuts. This observation gives further insight into the efficient implementation of the BCD method. We then propose a new algorithm which computes an approximate rounding of the convex hull of $\cA$, and which can also be used to compute an approximation to the minimum volume enclosing ellipsoid of $\cA$. Our algorithm is a modification of the algorithm of Kumar and \Yildirim, which combines Khachiyan's BCD method with a simple initialization scheme to achieve a slightly improved polynomial complexity result, and which returns a small ``core set.'' We establish that our algorithm computes an approximate solution to the dual optimization formulation of the minimum volume enclosing ellipsoid problem that satisfies a more complete set of approximate optimality conditions than either of the two previous algorithms. Furthermore, this added benefit is achieved without any increase in the improved asymptotical complexity bound of the algorithm of Kumar and \Yildirim~or any increase in the bound on the size of the computed core set. In addition, the ``dropping idea'' used in our algorithm has the potential of computing smaller core sets in practice. We also discuss several possible variants of this dropping technique.

Keywords: L{\"o}wner ellipsoid, core sets, rounding of polytopes, ellipsoid method, approximation algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Discrete Applied Mathematics, 155 (13) pp. 1731-1744 (2007).


Entry Submitted: 10/03/2005
Entry Accepted: 10/03/2005
Entry Last Modified: 08/24/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