sweetymoeyz

2022-07-07

"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}(y)$. Then for any $z\in K$ we have:

$\Vert y-z\Vert \ge \Vert x-z\Vert .$

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

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}(y)$. Then for any $z\in K$ we have:

$\Vert y-z\Vert \ge \Vert x-z\Vert .$

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

potamanixv

Beginner2022-07-08Added 15 answers

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 $\u27e8x-y,z-x\u27e9\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\mathrm{\perp}(x-y)$. Then the above gives $\u27e8x-y,t(x-y)+d+y-x\u27e9=(t-1)\Vert x-y{\Vert}^{2}\ge 0$ from which we get $t\ge 1$.

Then $\Vert z-y{\Vert}^{2}=\Vert d{\Vert}^{2}+{t}^{2}\Vert x-y{\Vert}^{2}\ge \Vert x-y{\Vert}^{2}$ which is the desired result.

Addendum: To see the first condition, suppose $\Vert z-y\Vert \ge \Vert y-x\Vert $ for all $z\in K$.

We have $\Vert z-y{\Vert}^{2}=\Vert z-x+x-y{\Vert}^{2}=\Vert z-x{\Vert}^{2}+\Vert x-y{\Vert}^{2}+2\u27e8z-x,x-y\u27e9$ (this is where Pythagoras appears) which gives $\Vert z-x{\Vert}^{2}+2\u27e8z-x,x-y\u27e9\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}\Vert z-x{\Vert}^{2}+2t\u27e8z-x,x-y\u27e9\ge 0$, dividing across by t and letting $t\downarrow 0$ yields the desired result.

If x=y there is nothing to prove, so we can suppose $x\ne y$.

The we have that $\u27e8x-y,z-x\u27e9\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\mathrm{\perp}(x-y)$. Then the above gives $\u27e8x-y,t(x-y)+d+y-x\u27e9=(t-1)\Vert x-y{\Vert}^{2}\ge 0$ from which we get $t\ge 1$.

Then $\Vert z-y{\Vert}^{2}=\Vert d{\Vert}^{2}+{t}^{2}\Vert x-y{\Vert}^{2}\ge \Vert x-y{\Vert}^{2}$ which is the desired result.

Addendum: To see the first condition, suppose $\Vert z-y\Vert \ge \Vert y-x\Vert $ for all $z\in K$.

We have $\Vert z-y{\Vert}^{2}=\Vert z-x+x-y{\Vert}^{2}=\Vert z-x{\Vert}^{2}+\Vert x-y{\Vert}^{2}+2\u27e8z-x,x-y\u27e9$ (this is where Pythagoras appears) which gives $\Vert z-x{\Vert}^{2}+2\u27e8z-x,x-y\u27e9\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}\Vert z-x{\Vert}^{2}+2t\u27e8z-x,x-y\u27e9\ge 0$, dividing across by t and letting $t\downarrow 0$ yields the desired result.

The distance between the centers of two circles C1 and C2 is equal to 10 cm. The circles have equal radii of 10 cm.

A part of circumference of a circle is called

A. Radius

B. Segment

C. Arc

D. SectorThe perimeter of a basketball court is 108 meters and the length is 6 meters longer than twice the width. What are the length and width?

What are the coordinates of the center and the length of the radius of the circle represented by the equation ${x}^{2}+{y}^{2}-4x+8y+11=0$?

Which of the following pairs of angles are supplementary?

128,62

113,47

154,36

108,72What is the surface area to volume ratio of a sphere?

An angle which measures 89 degrees is a/an _____.

right angle

acute angle

obtuse angle

straight angleHerman drew a 4 sided figure which had only one pair of parallel sides. What could this figure be?

Trapezium

Parallelogram

Square

RectangleWhich quadrilateral has: All sides equal, and opposite angles equal?

Trapezium

Rhombus

Kite

RectangleKaren says every equilateral triangle is acute. Is this true?

Find the number of lines of symmetry of a circle.

A. 0

B. 4

C. 2

D. InfiniteThe endpoints of a diameter of a circle are located at (5,9) and (11, 17). What is the equation of the circle?

What is the number of lines of symmetry in a scalene triangle?

A. 0

B. 1

C. 2

D. 3How many diagonals does a rectangle has?

A quadrilateral whose diagonals are unequal, perpendicular and bisect each other is called a.

A. rhombus

B. trapezium

C. parallelogram