Эллипсоид минимального объема

[grisania]

Кто знает, где в русских рессурсах Инета (можно и в аглицких рессурсах) написан алгоритм вычисления эллипсоида минимального объема, содержащий данное множество точек в n-мерном пространстве. Желательно, что бы считалось полуопределенным программированием (Semidefinite Programming).

[Vassil]

Много насчет полу-определенном программировании, в том числе, ссылки на ряд публикаций, алгоритмы (в том числе он-лайн, паралельные), ...

http://grid.r.dendai.ac.jp/sdpa/

Добавлено спустя 19 минут 54 секунды:

Или еще ...

По линку

http://www.control.isy.liu.se/~johanl/yalmip.html

можно увидеть

http://www.eecs.berkeley.edu/~akurzhan/ ... Manual.pdf

Не найдется ли там искомый Вами ответ?

[Vassil]

Поискал в Google по словам "Computation of Minimum-Volume" и оттуда видно, что есть статья в журнале

OPERATIONS RESEARCH, Vol. 52, No. 5, September–October 2004, pp. 690–706,

Computation of Minimum-Volume Covering Ellipsoids авторы: Peng Sun и Robert M. Freund

We present a practical algorithm for computing the minimum-volume n-dimensional ellipsoid that must contain m given points . 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.