# Projection onto convex set and a translated version

Let $K \subseteq \mathbb{R}^n$ be a closed convex set containing the origin. Let $\Pi_K$ denote the Euclidean projection onto $K$.

I would like to show that for any fixed $x_0 \in K$, $$\sup_{x \in \mathbb{R}^n} \left|\|\Pi_K(x_0+x)-x_0\|^2 - \|\Pi_K(x)\|^2\right| < \infty, \tag{1}$$ or equivalently, $$\sup_{x \in \mathbb{R}^n} \left|\|\Pi_{K - \{x_0\}}(x)\|^2 - \|\Pi_K(x)\|^2\right| < \infty.$$

Note that $\|\Pi_K(x_0+x)-x_0\|^2$ can be rewritten as $\|\Pi_{K - \{x_0\}}(x)\|^2$ where $K-\{x_0\} := \{x-x_0 : x \in K\}$, so my question can be viewed as controlling the difference in the square lengths of the projections onto $K$ and a translated version $K-\{x_0\}$.

I do not know if this is true, but have not been able to either prove it or give a counterexample.

Note that this is a different statement than $$\sup_{x \in \mathbb{R}^n} \|\Pi_{K-\{x_0\}}(x) - \Pi_K(x)\|^2 < \infty.$$ I do not know if this implies or is implied by the previous claim. I also do not know if this is true or false.

They are related as follows: $$\|\Pi_{K - \{x_0\}}(x)\|^2 - \|\Pi_K(x)\|^2 = \|\Pi_{K-\{x_0\}}(x) - \Pi_K(x)\|^2 + 2\langle\Pi_{K-\{x_0\}}(x)-\Pi_K(x), \Pi_K(x)\rangle.$$

Any references/hints/suggestions are appreciated!

Update: although I am not able to parse HK Lee's justification, I believe his/her counterexample is correct. I have verified using a computer that $K=\{(x,y) : y \ge x^2\}$ and $x_0 = (0,1)$ does not satisfy (1) above because the expression tends to $\infty$ for $x=(n,n)$ as $n \to \infty$. (But showing this analytically is messy since one needs to solve a cubic.)

My hunch is that the increasing change in curvature is the culprit in the above counterexample, and I conjecture that (1) does hold if $K$ is a polyhedron (finitely many linear constraints). But maybe that is a question for another time.

$$K':=\{ (x,y)| y\geq f(x):=x^2-1 \}$$

Hence $${\bf o}:=(0,0),\ {\bf x}_0:=(-1,0)\in K'$$

Define $$\textbf{x}_n:=(-a_n,f(-a_n)),\ a_n>a_{n-1}>0,\ n\geq 1,\ \lim_n\ \frac{a_n-a_{n-1}}{a_{n+1}-a_n} =0$$

Consider tangent lines $l_n$ of $f$ at ${\bf x}_n$. Note that these lines and line $x=0$ enclose a closed convex set $K$.

If $\pi_n$ is an orthogonal projection onto $l_n$ and if $$f'(-a_n) := -\tan\ \bigg(\frac{\pi}{2}-\theta_n \bigg) =- \frac{\cos\ \theta_n}{\sin\ \theta_n} =-2a_n$$ then

\begin{align*} \pi_n ({\bf x}_n+{\bf x}_0 ) -{\bf x}_0&={\bf x}_n + (-\sin^2 \theta_n,\sin\ \theta_n\cos\ \theta_n) -{\bf x}_0 \\ &= (-a_n -\sin^2 \theta_n +1, a_n^2 -1+\sin\ \theta_n\cos\ \theta_n)\\&\\ |\pi_n ({\bf x}_n+{\bf x}_0 ) -{\bf x}_0|^2 &\approx-2a_n (1-\sin^2\theta_n) + a_n^4-a_n^2 (1 -2\sin\ \theta_n\cos\ \theta_n) \\ &\\ |{\bf x}_n|^2&\approx -a_n^2+a_n^4 \\&\\ |\pi_n ({\bf x}_n+{\bf x}_0 ) -{\bf x}_0|^2 - |{\bf x}_n|^2 &\approx-2a_n (1-\sin^2\theta_n) + 2a_n^2 \sin\ \theta_n\cos\ \theta_n \\&\approx -a_n (1-\sin^2 \theta_n) \end{align*}

• In my question there are squares on all the norms. – angryavian Mar 22 '17 at 3:40
• I do not see how this answers the question; can you please elaborate? – angryavian Mar 23 '17 at 5:52
• Yes. You are right. My answer is not complete. – HK Lee Mar 23 '17 at 5:56
• I give a counterexample – HK Lee Mar 23 '17 at 9:55