Embedding of a homothete in a convex compactum: an algorithm and its convergence

Abstract

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.