sweetymoeyz

2022-07-07

"Pythagorean theorem" for projection onto convex set
I'm going through the book on online convex optimization by Hazan, and in the first chapter I saw this assertion (which Hazan calls the "pythagorean theorem"):
Let $K\subset {\mathbb{R}}^{d}$ be a convex set, $y\in {\mathbb{R}}^{d}$, and $x={\mathrm{\Pi }}_{K}\left(y\right)$. Then for any $z\in K$ we have:
$‖y-z‖\ge ‖x-z‖.$
It is presented without proof - what is a proof for this? Also, how does it relate to the pythagorean theorem?

potamanixv

Suppose x is the closest point to y in the closed convex set K.
If x=y there is nothing to prove, so we can suppose $x\ne y$.
The we have that $⟨x-y,z-x⟩\ge 0$ for all $z\in K$ (this is essentially the dual problem).
If $z\in K$, we can write $z-y=t\left(x-y\right)+d$, where $d\mathrm{\perp }\left(x-y\right)$. Then the above gives $⟨x-y,t\left(x-y\right)+d+y-x⟩=\left(t-1\right)‖x-y{‖}^{2}\ge 0$ from which we get $t\ge 1$.
Then $‖z-y{‖}^{2}=‖d{‖}^{2}+{t}^{2}‖x-y{‖}^{2}\ge ‖x-y{‖}^{2}$ which is the desired result.
Addendum: To see the first condition, suppose $‖z-y‖\ge ‖y-x‖$ for all $z\in K$.
We have $‖z-y{‖}^{2}=‖z-x+x-y{‖}^{2}=‖z-x{‖}^{2}+‖x-y{‖}^{2}+2⟨z-x,x-y⟩$ (this is where Pythagoras appears) which gives $‖z-x{‖}^{2}+2⟨z-x,x-y⟩\ge 0$ for all $z\in K$. Since $w\left(t\right)=x+t\left(z-x\right)\in K$ for all $t\in \left[0,1\right]$, we have ${t}^{2}‖z-x{‖}^{2}+2t⟨z-x,x-y⟩\ge 0$, dividing across by t and letting $t↓0$ yields the desired result.

Do you have a similar question?