| Sbornik: Mathematics |
|
|
|
|
|
The convex hull and the Carathéodory number of a set in terms of the metric projection operator K. S. Shklyaevab a Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia b Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia
Bibliographic databases:
     § 1. IntroductionLet $(X, \| \cdot \|)$ be a real Banach space. The distance of a point $x \in X$ to a set $M \subset X$ is defined by The closed and open balls, and the sphere in $X$ with centre $x \in X$ and radius $r > 0$ are denoted by $\overline{B}(x,r)$, $B(x,r)$ and $S(x,r)$, respectively. We let $\operatorname{ri} M$ denote the relative interior of a set $M \subset X$, that is, the interior of $M$ in its affine hull
$$
\begin{equation*}
\operatorname{aff} M := \biggl\{ \sum_{i=1}^k \lambda_i x_i\colon k \in \mathbb{N}, \, x_i \in M, \, \lambda_i \in \mathbb{R}, \, \sum_{i=1}^k \lambda_i=1 \biggr\}.
\end{equation*}
\notag
$$
The metric projection of a point $x$ onto a set $M$ is defined by
$$
\begin{equation*}
P_M(x)=\bigl\{y \in M\colon \| x-y \|=d(x, M) \bigr\}.
\end{equation*}
\notag
$$
We say that $M$ is a Chebyshev set if $P_M(x)$ is a singleton for each $x \in X$. The convex hull of a set $M$ is denoted by $\operatorname{conv} M$. The problem of the convexity of Chebyshev sets in concrete and abstract normed spaces has been studied extensively (see, for example, Efimov and Stechkin [1], Klee [2], [3], Berdyshev [4], Brø ndsted [5], Brown [6], [7], Vlasov [8], Balaganskii and Vlasov [9], Tsar’kov [10], [11], and Alimov [12], [13]). The investigations of the geometry of Chebyshev sets in finite-dimensional normed linear spaces date back to Bunt [14], Mann [15] and Motzkin [16], [17]. In his thesis [14] (1934) Bunt proved that, in strictly convex finite-dimensional Banach spaces with second-order modulus of smoothness (and, in particular, in finite-dimensional Euclidean spaces), each Chebyshev set is convex; he also showed that in two-dimensional spaces the condition of strict convexity can be dropped. In particular, this result implies that, in finite-dimensional Euclidean spaces $\mathbb R^n$, the class of Chebyshev sets coincides with the class of convex closed sets. A bit later, Motzkin [16] showed that any Chebyshev set in a two-dimensional normed plane is convex if and only if the space is smooth (a space is smooth if the unit sphere there has a unique support hyperplane at each point). Klee extended Bunt’s and Motzkin’s results in his early papers [2] and [3]: he showed that in any finite-dimensional smooth space every Chebyshev set is convex. Efimov and Stechkin were among the first authors to investigate Chebyshev sets in infinite-dimensional Banach spaces. In particular, they stated the problem of the convexity of Chebyshev sets in (infinite-dimensional) Hilbert spaces. For a survey of results for infinite-dimensional spaces, see [9]. As a natural generalization of Chebyshev sets, we consider sets with at most $k$-valued, nonempty metric projection. Definition 2. The Carathéodory number of a set $M$ is defined as the smallest natural number $k$ such that $\operatorname{conv}_k M=\operatorname{conv} M$. The following Carathéodory convex hull theorem is well known (see [18]): if $M \subset \mathbb{R}^d$, then $\operatorname{conv}_{d+1} M= \operatorname{conv} M $, that is, the Carathéodory number of $M$ is at most $d+1$. Under some additional conditions on a set $M$ the upper estimate of its Carathéodory number can be improved. Results of this type are due to Fenchel (see [10]), Bárány and Karasev (see [20]), and other authors. A detailed account of the available results on the Carathéodory number can be found in [20]. In the present paper we examine the Carathéodory numbers of sets $M$ with at most $k$-valued metric projection $P_M$. In 2010 Borodin stated the following problem. Problem A. Prove that in any finite-dimensional smooth space $X$ the Carathéodory number of each closed set $M \subset X$ with at most $k$-valued metric projection $P_M$ is at most $k$. Note that for $k=1$ this claim is valid because each Chebyshev set in a smooth finite-dimensional space is convex. Also note that for $k \geqslant d+1$ it holds automatically by Carathéodory’s theorem. For $k= d=2$ Problem A was solved by Flerov [21]. In our paper Problem A is solved under certain constraints on $M$, for spaces of arbitrary dimension (in particular, for boundedly compact sets $M$ in infinite-dimensional Banach spaces $X$). In Theorems 1–5 we present more general results on representations of a point in the convex hull of a set $M \subset X$ as a convex combination of points in the metric projection $P_M(x)$ for some $x \in X$. Using these results, in Corollaries 1–4 we derive analogues and extensions of Problem A. Moreover, with the help of Corollaries 1–4 we readily obtain sufficient conditions for the existence of a point with at most $k$-valued metric projection. The corresponding sufficient conditions are as follows: $\operatorname{conv}{M} \neq \operatorname{conv}_k{M}$ in Corollaries 1 and 4, and $\overline{\operatorname{conv}{M}} \neq \overline{\operatorname{conv}_k{M}}$ in Corollaries 2 and 3. Note that the infinite-dimensional analogue of Problem A for a Hilbert space $X$, with no constraints on $M$, includes Open Problem A as a particular case (for $k=1$). § 2. Auxiliary lemmasIn what follows $X_d$ denotes a normed space of dimension $d$. Lemma 1. Let $a, b \in X_d$, $r > 0$, let $a \in B(b,r)$, and let $f\colon \overline{B}(b,r) \to X_d$ be a continuous mapping such that $a \notin [x, f(x)]$ for all $x \in S(b,r)$. Then there exists a point $x_* \in B(b,r)$ such that $f(x_*)=a$. Proof. It can be assumed without loss of generality that $b=0$ and $r=1$. Assume that $f(x) \neq a$ for all $x \in B(0,1)$. Since $a \notin [x, f(x)]$ for all $x \in S(0,1)$, and since $f$ is continuous, there exists $\tau \in (0,1)$ such that $a \notin [x, f(t x)]$ for all $x \in S(0,1)$ and all $t \in [1-\tau, 1]$. Hence
$$
\begin{equation}
g(x,t) := \frac{t+\tau-1}{\tau}x+\frac{1-t}{\tau}f(tx) \neq a
\end{equation}
\tag{1}
$$
for all $x \in S(0,1)$ and all $t \in [1-\tau, 1]$. Consider the automorphism of the sphere $S(0,1)$: The map $\widetilde{f}\colon \overline{B}(0,1) \to S(0,1)$ defined by
$$
\begin{equation*}
\widetilde{f}(tx) := \begin{cases} u^{-1}\biggl( \dfrac{f(tx)-a}{\| f(tx)-a \| }\biggr), &x \in S(0,1),\ t \in [0, 1-\tau), \\ u^{-1}\biggl(\dfrac{g(x,t)-a}{\| g(x,t)-a \| }\biggr), &x \in S(0,1),\ t \in [1-\tau,1], \end{cases}
\end{equation*}
\notag
$$
is well defined in view of (1). Moreover, for all $x \in S(0,1)$,
$$
\begin{equation*}
\frac{g(x,1-\tau)-a}{\| g(x,1-\tau)-a \|}=\frac{f((1-\tau)x)-a}{\| f((1-\tau)x)-a \|}, \qquad \frac{g(x,1)-a}{\| g(x,1)-a\|}=\frac{x-a}{\| x-a\|}.
\end{equation*}
\notag
$$
Hence $\widetilde{f}$ is continuous and $\widetilde{f}|_{S(0,1)} \equiv \mathrm{id}$, that is, $\widetilde{f}$ retracts the ball $\overline{B}(0,1)$ onto its boundary $S(0,1)$, which is impossible (see [22], § 38).
Lemma 1 is proved. Let $(X, d_X)$ and $(Y, d_Y)$ be metric spaces. A set-valued map $F\colon X \to 2^Y \setminus \{\varnothing\}$ is said to be upper semicontinuous at a point $x_0 \in X$ if for each $\varepsilon > 0$ there exists $\delta > 0$ such that, for all $x \in B(x_0,\delta)$,
$$
\begin{equation*}
F(x) \subset B_\varepsilon(F(x_0)) := \Bigl\{ y \in Y\colon d_Y(y, F(x_0)) := \inf_{z \in F(x_0)}d_Y(y, z) < \varepsilon \Bigr\}.
\end{equation*}
\notag
$$
The graph of a set-valued mapping $F\colon X \to 2^Y \setminus \{\varnothing\}$ is defined by
$$
\begin{equation*}
\Gamma_F := \bigl\{ (x,y)\colon x \in X, \, y \in F(x) \bigr\};
\end{equation*}
\notag
$$
it is equipped with the distance $d( (x_1, y_1), (x_2, y_2) ) \,{:=} \max (d_X(x_1, x_2)$, $ d_Y(y_1, y_2) )$. Given a linear space $Y$, we denote the class of nonempty closed convex subsets of $Y$ by $\mathrm{Conv}(Y)$. Lemma 2. Let $a, b \in X_d$, $r > 0$, let $a \in B(b,r)$, and let $F\colon \overline{B}(b,r) \to \mathrm{Conv}(X_d)$ be an upper semicontinuous mapping such that $a \notin \operatorname{conv}(\{x\} \cup F(x))$ for all $x \in S(b,r)$. Then $a \in F(x_*)$ for some $x_* \in B(b,r)$. Proof. It can be assumed without loss of generality that $b=0$ and $r=1$. Suppose that $a \notin F(x)$ for all $x \in \overline{B}(0,1)$. Since $F$ is upper semicontinuous, there exists $\varepsilon \in (0, (1-\| a \|)/2)$ such that, for all $x \in \overline{B}(0,1)$ and all $y \in \overline{B}(0,1) \setminus B(0, 1-\varepsilon)$,
Next we require the following result. Theorem B (see [23], Theorem 1). Let $S$ be a compact metric space, $Y$ be a normed linear space and $\Phi\colon S \to \mathrm{Conv}(Y)$ be an upper semicontinuous mapping. Then for each $\varepsilon > 0$ there exists a single-valued $\varepsilon$-approximation of $\Phi$, that is, a continuous single-valued mapping $\varphi\colon S \to \operatorname{conv} \Phi(S)$ such that the graphs $\Gamma_\Phi$ and $\Gamma_\varphi$ of $\Phi$ and $\varphi$, respectively, satisfy $d^*(\Gamma_\varphi, \Gamma_\Phi):= \sup_{y \in \Gamma_\varphi} d(y, \Gamma_\Phi) < \varepsilon$. By Theorem B there exists a single-valued $\varepsilon$-approximation $f\colon \overline{B}(0,1) \to X$ of the set-valued mapping $F$. Since $d^* (\Gamma_{f},\Gamma_F) < \varepsilon$, by (2) we have
$$
\begin{equation}
B(a,\varepsilon) \cap f(\overline{B}(0,1))=\varnothing.
\end{equation}
\tag{3}
$$
Next we claim that $a \notin [y,f(y)]$ for $y \in S(0,1)$. Indeed, otherwise there exists $\lambda \in [0,1]$ such that Since $d^* (\Gamma_{f},\Gamma_F) < \varepsilon$, there would exist $z \in B(y,\varepsilon) \cap \overline{B}(0,1)$ and $w \in B(f(y),\varepsilon)$ such that $w \in F(z)$. Hence by (4)
$$
\begin{equation*}
\bigl\| \lambda z+(1-\lambda)w-a\bigr\| \leqslant \|\lambda(z-y\|+\bigl\| (1-\lambda)(w-f(y)) \bigr\| < \varepsilon,
\end{equation*}
\notag
$$
that is, $B(a,\varepsilon) \cap \operatorname{conv}(\{z\} \cup F(z)) \neq \varnothing$, which contradicts (2). So $f$ satisfies the conditions of Lemma 1, and therefore there exists $x_* \in B(0,1)$ such that $f(x_*)=a$. However, this is impossible by (3).
Lemma 2 is proved. § 3. Results for starlike domainsThe results in this section are related to combinatorial geometry; they are close to [24] in spirit. Recall that a domain $U \subset \mathbb{R}^d$ is starlike with respect to $0$ if $\lambda U \subset U$ for all $\lambda \in (0,1)$ and $0 \in U$. Let $U$ be a domain starlike with respect to $0$, and let $ p_u$ be its Minkowski functional, namely,
$$
\begin{equation*}
p_u\colon \mathbb{R}^d \to \mathbb{R}_+, \qquad x \mapsto \sup\bigl\{ \lambda \geqslant 0\colon \lambda x \in U\bigr\}.
\end{equation*}
\notag
$$
Traces of the following definition can be found in [25], Remark 2. Definition 3. Let $U \subset \mathbb{R}^d$ be a bounded starlike domain with respect to $0$. Given a point $x \in \mathbb{R}^d$ and a closed set $M \subset \mathbb{R}^d$, we set Note that
$$
\begin{equation*}
P^u_M(x) \neq \varnothing\quad\text{and} \quad M \cap U(x, d_u(x,M))= \varnothing,
\end{equation*}
\notag
$$
since $M$ is closed and $U$ is open. However, in general, the equality $M \cap \overline{U}(x,\lambda)=\varnothing$ need not hold for all $\lambda \in (0, d_u(x,M)) $. Recall that a function $f\colon \mathbb{R}^d \to \mathbb{R}$ is said to be upper semicontinuous on $\mathbb{R}^d$ if $\varlimsup_{x \to x_0} f(x) \leqslant f(x_0)$ for all $x_0 \in \mathbb{R}^d$. Lemma 3. Let $U \subset \mathbb{R}^d$ be a bounded starlike domain with respect to $0$ and let $M$ be a nonempty closed subset of $\mathbb{R}^d$. Then 1) the function $d_u(\,\cdot\,, M)$ is upper semicontinuous on $\mathbb{R}^d$; 2) the set-valued map $P^u_M$ is upper semicontinuous on $\mathbb{R}^d$. Proof. 1) Let $x \in \mathbb{R}^d$. We claim that the function $d_u(\,\cdot\, , M)$ is upper semicontinuous at $x$. In other words, we need to show that, for each sequence $x_n \to x$, $n\to\infty$,
$$
\begin{equation*}
d_u(x,M) \geqslant \varlimsup_{n \to \infty} d_u(x_n,M) =: r.
\end{equation*}
\notag
$$
Assume on the contrary that $d_u(x,M) < r$. Hence $M \cap U(x,r) \neq \varnothing$. We choose $y \in M \cap U(x,r)$ and set $z := (y-x)/r \in U$. It is clear that $y=x+r z$. Let $\varepsilon > 0$ be such that We also set $r_n := d_u(x_n,M)$. The above inclusion is invariant under homothetic transformations and translations, so
$$
\begin{equation}
B(x_n+r_n z, 4 r_n \varepsilon ) \subset (x_n+r_n U )=U(x_n,r_n).
\end{equation}
\tag{5}
$$
We choose $n$ so that
$$
\begin{equation*}
\| x-x_n\| < r \varepsilon\quad\text{and} \quad |r-r_n| < \min\biggl(\frac{r \varepsilon}{\| z \|+1}, \frac{r}{4}\biggr).
\end{equation*}
\notag
$$
In this case we have the estimate
$$
\begin{equation*}
\| x+r z -(x_n+r_n z)\| \leqslant \| x-x_n \|+\| (r-r_n)z \| < 2 r \varepsilon, \qquad r_n > \frac{3r}{4}.
\end{equation*}
\notag
$$
Using the last two inequalities and (5) we obtain Hence however, $y \in M \cap B(y, r \varepsilon)$ because $y$ has been chosen in $M \cap U(x,r)$. Therefore, $M \cap U(x,r)=\varnothing$, and so $d_u(x, M) \geqslant r$. This proves the first assertion of the lemma.
2) We claim that the set-valued mapping $P^u_M$ is upper semicontinuous at $x$. To prove this it suffices to show that if $x_n \to x$ as $n\to\infty$, $y_n \in P^u_M(x_n)$, and $y_n \to y$ as $n\to\infty$, then $y \in P^u_M(x)$. Passing to subsequences we can assume without loss of generality that $r_{n} := d_u(x_{n}, M) \to r$. The sets $\overline{U}(x_{n},r_{n})$ converge to $\overline{U}(x,r)$ in the Hausdorff metric. Hence $y \in \overline{U}(x,r)$. In addition, $y \in M$ because $y_n \in M$ and since $M$ is closed. On the other hand, since $d_u(\cdot,M)$ is upper semicontinuous, we have $R := d_u(x,M) \geqslant r$. Therefore, $y \in \overline{U}(x,R) \cap M$, that is, $y \in P^u_M(x)$. Lemma 3 is proved. As a direct corollary to Lemmas 2 and 3 we have the following. Theorem 1. Let $U \subset \mathbb{R}^d$ be a bounded starlike domain with respect to $0$, let ${M \subset \mathbb{R}^d}$ be a closed set, and let $a, b \in \mathbb{R}^d$ and $r > 0$ be such that $a \in B(b,r)$ and $a \notin \operatorname{conv}(\{x\} \cup P^u_M(x))$ for all $x \in S(b,r)$. Then there exists $x_* \in \mathbb{R}^d$ such that $a \in \operatorname{conv}(P^u_M(x_*))$. Under additional constraints on a set $M$ and a domain $U$, the above result can be refined as follows. Theorem 2. Let $U \subset \mathbb{R}^d$ be a bounded starlike domain with respect to $0$, let $\partial U$ be a $C^1$-smooth closed $(d-1)$-dimensional manifold, and let $M \subset \mathbb{R}^d$ be compact. Then $\operatorname{ri}(\operatorname{conv} M) \subset \bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P^u_M(x))$ and $\operatorname{conv} M=\overline{\bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P^u_M(x))}$. Proof. 1) First we show that $\operatorname{ri}(\operatorname{conv} M)\,{\subset} \bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P^u_M(x))$.
Consider the case when $\operatorname{aff} M= \mathbb{R}^d$. Then
$$
\begin{equation*}
\operatorname{ri} (\operatorname{conv} M)=\operatorname{int} (\operatorname{conv} M).
\end{equation*}
\notag
$$
Let $a \in \operatorname{ri} (\operatorname{conv} M) \setminus M$. We can find $a_1, \dots, a_\nu \in M$ and $\delta \in (0,1)$ such that
$$
\begin{equation}
B(a, 3\delta) \subset \operatorname{conv}(\{a_1, \dots, a_\nu\}), \qquad B(a, 3\delta) \cap M=\varnothing.
\end{equation}
\tag{6}
$$
We claim that there exists a point $x_* \in \mathbb{R}^d$ such that $a \in \operatorname{conv}(P^u_M(x_*))$. By Theorem 1, to prove this it suffices to find $R > 0$ such that
$$
\begin{equation*}
a \notin \operatorname{conv}(\{x\} \cup P^u_M(x)) \quad \forall\, x \in S(0,R).
\end{equation*}
\notag
$$
Let $V \subset \mathbb{R}^d$ be a bounded starlike domain, and let $\partial V$ be a $C^1$-smooth closed $(d-1)$-dimensional manifold. Given a point $y \in \partial V$, we denote the unit outward normal vector to $V$ at $y$ by $N_{\partial V}(y)$. We also consider the half-space
$$
\begin{equation}
\Pi_{\partial V}(y, t):= \bigl\{ x \in \mathbb{R}^d\colon \langle x, N_{\partial V}(y)\rangle \leqslant\langle y, N_{\partial V}(y)\rangle-t \bigr\}.
\end{equation}
\tag{7}
$$
The diameter of $M$ is defined by
$$
\begin{equation*}
\operatorname{diam}(M)=\sup\{ \| y-y' \|\colon y, y' \in M \}.
\end{equation*}
\notag
$$
Since $\partial U$ is $C^1$-smooth and compact, there exists $\lambda_0 > 0$ such that, for all $\lambda \geqslant \lambda_0$ and $y \in \partial U$,
$$
\begin{equation}
\lambda \overline{U} \cap \overline{B}(\lambda y, \operatorname{diam}(M) ) \subset \Pi_{\lambda \partial U}(\lambda y, -\delta) \cap \overline{B}(\lambda y, \operatorname{diam}(M) )
\end{equation}
\tag{8}
$$
and
$$
\begin{equation}
\lambda U \cap \overline{B}(\lambda y, \operatorname{diam}(M) ) \supset \Pi_{\lambda \partial U}(\lambda y, \delta) \cap \overline{B}(\lambda y, \operatorname{diam}(M) ).
\end{equation}
\tag{9}
$$
Next, there exists $R > 0$ such that
$$
\begin{equation}
d_u(x,M) \geqslant \lambda_0 \quad \forall\, x \in S(0,R).
\end{equation}
\tag{10}
$$
We prove that
$$
\begin{equation*}
B(a,\delta) \cap \operatorname{conv}(\{x\} \cup P^u_M(x))=\varnothing \quad \forall\, x \in S(0,R).
\end{equation*}
\notag
$$
Assume the contrary. Consider an arbitrary $b \in B(a,\delta) \cap \operatorname{conv}(\{x\} \cup P^u_M(x))$ and take $y_1, \dots, y_m \in P^u_M(x)$ such that $b \in \operatorname{conv}(\{x, y_1, \dots, y_m \})$. We also set It is clear that $\partial U'$ is homothetic to $\partial U$ and $y_1, \dots, y_m \in \partial U'$. Consider
$$
\begin{equation*}
N(y_1) := N_{\partial U'}(y_1)\quad\text{and} \quad \Pi(y_1,t) := \Pi_{\partial U'}(y_1, t).
\end{equation*}
\notag
$$
Since $U'$ is a starlike domain with respect to the point $x$, we have $x \in \Pi(y_1, 0)$, and therefore $x \in \Pi(y_1, -\delta)$. Substituting $\lambda U=U'-x$ and $\lambda y=y_1-x$ into (8) and (9) and adding $x$ to the resulting expressions we obtain
$$
\begin{equation}
\overline{U'} \cap \overline{B}(y_1, \operatorname{diam}(M) ) \subset \Pi(y_1, -\delta) \cap \overline{B}(y_1, \operatorname{diam}(M) )
\end{equation}
\tag{11}
$$
and
$$
\begin{equation}
U' \cap \overline{B}(y_1, \operatorname{diam}(M) ) \supset \Pi(y_1, \delta) \cap \overline{B}(y_1, \operatorname{diam}(M) ).
\end{equation}
\tag{12}
$$
It is clear that $\| y_1-y_i \| \leqslant \operatorname{diam}(M)$ for all $i=1, \dots, m$. Hence (11) implies that $y_i \in \Pi(y_1,-\delta)$. As a result, $\operatorname{conv}\{x, y_1, \dots, y_m\} \subset \Pi(y_1,-\delta)$, and therefore ${b \in \Pi(y_1,-\delta)}$. Consequently, $c := b-2\delta N(y_1) \in \Pi(y_1, \delta)$. It is clear that ${c\in B(a, 3\delta)}$, and now it follows from (6) that some of the points $a_1, \dots, a_\nu$ also lie in $\Pi(y_1,\delta)$. Without loss of generality we can assume below that $a_1 \in \Pi(y_1,\delta)$. On the other hand, since $M \subset \overline{B}(y_1, \operatorname{diam}(M))$, using (12) we obtain which, however, is impossible, because $U' \cap M=\varnothing$ and $a_1 \in \Pi(y_1,\delta) \cap M$.
Now consider the case when $\operatorname{aff} M \neq \mathbb{R}^d$. We can assume without loss of generality that $0 \in M$, that is, $\operatorname{aff} M= \operatorname{span} M$. We set $l:= d-\dim (\operatorname{span} M) > 0$. It is clear that there exists a set $W=\{w_1, \dots, w_l\}$, where $w_1, \dots, w_l \in \mathbb{R}^d$, such that
$$
\begin{equation}
\operatorname{aff} (M \cup W)=\operatorname{span} (M \cup W)=\mathbb{R}^d.
\end{equation}
\tag{13}
$$
By what has already been proved, for each point $a \in \operatorname{ri}(\operatorname{conv} M)$ and
$$
\begin{equation}
b := \frac{a}{2}+\frac{1}{2l}(w_1+\dots+w_l) \in \operatorname{int}(\operatorname{conv}(M \cup W))
\end{equation}
\tag{14}
$$
there exists $x_* \in \mathbb{R}^d$ such that Therefore, we have where
$$
\begin{equation*}
\lambda \in [0,1], \qquad y \in \operatorname{conv}(P^u_{M \cup W}(x_*) \cap M )\quad\text{and} \quad w \in \operatorname{conv}(P^u_{M \cup W}(x_*) \cap W).
\end{equation*}
\notag
$$
Since $\dim{(\operatorname{span}{M})}+\dim{(\operatorname{span}{W})}=n$, we have $\operatorname{span}{M} \cap \operatorname{span}{W}=\{ 0\}$. Now (14) implies that
$$
\begin{equation*}
\lambda=\frac{1}{2}, \qquad y=a\quad\text{and} \quad w=\frac{w_1+\dots+w_l}{l}.
\end{equation*}
\notag
$$
As a result,
$$
\begin{equation*}
a \in \operatorname{conv}(P^u_{M \cup W}(x_*) \cap M)=\operatorname{conv}(P^u_{M}(x_*)),
\end{equation*}
\notag
$$
as claimed.
2) Let us now prove the equality $\operatorname{conv} M=\overline{\bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P^u_M(x))}$. Since $M$ is compact, we have $\operatorname{conv} M=\overline{\operatorname{ri}(\operatorname{conv} M)} \subset \overline{\bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P^u_M(x))}$. It is clear that the reverse inclusion also holds because $\operatorname{conv}(P^u_M(x) ) \subset \operatorname{conv} M$ for all $x \in \mathbb{R}^d$. Theorem 2 is proved. Remark 1. Under the hypotheses of Theorem 2, for each $d \geqslant 2$ there exists a compact set $M \subset \mathbb{R}^d$ such that $\operatorname{conv} M \neq \bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P^u_M(x))$. Proof. As $U$ we take the Euclidean ball $B(0,1)$ in $\mathbb{R}^d$. Let $e_1, \dots, e_d$ be an orthonormal basis for $\mathbb{R}^d$, and let $M=\overline{B}(e_2,1) \cup \overline{B}(-e_2,1)$. Then $P^u_M$ is the metric projection $P_M$ in the Euclidean space $\mathbb{R}^d$. It is clear that $(e_1 \pm e_2) \in M$, since $e_1 \in \operatorname{conv} M$. It is easily seen that if $e_1 \in \operatorname{conv}(P_M(x))$, then $P_M(x)=\{e_1+e_2, e_1-e_2 \}$. Hence the ball $\overline{B}(x, \| x-e_2\|-1)$ touches the balls $\overline{B}(e_2,1)$ and $\overline{B}(-e_2,1)$ at the points $e_1+e_2$ and $e_1-e_2$, respectively. Now one can draw a straight line through each triple of points $\{e_2, e_1+e_2, x\}$ and $\{-e_2, e_1-e_2, x\}$ (here it is important that the space $\mathbb{R}^d$ is Euclidean). Clearly, these two straight lines intersect at $x$. On the other hand, the straight lines through the pairs of points $\{e_2, e_1+e_2 \}$ and $\{-e_2, e_1 -e_2 \}$, are parallel. This contradiction completes the proof. Corollary 1. Let $U \subset \mathbb{R}^d$ be a bounded starlike domain with respect to $0$, let $\partial U$ be a $C^1$-smooth closed $(d-1)$-dimensional manifold, and let $M \subset \mathbb{R}^d$ be a compact set. Assume that $|P^u_M(x)| \leqslant k$ for all $x \in \mathbb{R}^d$. Then $\operatorname{conv} M=\operatorname{conv}_k M$. Proof. By Theorem 2 and therefore, since $|P^u_M(x)| \leqslant k$, we have
The reverse inclusion is clear. So we have shown that $\overline{\operatorname{conv} M}=\overline{\operatorname{conv}_k M}$. The set $M$ is compact, hence the sets $\operatorname{conv} M$ and $\operatorname{conv}_k M$ are closed. Therefore, $\operatorname{conv} M=\operatorname{conv}_k M$. This proves Corollary 1. § 4. Results for convex domainLet $U$ be a bounded convex domain in a Banach space $X$, let $0 \in U$, and let $p_u$ be the Minkowski functional of $U$. It is clear that there exist $c_1$, $c_2 > 0$ such that
$$
\begin{equation*}
c_1 \| x \| \leqslant p_u(x) \leqslant c_2 \| x \| \quad \forall x \in X.
\end{equation*}
\notag
$$
We recall (see [26], § 2.4.7) that a convex domain $U$ is smooth if the Minkowski functional $p_u$ is Gâteaux differentiable on $X \setminus \{ 0 \}$, that is, for each $x \in X \setminus \{ 0 \}$ there exists a continuous linear functional $p'_u(x;\cdot) \in X^*$ such that for any $h \in X$ the limit exists. The modulus of smoothness of a convex body $U$ is defined by
$$
\begin{equation*}
\omega_u(t)=\sup\biggl\{ \frac{1}{2}(p_u(x+y)+p_u(x-y)-2)\colon x \in \partial U, \, y \in X, \, p_u(y)=t \biggr\}.
\end{equation*}
\notag
$$
A convex body $U$ is said to be uniformly smooth if its Minkowski functional $p_u$ is uniformly Fréchet differentiable on $U$, that is, (15) holds uniformly for $x \in \partial U$, $h \in U$. It is known (see [26], § 2.4.7) that the modulus of smoothness of a uniformly smooth body $U$ satisfies $\omega_u(t)=o(t)$ as $t \searrow 0$. Let $x \in \partial U$ and let $\Pi_x$ be the support hyperplane to $U$ at $x$. Then $p_u(x+y)-1 \geqslant 0$ and $p_u(x-y)-1 \geqslant 0$ for all $y \in \Pi_x-x$. Hence
$$
\begin{equation}
\sigma(t) := \sup\bigl\{ p_u(x+y)-1\colon x \in \partial U, \, y \in \Pi_x-x, \, p_u(y) \leqslant t \bigr\}=o(t), \qquad t \to 0.
\end{equation}
\tag{16}
$$
For $x \in \partial U$ let $f_x \in S_{X^*}$ be the support functional to $U$ at $x$. We claim that, for each $\varepsilon \in (0,c_1)$, there exists a positive $\delta=o(\varepsilon)$, $\varepsilon \searrow 0$, such that
$$
\begin{equation}
\bigl\{ z \in X\colon f_x(z) \leqslant f_x(x)-\delta \bigr\} \cap \overline{B}(x, \varepsilon) \subset U \cap \overline{B}(x, \varepsilon) \quad \forall\, x \in \partial U.
\end{equation}
\tag{17}
$$
Let $\varepsilon $ and $\delta $ be some positive numbers. We represent each point $z \in B(x, \varepsilon)$ such that $f_x(z) \leqslant f_x(x)-\delta$ as follows:
$$
\begin{equation*}
z=(1-\tau)x+y, \quad\text{where}\quad \tau \geqslant \frac{\delta}{f_x(x)}\quad\text{and} \quad y \in (\Pi_x-x).
\end{equation*}
\notag
$$
Now by (16) we have
$$
\begin{equation*}
p_u(z)=p_u((1-\tau)x+y)=(1-\tau) p_u\biggl(x+\frac{y}{1-\tau}\biggr) \leqslant 1-\tau+ \sigma(p_u(y))
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\tau=\tau p_u(x) \leqslant \tau p_u\biggl(x-\frac{y}{\tau}\biggr)=p_u(\tau x-y)=p_u(x-z) \leqslant c_2 \| x-z \| \leqslant c_2 \varepsilon.
\end{equation*}
\notag
$$
Since $z \in B(x, \varepsilon)$, we have $\| y \| \leqslant \| z-x\|+\tau \| x \| \leqslant \varepsilon+\tau/ c_1$, and therefore
$$
\begin{equation}
p_u(y) \leqslant c_2 \| y \| \leqslant c_2 \varepsilon+\tau \frac{c_2}{c_1} \leqslant \biggl(c_2+\frac{c_2^2}{c_1}\biggr) \varepsilon =: C \varepsilon.
\end{equation}
\tag{18}
$$
It is clear that for each $\varepsilon > 0$ one can choose $\delta=\delta(\varepsilon) > 0$ so that $c_1 \delta > \sigma(C \varepsilon)$ and $\delta=o(\varepsilon)$ as $\varepsilon \searrow 0$. By (18) and since $f_x(x) \leqslant \| x \| \leqslant 1/c_1$, for $\delta= \delta(\varepsilon)$ we have
$$
\begin{equation*}
p_u(z) \leqslant 1-\tau+\sigma(p_u(y)) \leqslant 1-\frac{\delta}{f_x(x)}+\sigma(C\varepsilon) \leqslant 1-c_1 \delta+\sigma(C \varepsilon) < 1.
\end{equation*}
\notag
$$
Therefore, $z \in U$. This proves (17). Note that in each smooth convex body a finite-dimensional space is uniformly smooth. Theorem 3. Let $U \subset \mathbb{R}^d$ be a bounded smooth convex domain such that $0 \in U$, and let $M \subset \mathbb{R}^d$ be closed. Then Proof. 1) First let us show that $\operatorname{ri}(\operatorname{conv} M)\,{\subset} \bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P_M(x))$. Consider the case when $\operatorname{aff} M= \mathbb{R}^d$. Then
$$
\begin{equation*}
\operatorname{ri} (\operatorname{conv} M)=\operatorname{int} (\operatorname{conv} M).
\end{equation*}
\notag
$$
Let $a \in \operatorname{ri} (\operatorname{conv} M) \setminus M$. Then there exist points $a_1, \dots, a_\nu \in M$ and $\delta \in (0,1)$ such that
$$
\begin{equation}
B(a, 2\delta) \subset \operatorname{conv}(\{a_1, \dots a_\nu\})\quad\text{and} \quad B(a, 2\delta) \cap M=\varnothing.
\end{equation}
\tag{19}
$$
We claim that there exists a point $x_* \,{\in}\, \mathbb{R}^d$ such that $a \!\in\! \operatorname{conv}(P_M(x_*))$. By Lemma 3 the map $P_M^u$ is upper semicontinuous. Now, in view of Theorem 1, in order to show that the required point $x_*$ exists it suffices to find $R > 0$ such that
$$
\begin{equation*}
a \notin \operatorname{conv}(\{x, P_M^u(x)\}) \quad \forall\, x \in S(0,R).
\end{equation*}
\notag
$$
We set $R_a :=\max_{i=1, \dots, \nu}\| a-a_i \|$. Now we recall the definitions of the unit outward normal vector $N_{\partial V}(y)$ and the half-space $\Pi_Y(y,t)$ introduced in the proof of Theorem 2 (see (7)). Since $U$ is uniformly smooth, we have (17). Hence there exists $\lambda_0 > 0$ such that, for all $\lambda \geqslant \lambda_0$ and all $y \in \lambda \partial U$,
$$
\begin{equation}
\Pi_{\lambda \partial U}(y, \delta) \cap \overline{B}(y, R_a +1 ) \subset U(0,\lambda) \cap \overline{B}(y, R_a +1 ).
\end{equation}
\tag{20}
$$
Let $R > 0$ be such that
$$
\begin{equation*}
p_u( a-x) > \lambda_0+\sup_{z \in B(a,\delta)} p_u(a-z) \quad \forall\, x \in S(0,R).
\end{equation*}
\notag
$$
We show that
$$
\begin{equation}
B(a, \delta) \cap \overline{U}(x, d_u(x,M))=\varnothing \quad \forall\, x \in S(0,R).
\end{equation}
\tag{21}
$$
Assume the contrary. Let $b \in B(a,\delta) \cap \overline{U}(x, d_u(x,M))$. It is clear that in this case $U(x, p_u(b-x)) \cap M=\varnothing$. Set $U' := U(x, p_u(b-x))$. Since from (20) we obtain
$$
\begin{equation*}
\Pi_{\partial U'} (b, \delta) \cap \overline{B}(b,R_a +1) \subset U' \cap \overline{B}(b, R_a +1).
\end{equation*}
\notag
$$
The inclusion $\overline{B}(a,R_a) \subset \overline{B}(b, R_a+1)$ is straightforward, hence
$$
\begin{equation}
\Pi_{\partial U'} (b, \delta) \cap \overline{B}(a,R_a) \subset U' \cap \overline{B}(a, R_a).
\end{equation}
\tag{22}
$$
We set $c := b-\delta N_{\partial U'}(b) \in \Pi_{\partial U'}(b,\delta)$. Since $b \in B(a,\delta)$, we find that
$$
\begin{equation*}
c \in B(a,2\delta) \subset \operatorname{conv}( \{a_1, \dots, a_\nu\}).
\end{equation*}
\notag
$$
Consequently, the half-space $\Pi_{\partial U'} (b, \delta)$ contains the point $c$ and one of the points $a_1, \dots, a_\nu$. We can assume without loss of generality that $a_1 \in \Pi_{\partial U'} (b, \delta)$. It is clear from the definition of $R_a$ that $a_1 \in \overline{B}(a,R_a)$. Hence
$$
\begin{equation}
a_1 \in \Pi_{\partial U'} (b, \delta) \cap \overline{B}(a,R_a).
\end{equation}
\tag{23}
$$
On the other hand $a_1 \in M$, and so $a_1 \notin U'$, which implies that It is clear that (23) and (24) are in contradiction to (22). This therefore proves (21). As a result, $B(a,\delta) \cap \operatorname{conv}( \{ x\} \cup P_M^u(x) )=\varnothing$ for all $x \in S(0,R)$. This completes the case when $\operatorname{aff} M=\mathbb{R}^d$.
The case when $\operatorname{aff} M \neq \mathbb{R}^d$ can be reduced to $\operatorname{aff} M=\mathbb{R}^d$ as in Theorem 2. 2) We claim that $\overline{\operatorname{conv} M}=\overline{\bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P_M^u(x))}$. By $1)$ we have $\overline{\operatorname{conv} M}=\overline{\operatorname{ri}(\operatorname{conv} M)} \subset \overline{\bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P^u_M(x))}$. It is clear that the reverse inclusion also holds, since $\operatorname{conv}(P^u_M(x) ) \subset \operatorname{conv} M$ for all $x \in \mathbb{R}^d$. Theorem 3 is proved. Remark 2. For a closed unbounded set $M$, in general $\operatorname{conv} M \neq \overline{\operatorname{conv} M} $ and therefore $\operatorname{conv} M \neq \overline{\bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P^u_M(x))}$, in contrast to the conclusion of Theorem 2. Corollary 2. Let $U \subset \mathbb{R}^d$ be a bounded smooth convex domain and $M \subset \mathbb{R}^d$ be a closed set with at most $k$-valued metric projection $P^u_M$. Then $\overline{\operatorname{conv} M}=\overline{\operatorname{conv}_k M}$. The proof is similar to the proof of Corollary 1. § 5. Infinite-dimensional resultsTheorem 4. Let $X$ be a Banach space, $U \subset X$ be a bounded uniformly smooth convex domain, and let $M \subset X$ be boundedly compact. Then Proof. Let $p_u$ be the Minkowski functional of $U$, and let $c_1$ and $c_2$, $c_1 < c_2$, be positive numbers such that
$$
\begin{equation}
c_1 \| x \| \leqslant p_u(x) \leqslant c_2 \| x \| \quad \forall x \in X.
\end{equation}
\tag{25}
$$
We assume without loss of generality that $c_2=1$ (for otherwise we can replace the norm $\| \cdot \|$ by $c_1 \| \cdot \|$). Let $a_1, \dots, a_\nu \in M$, $A := \{a_1, \dots, a_\nu\}$, and let ${a \in \operatorname{ri}(\operatorname{conv} A)}$. We claim that $a$ can be approximated arbitrarily well by points in $\bigcup_{x \in X}\operatorname{conv}(P^u_M(x))$. Given $Y \subset X$ and $t > 0$, we set
$$
\begin{equation}
Y_t := \bigl\{x \in X\colon d(x, Y) \leqslant t \bigr\}\quad\text{and} \quad Y^u_t := \bigl\{x \in X\colon d_u(x, Y) \leqslant t \bigr\}.
\end{equation}
\tag{26}
$$
Fix $\varepsilon \in (0,1/2)$. Since $U$ is uniformly smooth, (17) holds, and therefore here exists $\lambda_0 > 0$ such that for all $\lambda \geqslant \lambda_0$, all $y \in \lambda \partial U$ and any support functional $f_y \in S_{X^*}$ to $\lambda U$ at $y$ we have
$$
\begin{equation}
\bigl\{z\,{\in}\, X\colon f_y(z) \,{\leqslant}\, f_y(y)-\varepsilon \bigr\} \cap \overline{B}(y, \operatorname{diam}(A)+1) \,{\subset}\, U(0,\lambda) \cap \overline{B}(y, \operatorname{diam}(A)+1).
\end{equation}
\tag{27}
$$
Let $r > 0$ be such that
$$
\begin{equation*}
d_u(x, A_{2\varepsilon} \cup \{ a \}) \geqslant \lambda_0 \quad \forall\, x \in X \setminus B(0, r).
\end{equation*}
\notag
$$
We claim that
$$
\begin{equation}
a \notin \overline{U}(x, d_u(x,A_{2\varepsilon})) \quad \forall\, x \in X \setminus B(0,r).
\end{equation}
\tag{28}
$$
Assume the contrary. Then
$$
\begin{equation}
U(x, p_u(a-x)) \subset U(x, d_u(x, A_{2\varepsilon})).
\end{equation}
\tag{29}
$$
We denote the norm-one support functional to the domain $\overline{U}(x, p_u(a-x))$ at the point $a$ by $f_a$. For $t \in \mathbb{R}$ we set
$$
\begin{equation*}
\Pi(a, t)=\bigl\{z \in X\colon f_a(z) \leqslant f_a(a)-t \bigr\}.
\end{equation*}
\notag
$$
Hence by (27) we have
$$
\begin{equation}
\Pi(a, \varepsilon) \cap \overline{B}(a, \operatorname{diam}(A)+1) \subset U(x, p_u(a-x)) \cap \overline{B}(a, \operatorname{diam}(A)+ 1).
\end{equation}
\tag{30}
$$
It is clear that some points of $A$ also lie in the half-space $\Pi(a, 0)$. We can assume without loss of generality that $a_1 \in \Pi(a, 0)$, that is, $f_a(a_1) \leqslant f_a(a)$. Hence there exists $b_1 \in B(a_1, 2\varepsilon)$ such that $f_a(b_1) \leqslant f_a(a)-\varepsilon$. Since
$$
\begin{equation*}
\| b_1-a\| \leqslant \| b_1-a_1\|+\| a_1-a \| \leqslant 2\varepsilon+\operatorname{diam}(A) < 1+\operatorname{diam}(A),
\end{equation*}
\notag
$$
we have $b_1 \in \Pi(a, \varepsilon) \cap \overline{B}(a, \operatorname{diam}(A)+1)$. On the other hand $b_1 \notin U(x, p_u(a-x))$, since $A_{2\varepsilon} \cap U(x, p_u(a-x))= \varnothing$ in view of inclusion (29). But the existence of such $b_1$ contradicts (30). This therefore proves (28). Since $c_2=1$, from the definition (26) we obtain $A_{2\varepsilon} \subset A_{2c_2\varepsilon}^u= A_{2\varepsilon}^u$. Now (28) implies that
$$
\begin{equation}
a \notin \overline{U}(x, d_u(x,A^u_{2\varepsilon})) \quad \forall\, x \in X \setminus B(0,r).
\end{equation}
\tag{31}
$$
Next, from the definition of $P_M^u$ it is clear that the supremum
$$
\begin{equation}
\sup\bigl\{ \| y \|\colon y \in P_M^u(x), \,\| x \| \leqslant r \bigr\} =: R
\end{equation}
\tag{32}
$$
is finite. Since $M$ is boundedly compact, there exists an $\varepsilon$-net $x_1, \dots, x_m \in X$ for ${\overline{B}(0, R) \cap M}$. Let $L := \operatorname{span}\{x_1, \dots, x_m\}$. For $x \in L$ we set
$$
\begin{equation*}
D(x) := \overline{U}(x, d_u(x,M^u_{2\varepsilon})) \cap L
\end{equation*}
\notag
$$
and consider the set-valued mapping
$$
\begin{equation*}
\Phi\colon L \to 2^L \setminus \{\varnothing\}, \qquad x \mapsto P^u_{D(x)} \circ P_M^u(x).
\end{equation*}
\notag
$$
We claim that $\Phi$ is upper semicontinuous. To prove this it suffices to show that if $x_n \to x$ as $n\to\infty$, $z_n \in \Phi(x_n)$, and $z_n \to z$ as $n\to\infty$, then $z \in \Phi(x)$. By the definition of $\Phi$ there exist $y_n \in M$ such that Passing to a subsequence we can assume that $y_n \to y$ as $n\to\infty$ and, in addition, $y \in P^u_M(x)$, since the map $P_M^u$ is upper semicontinuous. The sets $D(x_n)$ tend to $D(x)$ in the Hausdorff metric, because the function $d_u(\, \cdot \,, M^u_{2\varepsilon})$ is continuous on $X$. Therefore, On the other hand $p_u(z_n-y_n) \to p_u(z-y)$ as $n\to\infty$. Hence $z \in P^u_{D(x)}(y)$, which implies that $z \in \Phi(x)$, as required.
Now consider the map
$$
\begin{equation*}
F\colon L \to \operatorname{Conv}(L), \qquad x \mapsto \operatorname{conv} \Phi(x).
\end{equation*}
\notag
$$
It is upper semicontinuous because $\Phi$ is. Note that for all $x \in L$
$$
\begin{equation*}
\operatorname{conv}( \{ x\} \cup F(x)) \subset D(x)=\overline{U}(x, d_u(x, M^u_{2\varepsilon})) \cap L \subset \overline{U}(x, d_u(x, A^u_{2\varepsilon})),
\end{equation*}
\notag
$$
so that by (31)
$$
\begin{equation*}
a \notin \operatorname{conv}( \{ x\} \cup F(x)) \qquad \forall\, x \in L \setminus B(0,r).
\end{equation*}
\notag
$$
Now by Lemma 2 there exists a point $x_* \in L \cap \overline{B}(0,r)$ such that Let $z_1, \dots, z_n \in \Phi(x_*)$ be points such that $a=\sum_{i=1}^n \lambda_i z_i$ for $ \lambda_i \geqslant 0$, $i=1,\dots,n$, $\sum_{i=1}^n{\lambda_i}=1$. Since $\Phi(x_*)=P^u_{D(x_*)} \circ P_M^u(x_*)$, there exist $y_i \in P_M^u(x_*)$ such that $z_i \in P^u_{D(x_*)}(y_i)$.
For each $i \in 1, \dots, n$ and all $z \in D(x_*)$, $\widetilde{z}_i \in P^u_L(y_i)$, we have
$$
\begin{equation}
p_u(z_i-y_i) \leqslant p_u(z-y_i) \leqslant p_u(z-\widetilde{z}_i)+p_u(\widetilde{z}_i-y_i).
\end{equation}
\tag{33}
$$
It is clear that
$$
\begin{equation}
p_u(\widetilde{z}_i-y_i)=d_u(y_i, L) \leqslant c_2 d(y_i, L)=d(y_i, L) \leqslant \varepsilon,
\end{equation}
\tag{34}
$$
because $y_i \in M \cap B(0,R)$ in view of (32) and since $L$ contains an $\varepsilon$-net for ${M \cap B(0,R)}$. Assume that $\widetilde{z}_i \notin D(x_*)$, that is, $p_u( \widetilde{z}_i-x_*) > d_u(x_*, M_{2\varepsilon}^u)$. Hence, for
$$
\begin{equation*}
z=x_*+d_u(x_*,M^u_{2\varepsilon})\frac{\widetilde{z}_i-x_*}{p_u(\widetilde{z}_i-x_*)}
\end{equation*}
\notag
$$
we have the estimate
$$
\begin{equation*}
\begin{aligned} \, p_u(\widetilde{z}_i-z) &=p_u(\widetilde{z}_i-x_*)-p_u(z-x_*)= p_u(\widetilde{z}_i-x_*)-d_u(x_*, M^u_{2\varepsilon}) \\ &\leqslant p_u(\widetilde{z}_i-y_i)+p_u( y_i-x_*)-d_u(x_*,M^u_{2\varepsilon}) \\ &\leqslant \varepsilon+d_u(x_*, M)-d_u(x_*, M^u_{2\varepsilon}) \leqslant 3\varepsilon. \end{aligned}
\end{equation*}
\notag
$$
Therefore,
$$
\begin{equation}
p_u(z-\widetilde{z}_i) \leqslant c_2\| z- \widetilde{z}_i\|=c_2\| \widetilde{z}_i-z \| \leqslant \frac{c_2}{c_1}p_u(\widetilde{z}_i- z) \leqslant \frac{3 \varepsilon}{c_1}.
\end{equation}
\tag{35}
$$
Now from (33)–(35) we obtain
$$
\begin{equation*}
\| z_i-y_i\| \leqslant \frac{p_u(z_i-y_i)}{c_1} \leqslant \frac{p_u(z- \widetilde{z}_i)}{c_1}+\frac{p_u(\widetilde{z}_i-y_i)}{c_1} \leqslant \frac{3\varepsilon}{c_1^2}+\frac{\varepsilon}{c_1} \leqslant \frac{4\varepsilon}{c_1^2}.
\end{equation*}
\notag
$$
If $\widetilde{z}_i \in D(x_*)$, then
$$
\begin{equation*}
p_u(z_i-y_i) =p_u(\widetilde{z}_i-y_i) \leqslant \varepsilon \quad \Longrightarrow \quad \| z_i-y_i \| \leqslant p_u(z_i-y_i) \leqslant \frac{\varepsilon}{c_1} < \frac{4\varepsilon}{c_1^2}.
\end{equation*}
\notag
$$
So, for $b=\sum_{i=1}^n \lambda_i y_i \in \operatorname{conv} P_M^u(x_*)$ we have
$$
\begin{equation*}
\| a-b\|=\biggl\| \sum_{i=1}^n \lambda_i (z_i-y_i)\biggr\| < \frac{4\varepsilon}{c_1^2} \sum_{i=1}^n \lambda_i=\frac{4\varepsilon}{c_1^2}.
\end{equation*}
\notag
$$
Since $\varepsilon$ can be chosen arbitrarily small, $a \in \overline{\bigcup_{x \in X}\operatorname{conv}(P_M^u(x))}$, and therefore $\operatorname{conv} M \subset \overline{\bigcup_{x \in X}\operatorname{conv}(P_M^u(x))}$. The reverse inclusion $\overline{\operatorname{conv} M} \supset \overline{\bigcup_{x \in X}\operatorname{conv}(P_M^u(x))}$ is clear.
Theorem 4 is proved. Corollary 3. Let $X$ be a Banach space, $U \subset X$ be a bounded uniformly smooth convex domain and $M \subset X$ be a compact set with at most $k$-valued metric projection $P_M^u$. Then $\overline{\operatorname{conv} M}=\overline{\operatorname{conv}_k M}$. Proof. By Theorem 4, $\overline{\operatorname{conv} M}=\overline{\bigcup_{x \in X}\operatorname{conv}(P^u_M(x))} \subset \overline{\operatorname{conv}_k M}$. The reverse inclusion $\overline{\operatorname{conv}_k M} \subset \overline{\operatorname{conv} M}$ is clear.
Corollary 3 is proved. Theorem 5. Let $X$ be a Banach space, $U \subset X$ be a bounded smooth convex domain and $M \subset X$ be a compact set. Then $\overline{\operatorname{conv} M}=\overline{\bigcup_{x \in X}\operatorname{conv}(P_M^u(x))}$. Proof. Let $p_u$ be the Minkowski functional of $U$. Let $c_1$ and $c_2$, $c_1 < c_2$, be the fixed positive numbers from (25). We can assume without loss of generality that $c_2 < 1$. Let $a_1, \dots, a_\nu \in M$, $A := \{a_1, \dots, a_\nu\}$, and let $a\,{\in} \operatorname{ri}(\operatorname{conv} A)$. We claim that $a$ can be approximated arbitrarily well by $\bigcup_{x \in X}\operatorname{conv}(P_M^u(x))$. Since $M$ is compact, there exists an $\varepsilon$-net $x_1, \dots, x_m \in X$ for $M$. Set
$$
\begin{equation*}
L := \operatorname{span}( A \cup \{x_1, \dots, x_m\}).
\end{equation*}
\notag
$$
It is clear that $V := U \cap L$ is a uniformly smooth convex domain in $L$, and it follows from the proof of Theorem 4 that there exits $r > 0$ such that
$$
\begin{equation*}
a \notin \overline{V}(x, d_u(x,A_{2\varepsilon}^u)) \quad \forall\, x \in L \setminus B(0,r)
\end{equation*}
\notag
$$
(see (31) and above). For $x \in L$ we set
$$
\begin{equation*}
D(x) := \overline{B}(x, d_u(x,M_{2\varepsilon}^u)) \cap L
\end{equation*}
\notag
$$
and consider the set-valued mapping
$$
\begin{equation*}
\Phi\colon L \to 2^L \setminus \{ \varnothing \}, \qquad x \mapsto P^u_{D(x)} \circ P_M^u(x).
\end{equation*}
\notag
$$
Arguing as in Theorem 4, it can be shown that there exist $x_* \in B(0,r) \cap L$ and $b \in \operatorname{conv} P_M^u(x_*)$ such that $\| a- b\| < 4\varepsilon/c_1^2$. It follows that $\overline{\operatorname{conv} M} \subset \overline{\bigcup_{x \in X}\operatorname{conv}(P_M^u(x))}$. The reverse inclusion $\overline{\bigcup_{x \in X}\operatorname{conv}(P_M^u(x))} \subset \overline{\operatorname{conv} M}$ is clear.
The theorem is proved. Corollary 4. Let $X$ be a Banach space, $U \subset X$ be a smooth convex domain and $M \subset X$ be a compact set. 1) If the metric projection $P^u_M$ is at most $k$-valued, then $\overline{\operatorname{conv} M}=\operatorname{conv} M=\operatorname{conv}_k M$. 2) If $\operatorname{conv} M$ is not closed, then for each $k$ there exists a point $x_k \in X$ such that $|P_M^u(x_k)| \geqslant k$. Proof. 1) By Theorem 4 We claim that the set $\operatorname{conv}_k M$ is closed. Indeed, if $x_n\,{\in} \operatorname{conv}_k M$ and $x_n \to x$ as ${n\to\infty}$, then for any natural $n$ there exist $y_{n}^i \in M$ (some of which can repeat) and $\lambda_n^{i} \geqslant 0$, $i=1, \dots, k$, $\sum_{i=1}^k \lambda_n^{i}=1$, such that Since $M$ is compact, there exists an increasing subsequence of indices $\{n_j\}_{j=1}^\infty \subset \mathbb{N}$ such that $y_{n_j}^{i} \to y^{i}$ and $\lambda_{n_j}^{i} \to \lambda^i$ as $j \to \infty$, for all $i=1, \dots, k$. It is clear that $x=\sum_{i=1}^k \lambda^i y^i \in \operatorname{conv}_k M$, and thus the set $\operatorname{conv}_k M$ is closed. Hence ${\overline{\operatorname{conv} M} \subset \operatorname{conv}_k M}$. The inclusion $\operatorname{conv}_k M \subset \operatorname{conv} M$ is clear. The last two inclusions imply that $\overline{\operatorname{conv} M}=\operatorname{conv} M= \operatorname{conv}_k M$.
Assertion 1) is immediate from 2). Corollary 4 is proved. § 6. Results for balls in Banach spacesIf as $U$ we take the unit ball $B(0,1)$ in a Banach space $X$, then $P_M^u$ is the ordinary metric projection $P_M$. Now the following result is immediate from Theorems 3–5. Theorem 6. Let $X$ be a Banach space, and let $M \subset X$. Then the following assertions hold. 1) If $X$ is a smooth finite-dimensional space and $M$ is boundedly compact, then $\operatorname{ri}(\operatorname{conv} M) \subset \bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P_M(x))$. 2) If $X$ is a uniformly smooth space and $M$ is boundedly compact, then $\overline{\operatorname{conv} M}=\overline{\bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P_M(x))}$. 3) If $X$ is smooth and $M$ is compact, then $\overline{\operatorname{conv} M}=\overline{\bigcup_{x \in \mathbb{R}^d} \operatorname{conv}(P_M(x))}$. Of course, similar results can also be derived from other theorems and corollaries presented in § 4 and § 5. The author is greatly indebted to P. A. Borodin for stating the problem and making valuable comments, and also to A. R. Alimov and I. G. Tsar’kov for helpful discussions. 
Citation in format AMSBIB
\Bibitem{Shk22} |
|
||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|