0
$\begingroup$

I have to prove that if $A$ is convex and closed set, then $z=P_A(x)$ for all $z\in A$ if and only if $\langle x-z, z-y\rangle \geq 0$ for all $y\in A$

I have following proof which is not much complicated, but I don't understand few things.

If $g(\theta)=||x-((1-\theta)z+\theta y)||^2, \theta \in R, z=P_A(x), y\in A$ is quadratic function of the variable $\theta$ and it has minimum at $\theta =-\frac{\langle x-z,z-y\rangle}{||z-y||^2}$

Now there is a part that I don't understand:

For $z=P_A(x)$, from convexity of a set A, we get $g(0)\leq g(\theta)$ for all $\theta \in [0,1]$, so $\theta_{min} \leq 0$.

I know why $g(0)\leq g(\theta)$ (I can see it by simply putting $0$ in function), but I don't know how convexity of $A$ caused that and why did we take $\theta$ from $[0,1]$.

The rest of the proof is ok.

Would anybody try to make this clear to me?

$\endgroup$
2
$\begingroup$

If $z$ is the projection of $x$ to $A$, then it's the closest point to $x$ in $A$. If $y$ is any other point in $A$ and $0\leq\theta\leq 1$, then $(1-\theta)z+\theta y$ is in $A$ because $A$ is convex. (Notice that this would not follow if $\theta$ were outside $[0,1]$.) So the distance from $x$ to this point $(1-\theta)z+\theta y$ in $A$, must be at least the distance from $x$ to $z$. Square both sides of that inequality (because squared distances are algebraically nicer than distances in Euclidean space), and you get $g(\theta)\geq g(0)$. So $g(\theta)$, with $\theta$ restricted to $[0,1]$, takes its minimum value at $\theta=0$.

$\endgroup$
  • $\begingroup$ Ok, everything you wrote is now clear to me. But I wrote above that $\theta_{min} \leq 0$. Can it $\leq 0$ if we choose it from $[0,1]$? It's written so in the proof in the book. $\endgroup$ – user23709 Jun 11 '13 at 10:41
  • $\begingroup$ As far as I can tell, $\theta_{\text{min}}$ (which isn't defined in the material you quoted) is supposed to be the value of $\theta$ where the quadratic function $g(\theta)$ has its minimum value. It need not be in $[0,1]$; in fact, the only way it could be there is if it is $0$. What's involved here is that, if a quadratic function (in your case $g$) has a lower value at $0$ than elsewhere in $[0,1]$, then its minimum (the bottom of its parabola-shaped graph) must occur at a point $\leq0$. $\endgroup$ – Andreas Blass Jun 11 '13 at 16:17

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.