Введение 3
ГЛАВА 1. Теоретическая часть 5
1.1 Задача проектирования нуля евклидова пространства на выпуклый
многогранник в первоначальной постановке 5
1.2 Линейная задача о дополнительности 6
1.3 Решение задачи о дополнительности 7
1.4 Алгоритм сведения задачи проектирования нуля евклидова пространства на выпуклый многогранник к линейной задаче о
дополнительности 11
ГЛАВА 2. Практическая часть 16
2.1 Разработка программы и интерфейса 16
2.2 Числовые эксперименты 18
Заключение 35
Список использованных источников 36
Приложения 37
Приложение
Задача проектирования нуля евклидова пространства на выпуклый многогранник имеет важное значение в дифференцируемой и недифференцируемой выпуклой оптимизации, в теории линейных разделений выпуклых многогранников, классификации данных. Большое число применений задачи проектирования нуля на выпуклый многогранник заставляет более тщательно изучать возможность сведения этой задачи к другим связанным с ней задачам математического программирования, в частности к линейной задаче о дополнительности.
Задача проектирования нуля евклидова пространства на выпуклый многогранник широко используется в негладкой выпуклой оптимизации в целом и выпуклых минимаксных задачах в частности.
Проблемой исследования данной работы является - поиск решения задачи проектирования нуля евклидова пространства на выпуклый многогранник наиболее оптимальным способом.
Решение этой задачи можно отыскать путем сведения к задаче квадратичного программирования, задаче максимина, неотрицательной задаче методом наименьших квадратов, линейной задаче о дополнительности, однако метод Лемке решения задачи о дополнительности имеет ряд преимуществ в сравнении с большинством методов квадратичного программирования.
Таким образом, целью работы является реализовать в пакете Matlab программу, позволяющую путем решения линейной задачи о дополнительности, находить решение задачи проектирования нуля евклидова пространства. Для её достижения необходимо решить следующие задачи:
- Изучить и численно реализовать алгоритм сведения задачи проектирования нуля евклидова пространства на выпуклый многогранник к линейной задаче о дополнительности;
- Найти решение линейной задачи о дополнительности или убедиться в его отсутствии;
- Написать программу в среде Matlab и спроектировать её интерфейс в среде визуального программирования GUIDE.
Следующая работа включает в себя две главы: первая глава - «Теоретическая часть» - разделена на четыре части: первая содержит постановку задачи проектирования нуля евклидова пространства на выпуклый многогранник; вторая - постановку линейной задачи о дополнительности; третья часть описывает метод решения задачи о дополнительности - алгоритм Лемке; четвертая приводит алгоритм сведения задачи проектирования нуля евклидова пространства на выпуклый многогранник к задаче о дополнительности.
Во второй главе - «Практическая часть» - содержится две части: «Разработка программы и интерфейса», где описывается процесс создания программы и интерфейса к ней; и «Числовые эксперименты», где на различных тестовых примерах проверяется корректность и точность работы программы.
В ходе выполнения данной дипломной работы был изучен и численно реализован алгоритм сведения задачи проектирования нуля евклидова пространства на выпуклый многогранник к линейной задаче о дополнительности; найден способ отыскать решение линейной задачи о дополнительности или убедиться в его отсутствии; написана программа в среде Matlab и спроектирован её интерфейс в среде визуального программирования GUIDE.
На первом этапе работы были изучены и описаны постановки задачи проектирования нуля евклидова пространства на выпуклый многогранник, линейной задачи о дополнительности, а также метод решения задачи о дополнительности; был изучен и численно реализован алгоритм сведения задачи проектирования нуля евклидова пространства на выпуклый многогранник к линейной задаче о дополнительности.
На втором этапе была разработана, реализована и описана программа, позволяющая использовать алгоритм сведения на практике, а также разработан и описан интерфейс к ней; были проведены различные числовые эксперименты, программа была протестирована и показала успешность своей работы.
Таким образом, цель работы достигнута: программа в пакете Matlab, позволяющая путем решения линейной задачи о дополнительности находить решение задачи проектирования нуля евклидова пространства, реализована.
Полученная программа имеет широкие возможности, а также обладает богатой практической применимостью вследствие связанности задачи проектирования нуля евклидова пространства на выпуклый многогранник с задачей вычисления расстояния между выпуклыми многогранниками, такой как компьютерная графика, робототехника, обнаружение столкновений и поиск пути в присутствии препятствий.
