I.G. Tsar’kov. Stability of the relative Chebyshev projection in polyhedral spaces ... P. 235-245

The paper is concerned with structural and stability properties of the set of Chebyshev   centers of a set. Given a nonempty bounded subset $M$ of a metric space $(X,\varrho)$, the quantity $\operatorname{diam} M =\sup_{x,y\in M}\varrho(x,y)$ is called the diameter of $M$, and $r_M:=r(M):=\inf\bigl\{a\geqslant 0, \ x\in X \mid M\subset B(x,a)\bigr\}$, the Chebyshev radius of $M$. A point $x_0\in X$ for which $M\subset B(x_0,r(M))$ is called a Chebyshev center of $M$. The concept of a Chebyshev center and related stability, existence and uniqueness problems are important in various branches of mathematics. We study the structure of the set of Chebyshev centers and the stability of the Chebyshev projection (the Chebyshev center map). In the space $X=C(Q)$, where $Q$ is a normal topological space, we describe the structure of the Chebyshev center of  sets with a unique Chebyshev center. The Chebyshev projection is the mapping associating with a nonempty bounded set the set of all its Chebyshev centers. Given a nonempty bounded set $M$ of a space $X$ and a nonempty set $Y\subset X$, the relative Chebyshev radius is defined as $ r_Y(M)=\inf_{y\in Y} r(y,M)$, where $  r(x,M):=\inf\bigl\{r\ge 0\mid M\subset B(x,r)\bigr\}=\sup_{y\in M}\|x-y\|$. The set of relative Chebyshev centers is defined as $  \mathrm{Z}_Y(M):=\{y\in Y\mid r(y,M)=r_Y(M)\}$. The mapping $M\mapsto \mathrm{Z}_Y(M)$ is called the relative Chebyshev projection (with respect to the set $Y$). Stability properties of the relative Chebyshev projection in finite-dimensional polyhedral spaces are studied. In particular, in a finite-dimensional polyhedral space, the projection $\mathrm{Z}_Y(\,\cdot\,)$, where  $Y$ is  a subspace, is shown to be globally Lipschitz continuous.

Keywords: Chebyshev center, Chebyshev projection, stability

Received September 11, 2018

Revised November 14, 2018

Accepted November 19, 2018

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 16-01-00295) and by the RF President’s Grant for State Support of Leading Scientific Schools (project no. NSh-6222.2018.1).

Igor’ Germanovich Tsar’kov, Dr. Phys.-Math. Sci., Prof., Department of Mechanics and Mathematics Moscow State University, Moscow, 119991 Russia, e-mail: igtsarkov@yandex.ru


1.   Ivanov G.E., Balashov M.V. Lipschitz continuous parametrizations of set-valued maps with weakly convex images. Izv. Math., 2007, vol. 71, no. 6, pp. 1123–1143. doi: 10.1070/IM2007v071n06ABEH002384

2.   Balashov M.V., Repov$\check{\mathrm{s}}$ D. On Pli$\acute{\mathrm{s}}$ metric on the space of strictly convex compacta. J. Convex Anal., 2012, vol. 19, no. 1, pp. 171–183.

3.   Zikratov I.A., Shago F.N., Gurtov A.V., Ivaninskaya I.I. Optimization of the coverage zone for a cellular network based on mathematical programming. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2015, vol. 15, no. 2, pp. 313–321 (in Russian). doi: 10.17586/2226-1494-2015-15-2-322-328

4.   Geniatulin K., Nosov V. Using of coordinating rings method in frequency-spatial planning of mobile satellite communication system with zonal maintenance. Vestnik SibGUTI, 2014, no. 1, pp. 35–45.

5.   Bychkov I.V., Kazakov A.L., Lempert A.A., Bukharov D.S., Stolbov A.B. The intelligent management system of development of regional transport-logistic infrastructure. Autom. Remote Control, 2016, vol. 77, no. 2, pp. 332–343. doi: 10.1134/S0005117916020090

6.   Guseinov Kh.G., Moiseev A.N., Ushakov V.N. On the approximation of reachable domains of control systems. J. Appl. Math. Mech., 1998, vol. 62, no. 2, pp. 169–175.

