"Pythagorean theorem" for projection onto convex set

Question

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 \mathbb{R}^d$ be a convex set, $y \in \mathbb{R}^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?

Answer 1

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 x\rangle + t^2 \|\mathbf z - \mathbf x\|^2$. This parabola has vertex at $t = -\frac{b}{2a} = \frac{\langle \mathbf y - \mathbf x, \mathbf z - \mathbf x\rangle}{2\|\mathbf z - \mathbf x\|^2}$, 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 - 2\cdot 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.)

Answer 2

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\neq 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\|^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 \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.