"Pythagorean theorem" for projection onto convex setI'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 ⊂ R d be a convex set, y ∈ R d , and x = Π K ( y ). Then for any z ∈ K we have: ‖ y − z ‖ ≥ ‖ x − z ‖ .It is presented without proof - what is a proof for this? Also, how does it relate to the pythagorean theorem?

Question

&quot;Pythagorean theorem&quot; for projection onto convex setI&#039;m going through the book on online convex optimization by Hazan,  and in the first chapter I saw this assertion (which Hazan calls the &quot;pythagorean theorem&quot;):Let   K  ⊂            R        d   be a convex set,   y  ∈            R        d  , and   x  =      Π    K    (  y  ). Then for any   z  ∈  K we have:  ‖  y  −  z  ‖  ≥  ‖  x  −  z  ‖  .It is presented without proof - what is a proof for this? Also, how does it relate to the pythagorean theorem?

potamanixv · Accepted Answer

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  ≠  y.The we have that   ⟨  x  −  y  ,  z  −  x  ⟩  ≥  0 for all   z  ∈  K (this is essentially the dual problem).If   z  ∈  K, we can write   z  −  y  =  t  (  x  −  y  )  +  d, where   d  ⊥  (  x  −  y  ). Then the above gives   ⟨  x  −  y  ,  t  (  x  −  y  )  +  d  +  y  −  x  ⟩  =  (  t  −  1  )  ‖  x  −  y      ‖    2    ≥  0 from which we get   t  ≥  1.Then   ‖  z  −  y      ‖    2    =  ‖  d      ‖    2    +      t    2    ‖  x  −  y      ‖    2    ≥  ‖  x  −  y      ‖    2   which is the desired result.Addendum: To see the first condition, suppose   ‖  z  −  y  ‖  ≥  ‖  y  −  x  ‖ for all   z  ∈  K.We have   ‖  z  −  y      ‖    2    =  ‖  z  −  x  +  x  −  y      ‖    2    =  ‖  z  −  x      ‖    2    +  ‖  x  −  y      ‖    2    +  2  ⟨  z  −  x  ,  x  −  y  ⟩ (this is where Pythagoras appears) which gives   ‖  z  −  x      ‖    2    +  2  ⟨  z  −  x  ,  x  −  y  ⟩  ≥  0 for all   z  ∈  K. Since   w  (  t  )  =  x  +  t  (  z  −  x  )  ∈  K for all   t  ∈  [  0  ,  1  ], we have       t    2    ‖  z  −  x      ‖    2    +  2  t  ⟨  z  −  x  ,  x  −  y  ⟩  ≥  0, dividing across by t and letting   t  ↓  0 yields the desired result.

"Pythagorean theorem" for projection onto convex set I'm going through the book on online convex op

Answered question

Answer & Explanation

New Questions in High school geometry