7.   Ivanov V.V. Algorithms of optimal accuracy for the approximate solution of operator equations of the first kind. U.S.S.R. Comput. Math. Math. Phys., 1975, vol. 15, no. 1, pp. 1–9. doi: 10.1016/0041-5553(75)90129-9

8.   Ushakov V.N., Lebedev P.D., Lavrov N.G. Algorithms of optimal packing construction in ellipse. Vestnik YuUrGU. Ser. Mat. Model. Progr., 2017, vol. 10, no. 3, pp. 67–79 (in Russian). doi: 10.14529/mmp170306

9.   Alimov A.R., Tsar’kov I.G. Connectedness and solarity in problems of best and near-best approximation. Russian Math. Surveys, 2016, vol. 71, no. 1, pp. 1–77. doi: 10.1070/RM9698

10. Vasil’eva A.A. Closed spans in C(T)$ and $L_\varphi(T)$C(T)  and their approximative properties. Math. Notes, 2003, vol. 73, no. 1, pp. 125–128. doi: 10.1023/A:1022134303534

11.   Vasil’eva A.A. Closed spans in vector-valued function spaces and their approximative properties. Izv. Math., 2004, vol. 68, no. 4, pp. 709–747. doi: 10.1070/IM2004v068n04ABEH000496

12.   Garcia-Ferreira S., Ortiz-Castillo Y.F., Yamauchi T. Insertion theorems for maps to linearly ordered topological spaces. Topol. Appl., 2015, vol. 188, pp. 74–81. doi: 10.1016/j.topol.2015.03.011

13.   Franchetti C., Cheney E.W. The embedding of proximinal sets. J. Approx. Theory, 1986, vol. 4, pp. 213–225. doi: 10.1016/0021-9045(86)90006-7

14.   Levitin E.S. Perturbation theory in mathematical programming and its application. Wiley Series in Discrete Mathematics and Optimization (book 38), 1st Edition, N Y: Wiley, 1994. 402 p. ISBN-10: 0471939358 . Original Russian text published in Levitin E.S., Teoriya vozmushchenii v matematicheskom programmirovanii i ee prilozheniya, Moscow, Nauka Publ., 1992, 359 p.

15.   Polovinkin E.S., Balashov M.V. Elementy vypuklogo i sil’no vypuklogo analiza [Elements of convex and strongly convex analysis]. Moscow: Fizmatlit Publ., 2004, 416 p. ISBN: 5-9221-0499-3

16.   Druzhinin Yu.Yu. Existence of a Lipschitz selection of the Chebyshev-centre map. Sb. Math., 2013, vol. 204, no. 5, pp. 641–660. doi: 10.1070/SM2013v204n05ABEH004315

17.   Cline A.K. Lipschitz conditions on uniform approximation operators. J. Approx. Theory, 1973, vol. 8, no. 2, pp. 160–172. doi: 10.1016/0021-9045(73)90025-7

18.   Berdyshev V.I. Metric projection onto finite-dimensional subspaces of C and L. Math. Notes, 1975, vol. 18, no. 4, pp. 871–879. doi: 10.1007/BF01153037

19.   Bartelt M. On Lipschitz conditions, strong unicity and a theorem of A.K. Cline. J. Approx. Theory, 1975, vol. 14, no. 4, pp. 245–250. doi: 10.1016/0021-9045(75)90072-6

20.   Finzel M. Linear-approximation in $\ell^\infty_n$.  J. Approx. Theory, 1994, vol. 76, no. 3, pp. 326–350. doi: 10.1006/jath.1994.1021

21.   Li W. Hoffman’s theorem and metric projections in polyhedral spaces. J. Approx. Theory, 1993, vol. 75, no. 1, pp. 107–111. doi: 10.1006/jath.1993.1090

22.   Finzel M., Li W. Piecewise affine selections for piecewise polyhedral multifunctions and metric projections. J. Conv. Anal., 2000, vol. 7, no. 1, pp. 73–94.