Применение экстремальных эллипсоидов в задачах представления данных при суррогатном моделировании

В докладе будут рассмотрены некоторые задачи при представлении и сжатии данных в суррогатных моделях, в которых используются разные экстремальные эллипсоиды.
Первая задача сводится к следующей. В пространстве $R^N$ задан выпуклый многогранник $P$ с помощью системы линейных неравенств $Ax<b$, где $x$ – вектор в $R^N$, $A$ – матрица размера $K\times N$, $b$ – вектор-столбец размерности $K$, стоящий в правой части системы неравенств. Необходимо построить эффективный алгоритм «случайного блуждания» по многограннику $P$.
Вторая задача такая: в многограннике $P$ задано конечное множество точек $Q=\{x_1,\dots,x_M\}$. Требуется построить $N$-мерный эллипсоид, принадлежащий многограннику $P$, который «хорошо» аппроксимирует множество $Q$.
Будет описано несколько подходов к решению этих задач. В первой задаче используется аналитический центр многогранника и эллипсоид Дикина. Решение второй задачи основано на построении классических экстремальных эллипсоидов: эллипсоида минимального объема, содержащего точки $Q$, и эллипсоида максимального объема, вписанный в многогранник $P$. Такие задачи весьма эффективно решаются с применением техники линейный матричных неравенств, разработанной в теории выпуклой оптимизации.
Эти задачи достаточно актуальны в приложениях, например, при описании крыла самолета при суррогатном моделировании и оптимизации аэродинамики полета самолета.
При компьютерном моделировании используется открытый программный пакет CVX, разработанный под руководством профессора Стефана Бойда (Stephen Boyd), известного специалиста по выпуклой оптимизации.
В докладе будет также рассказано про метод линейных матричных неравенств, который лежит в основе построения экстремальных эллипсоидов.