4
$\begingroup$

Given a nonempty closed convex set $A\subset\mathbb R^n$, we know that for each $x\in\mathbb R^n$ there is a unique $p_A(x)\in A$ such that $$\|x-p_A(x)\|\le \|x-y\| \quad\forall y\in A.$$ The map $p_A:\mathbb R^n\to A$ is called the metric projection of $A$, and sends each $x$ to its unique nearest point in $A$.

One notable property of metric projections is that they are contracting, meaning that $$\|p_A(x)-p_A(y)\| \le \|x-y\|,\quad\forall x,y\in\mathbb R^n.$$ Geometrically, this is pretty clear from figures such as this:

$\hspace{100pt}$

One way to prove this, following Schneider's book (Theorem 1.2.1), is the following:

  1. Define $v\equiv p_A(y)-p_A(x)$, and assume $v\neq \mathbf 0$.
  2. Define $f(t)\equiv\|x-(p_A(x)+tv)\|^2$ for $t\ge0$.
  3. Observe that $f$ has a minimum at $t=0$ (clear from the definition of $p_A$) and thus $f'(0)=2\langle p_A(x)-x,v\rangle\ge0$.
  4. Doing the same replacing $x\to y$ we show that $\langle p_A(y)-y,v\rangle\le0$.
  5. Conclude that the segment $[x,y]$ crosses the two hyperplanes orthogonal to $v$ and passing through $p_A(x)$ and $p_A(y)$. The distance between these two hyperplanes is $\|p_A(x)-p_A(y)\|$, so this implies that $\|x-y\|$ must be larger than this, QED.

While this proof is fine, I was wondering if there is a "better" way to prove it that only relies on geometrical arguments. In particular, a proof that doesn't require to introduce a function such as $f$ and reason on its first derivative.

$\endgroup$
2
$\begingroup$

All the proofs that I have seen rely on similar arguments. However, there is one geometric element that can be better highlighted.

It is the fact that for $x \in V$ and $z \in A$ you have: $$\langle z - x, z - y \rangle \le 0$$ for any $y \in A$ if and only if $z$ is the orthogonal projection of $x$ onto $A$. Meaning that all the points in $A$ are on one side of the hyperplane passing through $p_A(x)$ and orthogonal to $p_A(x) -x$.

It is a pity that this is hidden in the proof provided.

From this result, you can get that the projection is contracting in the following way. You have

$$\begin{aligned} \Vert x - y \Vert^2 &= \Vert p_A(x) - p_A(y) + r \Vert^2 \text{ where } r= (x-y) + (p_A(x) - p_A(y)\\ &= \Vert p_A(x) - p_A(y) \Vert^2 + \Vert r \Vert^2 + 2 \langle r, p_A(x)-p_A(y) \rangle\\ &= \Vert p_A(x) - p_A(y) \Vert^2 + \Vert r \Vert^2\\ &+ \langle x-p_A(x), p_A(x)-p_A(y) \rangle + \langle y-p_A(y), p_A(y)-p_A(x) \rangle \end{aligned}$$

And you can conclude as $$\Vert r \Vert^2\\ + \langle x-p_A(x), p_A(x)-p_A(y) \rangle + \langle y-p_A(y), p_A(y)-p_A(x) \rangle \ge 0.$$

An image (courtesy of glS) describing what happens: enter image description here

$\endgroup$
4
  • $\begingroup$ if I'm reading this correctly, this is essentially another way to state that the supporting hyperplanes separate $A$ from its complementary, together with the fact that there is a supporting hyperplane passing through each $p_A(x)$ (which follows from the fact that there is a supporting hyperplane at every element of the boundary). I'm failing to see how this can be used for the proposition under exam though, as we here need to control two different points and their projections. $\endgroup$ – glS Aug 31 '20 at 15:14
  • $\begingroup$ I do agree with the first part of your comment. Regarding the second part, see my updated answer. $\endgroup$ – mathcounterexamples.net Aug 31 '20 at 15:27
  • $\begingroup$ very nice, thank you! I made a graphical representation of the construction, i.stack.imgur.com/LZ6pQ.png, if you want to add it to the post for better clarity. The gist, as I understand it, is to show that $x-p_A(x)$ and $y-p_A(y)$ point in diverging directions (which you can show using the statement you pointed out) which implies that the angle between $x-y$ and $r$ is obtuse $\endgroup$ – glS Sep 2 '20 at 9:20
  • $\begingroup$ Thanks. Image is indeed useful and I updated my answer using it. $\endgroup$ – mathcounterexamples.net Sep 2 '20 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.