# Projection onto closed convex set

Show that the function defined by $f(t)=|P_{D}(x+td)-x|$ is nondecreasing, where $D$ is closed convex, $x\in D$, $t\geq 0$, $d\in \mathbb{R}^{n}$ and $P_{D}$ is projection onto D.

I tried to solve this question in a lot of ways, for example, if we use the polarization identity, we get $$\frac{1}{2}(|P_{D}(x+td)-x|^{2}-|P_{D}(x+sd)-x|^{2})= \\ \langle P_{D}(x+td)-x+P_{D}(x+sd)-x,P_{D}(x+td)-x-(P_{D}(x+sd)-x)\rangle$$ where $\langle,\rangle$ stands for the usual scalar product on $\mathbb R^{n}$. I tried to explore this equality, but i got nothing.

Here is some inequalities that maybe can help: if D is closed and convex then: $$<x-P_{D}(x),v-P_{D}(x)>\ \leq \ 0 \ \forall v\in D$$ $$<x-v,v-P_{D}(x)>\ \leq \ 0 \ \forall v\in D$$

I appreciate some help, this is a problem from my homework. Thanks

-
Eer...what is $\,P_D\,$?? –  DonAntonio Sep 23 '12 at 14:40
@DonAntonio I guess from the title that $P_D$ is the orthogonal projection onto $D$. –  Siminore Sep 23 '12 at 14:53

Suppose $v, w \in \mathbb{R}^n$ and let $z = P_D(w) - P_D(v)$. Then (using your first inequality) we have

$$\langle v, z \rangle \leq \langle P_D(v), z \rangle \leq \langle P_D(w), z \rangle \leq \langle w, z \rangle.$$

Now take $v = x + t_1d$ and $w = x + t_2d$ for some $t_2 > t_1 > 0$. Then these inequalities can be rewritten as

$$t_1 \langle d, z \rangle \leq \langle P_D(v) - x, z \rangle \leq \langle P_D(w) - x, z \rangle \leq t_2 \langle d, z \rangle.$$

This implies that $\langle d, z \rangle \geq 0$ and in particular

$$\langle P_D(v) - x, z \rangle \geq 0.$$

Then

$$||P_D(w) - x||^2 = ||P_D(v) - x + z||^2 = ||P_D(v)-x||^2 + 2 \langle P_D(v) - x, z\rangle + ||z||^2 \geq ||P_D(v)-x||^2.$$

-
Nice answer, thanks WimC. –  Tomás Oct 1 '12 at 12:37

Simplifications: we can assume that $x=0$ (since we could shift the whole picture by $-x$), so $0\in D$. Denote $P_t:=P_D(td)$ and $P_s:=P_D(sd)$, $\ 0<t<s$. We want to prove that $|P_s|^2 > |P_t|^2$, i.e. $$\langle P_s - P_t, P_s+P_t\rangle \ge 0$$ That's where I could get, also $t=1$ can be a simplification, but doesn't matter much. Now we can use that $0$, $P_s$, $P_t$ and $\displaystyle\frac{P_s+P_t}2$ are all in $D$. I think we are very near...

-
Did you get some result with this, because i tried this one too with no results. Im gonna edit my post and put some inequalities that are true for this case. The inequality u used can be taken as a definition of projection in this case (Closed Convex). –  Tomás Sep 24 '12 at 12:23
Not yet, I saw it at first glance that it is similar to your polarization, but then I also realized that not exactly the same. Anyway, is it clear, why those properties hold for $P_D$? Maybe the same method is useful. If I find something, post it, but I think, we're near.. –  Berci Sep 24 '12 at 15:34
The first property is an immediate consequence of the definition of projection. You can find it, for example, in the book of Brezis Functional Analysis. The other one is an exercise (consequence of the first one).In fact they are equivalent. –  Tomás Sep 24 '12 at 22:39