Vtyjkyuk

I'm going through the book on online convex optimization by Hazan, (http://ocobook.cs.princeton.edu/OCObook.pdf) and in the first chapter I saw this assertion (which Hazan calls the "pythagorean theorem"):

Let $K subset mathbbR^d$ be a convex set, $y in mathbbR^d$, and $x = Pi_K(y)$. Then for any $z in K$ we have:
$$
|y - z | geq |x - z|.
$$

It is presented without proof - what is a proof for this? Also, how does it relate to the pythagorean theorem?

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 $xneq y$.

The we have that $langle x-y, z -x rangle ge 0$ for all $z in K$ (this is essentially the dual problem).

If $z in K$, we can write $z-y = t(x-y)+ d$, where $d bot (x-y)$. Then the above gives
$langle x-y, t(x-y)+ d +y -x rangle = (t-1)|x-y|^2ge 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 langle z-x,x-y rangle $ (this is where Pythagoras appears) which gives
$|z-x|^2 + 2 langle z-x,x-y rangle ge 0$ for all $z in K$.
Since $w(t)=x+t(z-x) in K$ for all $t in [0,1]$, we have
$t^2 |z-x|^2 + 2 t langle z-x,x-y rangle ge 0$, dividing across by $t$ and letting $t downarrow 0$ yields the desired result.

Relevant is the so-called "obtuse angle criterion":

Let $mathcal K subseteq mathbb R^d $ be a convex set, $mathbf y in mathbb R^d setminus mathcal K$, and $mathbf x = Pi_mathcal K(mathbf y)$ (that is, $mathbf x$ is the closest point in the set $mathcal K$ to $mathbf y$) . Then for any point $mathbf z in mathcal K$, the angle between $mathbf z-mathbf x$ and $mathbf y - mathbf x$ is obtuse or right.

(We assume that $mathbf x$ exists; it is guaranteed to exist if $mathcal K$ is closed and nonempty.)

It's often convenient to state this in inner-product form as

$$langle mathbf z - mathbf x, mathbf y - mathbf x rangle le 0.$$

To prove this, start by observing that for every $t in [0,1]$, $(1-t)mathbf x + t mathbf z in mathcal K$, and so the function $phi(t) = |(1-t)mathbf x + t mathbf z - mathbf y|^2$ is minimized on $[0,1]$ by $t=0$. Then do some calculus to $phi(t)$ to figure out when this happens, and the inner-product condition comes out as the result.

(We can expand $phi(t) = |mathbf y - mathbf x - t(mathbf z - mathbf x)|^2$ to $|mathbf y - mathbf x|^2 - 2t langle mathbf y - mathbf x, mathbf z - mathbf xrangle + t^2 |mathbf z - mathbf x|^2$. This parabola has vertex at $t = -fracb2a = fraclangle mathbf y - mathbf x, mathbf z - mathbf xrangle2$, and we want this to be less than or equal to $0$, giving us the obtuse angle criterion.)

The theorem that $|mathbf y - mathbf z| ge |mathbf x - mathbf z|$ is a geometric consequence of the obtuse angle criterion. Consider the triangle with vertices $mathbf x, mathbf y, mathbf z$. Then because the angle at $mathbf x$ is right or obtuse, it is the largest angle of the triangle. Therefore the opposite side of the triangle - the side from $mathbf y$ to $mathbf z$ - is its longest side.

I am guessing that this is where the connection to the Pythagorean theorem comes from. More precisely, we can deduce this inequality about triangles from the Law of Cosines, a generalization of the Pythagorean theorem. In a triangle $triangle ABC$, we have $$AB^2 = AC^2 + BC^2 - 2cdot AB cdot BC cdot cos angle C,$$ and if $angle C$ is right or obtuse, this implies that $AB^2 ge AC^2 + BC^2$. So in particular, $AB^2 ge AC^2$ and $AB^2 ge BC^2$: the side opposite $angle C$ is the longest side.

(Of course, the attribution of this result to Pythagoras is not serious.)