Введение 4
Глава 1. Постановка задачи 5
Глава 2. Задача Сильвестра 6
2.1. Постановка задачи 6
2.2. Общий вид задачи квадратичного программирования и двойственной к ней 7
2.3. Двойственная задача для задачи Сильвестра и её решение 8
2.4. Решение задачи в среде MATLAB 9
Глава 3. Алгоритм Шора 12
3.1. Оператор сжатия пространства 12
3.2. Итеративный алгоритм построения минимального эллипсоида 14
3.3. Практическое испытание алгоритма 18
Глава 4. Алгоритм Хачияна 20
4.1. Вспомогательные сведения 20
4.2. Вывод двойственной задачи для задачи о минимальном эллипсоиде. . . 21
4.3. Алгоритм Хачияна 24
Глава 5. Комбинированный алгоритм 27
Глава 6. Сводное сравнение методов 30
Заключение 32
Список литературы
В данной работе рассматривается задача построения эллипсоида минимального объёма, содержащего заданное множество точек в R". Как её частный случай также рассмотрена задача Сильвестра — задача построения минимального шара.
Решение задачи Сильвестра получается с помощью двойственной задачи квадратичного программирования. Оно реализовано в MATLAB. Продемонстрированы результаты работы программы на тестовых данных.
Для задачи о минимальном эллипсоиде описано три алгоритма, дающих приближённое решение. Все три алгоритма используют вспомогательную задачу в пространстве R"+1, которая позволяет искать эллипсоид с фиксированным центром. Представлен вывод формул, по которым восстанавливается решение исходной задачи.
Первый алгоритм, алгоритм Шора, использует оператор сжатия пространства. Оператор сжатия рассмотрен подробно и его работа проиллюстрирована на нескольких примерах с шарами и эллипсами на плоскости.
Вторым был рассмотрен алгоритм Хачияна. Этот алгоритм решает двойственную по Лагранжу задачу, по решению которой однозначно восстанавливается решение исходной. Подробно представлен вывод двойственной задачи и самого алгоритма.
На основе алгоритма Хачияна разработан и описан комбинированный алгоритм, с помощью которого решается двойственная задача. Используется градиентный метод без точного линейного поиска и идея активного множества.
Все три метода реализованы в MATLAB и протестированы на модельных задачах. Приведены сводные таблицы результатов, в которых представлены данные о точности вычислений и затраченном времени. Продемонстрировано превосходство комбинированного метода во всех тестовых случаях
В рамках данной работы проведён анализ решения задачи о минимальном эллипсоиде с применением теории двойственности по Лагранжу. Рассмотрен также частный случай — задача Сильвестра, для которой получено решение с помощью двойственности в квадратичном программировании.
Одним из результатов работы является разработка комбинированного алгоритма, использующего идею повышения размерности из алгоритма Шора, идею двойственности по Лагранжу из алгоритма Хачияна и градиентный метод без точного линейного поиска.
Все алгоритмы реализованы в MATLAB и проверены на множестве тестовых примеров. Приведены сводные таблицы точности и времени работы всех методов, выполнено сравнение их производительности на задаче Сильвестра, для которой имеется точное решение с помощью квадратичного программирования.
Предварительные результаты были опубликованы в [8,9,10,11].
