2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – copper.hat May 31 '18 at 4:51
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @ 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$? $\endgroup$ – Saeed Aug 12 '18 at 1:56
  • $\begingroup$ @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$. $\endgroup$ – copper.hat Aug 12 '18 at 8:02
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Does the proof of the inner-product condition hold for arbitrary normed spaces? $\endgroup$ – Reginald May 31 '18 at 4:52
  • $\begingroup$ @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). $\endgroup$ – copper.hat May 31 '18 at 5:35
  • $\begingroup$ Rather, arbitrary IP space $\endgroup$ – Reginald May 31 '18 at 5:42
  • $\begingroup$ @Reginald: The result holds for closed convex sets in a Hilbert space. $\endgroup$ – copper.hat May 31 '18 at 13:11
  • $\begingroup$ 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.) $\endgroup$ – Misha Lavrov May 31 '18 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.