Тематический выпуск

Алгоритм нахождения обобщенного чебышевского центра множеств, заданных опорными функциями

П. А. Архипов

Институт науки и технологий (ISTA), Австрия

Аннотация: Статья посвящена задаче оптимизации. Пусть ${A, B \subset \mathbb{R}^n}$ – выпуклые компакты. Рассмотрим минимальное число ${t^0 > 0}$ такое, что $t^0 B$ накрывает $A$ после сдвига на вектор ${x^0 \in \mathbb{R}^n}$. Цель – найти $t^0$ и $x^0$. В частном случае, когда $B$ является единичным шаром с центром в нуле, $x^0$ и $t^0$ известны как чебышевский центр и чебышевский радиус $A$. В данной статье рассматривается случай, когда $A$ и $B$ определяются с помощью своих опорных функций. Предложен алгоритм в духе градиентного спуска Б.Т. Поляка для эффективного решения таких задач. Алгоритм имеет сверхлинейную скорость сходимости и может решать стомерные тестовые задачи за разумное время, однако для гарантии наличия сходимости необходимы некоторые дополнительные условия на $A$ и $B$. Дополнительно исследовано поведение алгоритма для простого частного случая, что приводит к ряду теоретических результатов. Изучаются также возмущения этого частного случая.

Ключевые слова: оптимизация, чебышевский центр, градиентный спуск.

Статья представлена к публикации членом редколлегии: П. С. Щербаков

Поступила в редакцию: 25.01.2024
После доработки: 12.03.2024
Принята к публикации: 20.03.2024

DOI: 10.31857/S0005231024060059

 Англоязычная версия: Automation and Remote Control, 2024, 85:6, 522–532