# “Pythagorean theorem” for projection onto convex set

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?

• The notes are a bit sloppy. The set $K$ should be closed to guarantee that a projection (as defined in Chapter 2, not 1 as you wrote above). It is a bit disingenuous to label the result as 500 BC. – copper.hat May 31 '18 at 4:51

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.

• @ copper.hat: Could you please explain the last two lines, especially getting the inequality in terms of $t$ from $w(t)$? Also, in Addendum, why do you need two inequalities, one without $t$ and one with $t$? – Saeed Aug 12 '18 at 1:56
• @Saeed: If you substitute $w(t)$ for $z$ in $\|z-x\|^2 + 2 \langle z-x,x-y \rangle \ge 0$ you will get the last inequality. Then divide by $t$ and let $t \to 0$. The goal is to show the first order condition of optimality, $\langle x-y, z -x \rangle \ge 0$ for all $z \in K$. – copper.hat Aug 12 '18 at 8:02

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.)

• Does the proof of the inner-product condition hold for arbitrary normed spaces? – Reginald May 31 '18 at 4:52
• @Reginald: An arbitrary normed space does not have an inner product. Also. there is not necessarily a unique closest point in an arbitrary normed space (take the $l_1$ norm in the plane for example). – copper.hat May 31 '18 at 5:35
• Rather, arbitrary IP space – Reginald May 31 '18 at 5:42
• @Reginald: The result holds for closed convex sets in a Hilbert space. – copper.hat May 31 '18 at 13:11
• Regarding uniqueness: for this result to hold, we need not assume $\mathbf x$ is the unique closest point, but a closest point. (Which implies uniqueness for closest points in convex sets, whenever they exist.) – Misha Lavrov May 31 '18 at 14:42