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

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

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