# "Pythagorean theorem" for projection onto convex set I'm going through the book on online convex op

"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?
You can still ask an expert for help

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

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.

We have step-by-step solutions for your answer!