7
$\begingroup$

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.

$\endgroup$
2
+50
$\begingroup$

$$ 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*}

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

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.