1
$\begingroup$

Given a compact subset $M$ of $\mathbb{R}^n$, the metric projection associated with $M$ is a function that maps each point $x\in \mathbb{R}^n$ to the nearest points in $M$, that is, $\arg \min_{y\in M} d(x,y)$, where $d$ is a distance function.

I am interested particularly in the case in which $d$ is the taxicab metric ($\ell_1$). In general there may be several nearest points, so the metric projection is a set-valued function. For example, if the set $M$ is the line with slope 1 through the origin, and $x$ is the point $(1,0)$, then the metric projection of $x$ into $M$ is the entire segment between $(0,0)$ and $(1,1)$.

My question concern the case in which the set $M$ is convex:

  • Does the set-valued metric projection have any continuity properties - e.g. is it hemicontinuous, upper-hemicontinuous, or lower-hemicontinuous?
  • Does there exist a single-valued selection from the metric projection (i.e., a single-valued function that always returns one point from the metric projection), which is a continuous function?

I found some papers on continuity of metric projections (there is also some text in Wikipedia), but they use very general terms, which I am not sure how to apply in my special case.

$\endgroup$
1
  • 1
    $\begingroup$ The projection is an implicitly defined mapping between $\mathbb{R}^n$ and $\mathbb{R}^n$ given by solving the first-order optimality conditions (which are set-valued since $d$ is not smooth). You can apply a set-valued implicit mapping theorem to this depending on the structure of $M$; look at something called the Aubin property (Lipschitz continuity for set-valued maps, basically). $\endgroup$ Commented Oct 11, 2024 at 12:01

1 Answer 1

1
+50
$\begingroup$

Let $n$ be any natural number, $X$ be the space $\mathbb R^n$, $M$ be a nonempty compact subset of the space $X$, and $p_M$ be the metric projection associated with $M$. As I understood the definition of upper hemicontinuity from Wikipedia, the function $p_M$ is upper hemicontinuous, that is for each $a\in X$ and each open set $V\supset p_M(a)$, there exists a neighbourhood $U$ of $a$ such that $p_M(x)\subset V$ for all $x\in U$.

Indeed, otherwise there exists a sequence $(a_n)_{n\in\mathbb N}$ of points of $X$ convergent to $a$ and a sequence $(b_n)_{n\in\mathbb N}$ such that $b_n\in p_M(a_n)\setminus V$ for each natural $n$. Since the set $M$ is a metric compact, taking a subsequence of the sequence $(a_n)_{n\in\mathbb N}$, if needed, we can suppose that the sequence $(b_n)_{n\in\mathbb N}$ converges to a point $b\in M$. Let $D=d(a,M)$, $D'=d(a,b)$, and for each natural $n$ let $D_n=d(a_n,M)$. The triangle inequality implies that $|D-D_n|=|d(a,M)-d(a_n,M)|\le d(a,a_n)$. Since the sequence $(a_n)_{n\in\mathbb N}$ converges to $a$, the sequence $(D_n)_{n\in\mathbb N}$ converges to $D$. For each natural $n$ we have $b_n\in p_M(a_n)$, so $d(a_n,b_n)=d(a_n,M)=D_n$. Since the sequence $(a_n)_{n\in\mathbb N}$ converges to $a$ and the sequence $(b_n)_{n\in\mathbb N}$ converges to $b$, the sequence $(D_n)_{n\in\mathbb N}=(d(a_n,b_n))_{n\in\mathbb N}$ converges to $d(a,b)=D'$. Thus $D'=D$ and thus $d(a,M)=d(a,b)$, so $d\in p_M(a)$, a contradiction.

For each $a\in X$ the set $p_M(a)$ is a convex compact as the intersection of the convex compact sets $M$ and the $\ell_1$-ball of radius $d(a,M)$ centered at $a$. Then according to Wikipedia, the set $p_M(a)$ is Chebyshev with respect to the Euclidean metric $d_E$ on $\mathbb R^n$, that is there exists a unique point $b(a)\in p_M(a)$ such that $d_E(a,b(a))=d_E(a,M)$.

Unfortunately, as I understood the definition of lower hemicontinuity from Wikipedia, the function $p_M$ can fail to be lower hemicontinuous. Namely, let $n=3$, $M$ be a cone, whose vertex is $(0,0,1)$ and base is the unit circle in the $xOy$ plane centered at $(2,0,0)$. Then $p_M(0,0,0)$ is the segment with the endpoints $(0,0,1)$ and $(1,0,0)$. Let $y>0$ and $P=(0,y,0)$. Let us study the set $p_M(P)$.

The distance $d(P,M)$ from the point $P$ to $M$ equals the distance from $P$ to the lateral surface of the cone $M$, whose points $Q$ can be parametrized as $(1-h)(0,0,1)+h(2+cos t,\sin t,0)$, $h\in [0,1]$, $t\in [0,2\pi]$. Then $d(P,Q)=1+h(1+\cos t)+|y-h\sin t|$. If $h=0$ then $d(P,Q)=1+y$. Otherwise the minimum of $d(P,Q)$ can be attained either when the partial derivative $d(P,Q)_t$ of $d(P,Q)$ with respect to $t$ either equals zero of does not exist.

In the first case we have $\cos t=\pm \sin t=\pm \frac{\sqrt{2}}2$. To minimize $d(P,Q)$ we need $-\cos t=\sin t=\frac{\sqrt{2}}2$. If $h\le \sqrt{2}y$ then $$d(P,Q)=1+h\left(1-\frac{\sqrt{2}}2\right)+y-h\cdot \frac{\sqrt{2}}2=1+h(1-\sqrt{2})+y$$ and its minimum $1+(\sqrt{2}-1)y$ is attained when $h=\sqrt{2}y$. If $h\le \sqrt{2}y$ then $$d(P,Q)=1+h\left(1-\frac{\sqrt{2}}2\right)+h\cdot \frac{\sqrt{2}}2-y=1+h+y$$ and its minimum $1+y$ is attained when $h=0$.

In the second case we have $y=h\sin t<h$, so $\cos t=\pm \sqrt{1-\left(\frac yh\right)^2}$. To minimize $d(P,Q)$ we need to choose the minus sign here. Then $$d(P,Q)=1+h\left(1-\sqrt{1-\left(\frac yh\right)^2}\right)=1+h-\sqrt{h^2-y^2}.$$ The partial derivative $d(P,Q)_t$ of $d(P,Q)$ with respect to $t$ equals $$1-\frac 1{\sqrt{1-\left(\frac yh\right)^2}}<0,$$ so to attain the minimum of $d(P,Q)$ we need to put $h=1$. Then $d(P,Q)=2-\sqrt{1-y^2}$.

From above we see that for the point $Q$, $h\in\{0,1\}$.

But even when the function $p_M$ is not lower hemicontinous, there still is a hope that it has a single-valued continuous selection. I am going to think about this more.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.