4 октября 2012, 17:00, ИППИ
Доклад В.В.Чепыжова и А.А.Ильина
ПРИМЕНЕНИЕ ЭКСТРЕМАЛЬНЫХ ЭЛЛИПСОИДОВ В ЗАДАЧАХ ПРЕДСТАВЛЕНИЯ ДАННЫХ ПРИ СУРРОГАТНОМ МОДЕЛИРОВАНИИ
Аннотация. В докладе будут рассмотрены некоторые задачи при представлении и сжатии данных в суррогатных моделях, в которых используются разные экстремальные эллипсоиды.
Первая задача сводится к следующей. В пространстве $R^N$ задан выпуклый многогранник $P$ с помощью системы линейных неравенств $Ax<b$, где $x$ -- вектор в $R^N$, $A$ -- матрица размера $K imes N$, $b$ -- вектор-столбец размерности $K$, стоящий в правой части системы неравенств.
Необходимо построить эффективный алгоритм "случайного блуждания" по многограннику $P$.
Вторая задача такая: в многограннике $P$ задано конечное множество точек $Q={x_1,...,x_M}$. Требуется построить N-мерный эллипсоид, принадлежащий многограннику $P$, который "хорошо" аппроксимирует множество $Q$.
Будет описано несколько подходов к решению этих задач. В первой задаче используется аналитический центр многогранника и эллипсоид Дикина. Решение второй задачи основано на построении классических экстремальных эллипсоидов: эллипсоида минимального объема, содержащего точки $Q$, и эллипсоида максимального объема, вписанный в многогранник $P$. Такие задачи весьма эффективно решаются с применением техники линейный матричных неравенств, разработанной в теории выпуклой оптимизации.
Эти задачи достаточно актуальны в приложениях, например, при описании крыла самолета при суррогатном моделировании и оптимизации аэродинамики полета самолета.
При компьютерном моделировании используется открытый программный пакет CVX, разработанный под руководством профессора Стефана Бойда (Stephen Boyd), известного специалиста по выпуклой оптимизации.
В докладе будет также рассказано про метод линейных матричных неравенств, который лежит в основе построения экстремальных эллипсоидов.
| 28.09.2012 | Петров Леонид Александрович |