Рассматривается задача покрытия данного выпуклого компакта гомотетичным образом другого выпуклого компакта с заданным центром гомотетии, вычисляется коэффициент гомотетии. Задача имеет старую историю и тесно связана с вопросами о чебышевском центре, задачах о транслятах и другими задачами вычислительной геометрии. Методы аппроксимации многогранниками и другие аппроксимационные методы не работают в пространстве уже умеренной размерности (более 5 на ПК). Мы предлагаем подход, основанный на применении метода проекции градиента, который гораздо слабее чувствителен к размерности, чем аппроксимационные методы. Мы выделяем классы множеств, для которых удается доказать линейную скорость сходимости градиентного метода, т. е. сходимость со скоростью геометрической прогрессии с положительным знаменателем строго меньше 1. Эти множества должны быть сильно выпуклыми и обладать в определенном смысле гладкостью границы.
The problem of covering of a given convex compact set by a homothetic image of another convex compact set with a given homothety center is considered, the coefficient of homothety is calculated. The problem has an old history and is closely related to questions about the Chebyshev center, problems about translates, and other problems of computational geometry. Polyhedral approximation methods and other approximation methods do not work in a space of already moderate dimension (more than 5 on a PC). We propose an approach based on the application of the gradient projection method, which is much less sensitive to dimension than the approximation methods. We select classes of sets for which we can prove the linear convergence rate of the gradient method, i. e. convergence with the rate of a geometric progression with a positive ratio strictly less than 1. These sets must be strongly convex and have, in a certain sense, smoothness of the boundary.
The authors declare that there are no conflicts of interest present.