Аннотация:
Будут рассмотрены методы описания пространства дизайна и представления данных с помощью экстремальных эллипсоидов.
Работа актуальна в области оптимизации, предсказательного метамоделирования, детектирования аномалий, задачах представления данных.
Пусть имеется конечное множество точек X, удовлетворяющих заданному множеству линейных ограничений. Ставится двухкритериальная задача нахождения эллипсоида минимального объема, содержащего наибольшее количество точек из X, который принадлежит заданному многограннику ограничений.
Будут представлены приближенные методы построения фронта Парето этой задачи. На базе классических экстремальных эллипсоидов с помощью дополнительных процедур учета многогранника ограничений разработаны алгоритмы приближения фронта Парето. В пространствах небольшой размерности проведено сравнение предложенных методов со случайной генерацией параметров эллипсоида. В упрощенном случае отсутствия линейных ограничений предложен алгоритм на основе решения задачи выпуклой оптимизации для соответствующей гладкой задачи, которая аппроксимирует исходную задачу, содержащую дискретный критерий.
Задачи построения экстремальных эллипсоидов формулируются в виде задач выпуклого программирования, в которой ограничения записываются с использованием аппарата линейных матричных неравенств. Это позволяет использовать при решении этих задач известные высокоэффективные пакеты (CVX и др.)
Будут также рассмотрены две вспомогательные задачи, позволяющие ускорить построение оптимальный эллипсоидов, сократив избыточность данных: задача определения тех точек из конечного множества, которые являются вершинами выпуклой оболочки и задача удаления из системы линейных неравенств тех, отсутствие которых не меняет решение этой линейной системы.
|
