Computation of minimum-volume covering ellipsoids
成果类型：
Article
署名作者：
Sun, P; Freund, RM
署名单位：
Duke University; Massachusetts Institute of Technology (MIT)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1040.0115
发表日期：
2004
页码：
690-706
关键词：
摘要：
We present a practical algorithm for computing the minimum-volume n-dimensional ellipsoid that must contain m given points a(1),..., a(m) is an element of R-n. This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes it particularly amenable to solution by interior-point methods, and it has been the subject of much theoretical complexity analysis. Here we focus on computation. We present a combined interior-point and active-set method for solving this problem. Our computational results demonstrate that our method solves very large problem instances (m = 30,000 and n = 30) to a high degree of accuracy in under 30 seconds on a personal computer.