Menu: Home :: go to Journal :: switch to Russian :: switch to English
You are here: all Journals and Issues→ Journal→ Issue→ Article

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


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.


gradient projection method, strong convexity, uniform smoothness, supporting function, nonconvex optimization

Full-text in one file









[1] L. Danzer, B. Grunbaum, V. Klee, Helly's Theorem and its Applications, Mir Publ., Moscow, 1968 (In Russian). [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] B. T. Polyak, Introduction to Optimization, Optimization Software, New York, 1987. [4] M.V. Balashov, E.S. Polovinkin, “M -strongly convex subsets and their generating sets”, Sb. Math., 191:1 (2000), 25–60. [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.



Section of issue

Scientific articles

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