Меню: Главная :: К журналу :: switch to Russian :: switch to English
Вы здесь: Все журналы и выпуски→ Журнал→ Выпуск→ Статья

Вложение гомотета в выпуклый компакт: алгоритм и его сходимость

Аннотация

Рассматривается задача покрытия данного выпуклого компакта гомотетичным образом другого выпуклого компакта с заданным центром гомотетии, вычисляется коэффициент гомотетии. Задача имеет старую историю и тесно связана с вопросами о чебышевском центре, задачах о транслятах и другими задачами вычислительной геометрии. Методы аппроксимации многогранниками и другие аппроксимационные методы не работают в пространстве уже умеренной размерности (более 5 на ПК). Мы предлагаем подход, основанный на применении метода проекции градиента, который гораздо слабее чувствителен к размерности, чем аппроксимационные методы. Мы выделяем классы множеств, для которых удается доказать линейную скорость сходимости градиентного метода, т. е. сходимость со скоростью геометрической прогрессии с положительным знаменателем строго меньше 1. Эти множества должны быть сильно выпуклыми и обладать в определенном смысле гладкостью границы.

Ключевые слова

метод проекции градиента, сильная выпуклость, равномерная гладкость, опорная функция, невыпуклая оптимизация

Полный текст статьи

Скачать

DOI

10.20310/2686-9667-2022-27-138-143-149

УДК

517.977

Страницы

143-149

Список литературы

[1] Л. Данцер, Б. Грюнбаум, В. Кли, Теорема Хелли и ее применения, Мир, М., 1968. [2] M. Althoff, G. Frehse, A. Girard, “Set propagation techniques for reachability analysis”, Annual Review of Control, Robotics, and Autonomous Systems, 4:1 (2021), 369–395. [3] Б.Т. Поляк, Введение в оптимизацию, Наука, М., 1983. [4] М.В. Балашов, Е.С. Половинкин, “M -сильно выпуклые подмножества и их порождающие множества”, Матем. сб., 191:1 (2000), 27–64. [5] P. Cannarsa, H. Frankowska,, “Interior sphere property of attainable sets and time optimal control problems”, ESAIM: Control, Optimisation and Calculus of Variations, 12:2 (2006), 350–370. [6] J. Bolte, Sh. Sabach, M. Teboulle, “Proximal alternating linearized minimization for nonconvex and nonsmooth problems”, Mathematical Programming, 146:1–2 (2014), 459–494. [7] M.V. Balashov, A.A. Tremba, “Error bound conditions and convergence of optimization methods on smooth and proximally smooth manifolds”, Optimization, 71:3 (2022), 711-735. [8] G.E. Ivanov, V.V. Goncharov, “Strong and weak convexity of closed sets in a Hilbert space”, Operations Research, Engineering, and Cyber Security. V. 113, Springer Optimization and Its Applications, eds. N. Daras, T. Rassias, Springer International Publishing, Cham, Switzerland, 2017, 259–297.

Поступила в редакцию

2022-05-22

Название раздела в выпуске

Научные статьи

Для корректной работы сайта используйте один из современных браузеров. Например, Firefox 55, Chrome 60 или более новые.