1. Введение 3
2. Постановка задачи 4
3. Вспомагательные сведения 6
4. Решение задачи 10
4.1 Алгоритм проверки условий крайности 10
4.2 Программная реализация 13
5. Заключение 20
Список литературы 21
Во многих задачах вычислительной геометрии и на некоторых этапах реализации алгоритмов недифференцируемой оптимизации возникает задача по выявлению крайних точек выпуклой оболочки конечного числа точек. Например, кодифференциал функции f суммы от кодифференцируемых функций fk представляет собой сумму (по Минковскому) кодифференциалов dfk, т.е. сумму выпуклых многогранников. Естественно, что количество элементов в кодифференциале df функции f возрастает экспоненциально. В таком случае для эффективной работы численных алгоритмов негладкого анализа необходимо производить «чистку», т.е. отбросить не информативные точки и оставить только крайние.
Из известных методов решающих рассматриваемую задачу является алгоритм QuickHull [3] — построение выпуклой оболочки для заданного набора точек. Однако, его применение сопряжено со многими ограничениями. Разработчики пакета MatLab обращают внимание на то, что данная процедура дает гарантированный результат для набора точек из про странства размерностей не более 6-9.
В работе рассматривается программная реализация по выявлению крайних точек у множества, которое получается в результате сложения многогранника и отрезка. Теоретической базой данного алгоритма являются результаты работы [1]. Предполагается, что многогранник задан крайними точками, а также известны грани и их нормали. В частности, данную информацию о многограннике можно получить в результате применения алгоритма QuickHull...
В работе разработан программный пакет на языке JavaScript для численной проверки необходимого и достаточного условия крайности точек суммы двух многогранников. Крайние точки сравнивались с результатами нахождения выпуклой оболочки этой суммы. Численные эксперименты подтверждают теоретические результаты. В трехмерном случае удалось наглядно изобразить каждый этап программной реализации.
