By this author

An Algorithm for Finding the Generalized Chebyshev Center of Sets Defined via Their Support Functions

Issue number 6 from 15.06.2024

Статья посвящена задаче оптимизации. Пусть A,B ⊂ Rn - выпуклые компакты. Рассмотрим минимальное число t0 > 0 такое, что t0B накрывает A после сдвига на вектор x0 ∈ Rn. Цель - найти t0 и x0. В частном случае, когда B является единичным шаром с центром в нуле, x0 и t0 известны как чебышевский центр и чебышевский радиус A. В данной статье рассматривается случай, когда A и B определяются с помощью своих опорных функций. Предложен алгоритм в духе гардиентного спуска Б.Т. Поляка для эффективного решения таких задач. Алгоритм имеет сверхлинейную скорость сходимости и может решать стомерные тестовые задачи за разумное время, однако для гарантии наличия сходимости необходимы некоторые дополнительные условия на A и B. Дополнительно исследовано поведение алгоритма для простого частного случая, что приводит к ряду теоретических результатов. Изучаются также возмущения этого частного случая.

8 0