• Support PF! Buy your school textbooks, materials and every day products Here!

Convex Set in R^n Problem

  • #1

Homework Statement


Let ##C \subset \mathbb{R}^n## a convex set. If ##x \in \mathbb{R}^n## and ##\overline{x} \in C## are points that satisfy ##|x-\overline{x}|=d(x,C)##, proves that ##\langle x-\overline{x},y-\overline{x} \rangle \leq 0## for all ##y \in C##.

Homework Equations



By definition we have ##d(x,C) = inf \{ |x-z| ; z \in C \}##.
And if ##C## is a convex set, then for any two points ##v,w \in C## we have ##(1-t)v+tw \in C##.

The Attempt at a Solution



Due the fact that ##|x-\overline{x}|=d(x,C)## , I know that ##|x-\overline{x}|^2 \leq |x-z|^2## for all ##z \in C##.
I tried to sketch a prove by contraction. So I supposed that there is an ##y \in C## that ##\langle x-\overline{x},y-\overline{x} \rangle > 0##.
Then I used the fact that ##C## is a convex set, so ##z=(1-t)y+t\overline{x} \in C##, where ##t \in [0,1]##.
Then I intend to conclude something like ##|x-z|^2 < |x-\overline{x}|^2##, what would be an absurd:
upload_2018-9-5_14-1-30.png


But the fact is I came nowhere with my attempt... =(
 

Attachments

Answers and Replies

  • #2
12,653
9,173
If I draw a picture, then the law of cosine and the triangle inequality will come to mind, especially as such an inner product is part of the law of cosine.
 
  • #3
tnich
Homework Helper
1,048
336

Homework Statement


Let ##C \subset \mathbb{R}^n## a convex set. If ##x \in \mathbb{R}^n## and ##\overline{x} \in C## are points that satisfy ##|x-\overline{x}|=d(x,C)##, proves that ##\langle x-\overline{x},y-\overline{x} \rangle \leq 0## for all ##y \in C##.

Homework Equations



By definition we have ##d(x,C) = inf \{ |x-z| ; z \in C \}##.
And if ##C## is a convex set, then for any two points ##v,w \in C## we have ##(1-t)v+tw \in C##.

The Attempt at a Solution



Due the fact that ##|x-\overline{x}|=d(x,C)## , I know that ##|x-\overline{x}|^2 \leq |x-z|^2## for all ##z \in C##.
I tried to sketch a prove by contraction. So I supposed that there is an ##y \in C## that ##\langle x-\overline{x},y-\overline{x} \rangle > 0##.
Then I used the fact that ##C## is a convex set, so ##z=(1-t)y+t\overline{x} \in C##, where ##t \in [0,1]##.
Then I intend to conclude something like ##|x-z|^2 < |x-\overline{x}|^2##, what would be an absurd:
View attachment 230255

But the fact is I came nowhere with my attempt... =(
I think you are close here. I suggest writing the convexity condition as ##z=(1-t)\overline{x}+ty \in C##, that is, swapping ##t## and ##(1-t)##. This gives you points close to ##\overline{x}## when ##t## is small, and that is where you are likely to find a point ##z## that violates the condition ##|x-\overline{x}|=inf \{ |x-z| ; z \in C \}##. Then, if you work through your derivation with this change, you get ##\langle x-\overline{x},y-\overline{x} \rangle## showing up explicitly and you can find a condition on ##t## that gives you what you need.
 
  • #4
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

Homework Statement


Let ##C \subset \mathbb{R}^n## a convex set. If ##x \in \mathbb{R}^n## and ##\overline{x} \in C## are points that satisfy ##|x-\overline{x}|=d(x,C)##, proves that ##\langle x-\overline{x},y-\overline{x} \rangle \leq 0## for all ##y \in C##.

Homework Equations



By definition we have ##d(x,C) = inf \{ |x-z| ; z \in C \}##.
And if ##C## is a convex set, then for any two points ##v,w \in C## we have ##(1-t)v+tw \in C##.

The Attempt at a Solution



Due the fact that ##|x-\overline{x}|=d(x,C)## , I know that ##|x-\overline{x}|^2 \leq |x-z|^2## for all ##z \in C##.
I tried to sketch a prove by contraction. So I supposed that there is an ##y \in C## that ##\langle x-\overline{x},y-\overline{x} \rangle > 0##.
Then I used the fact that ##C## is a convex set, so ##z=(1-t)y+t\overline{x} \in C##, where ##t \in [0,1]##.
Then I intend to conclude something like ##|x-z|^2 < |x-\overline{x}|^2##, what would be an absurd:
View attachment 230255

But the fact is I came nowhere with my attempt... =(
What theorems about convex sets have already been proved in your course and so are available for you to use? For example, have you seen the "separating hyperplane" theorem?
 
  • #5
Finally I done this question!
Thanks for all the help. I could do it following the tip tnich gave to me.
Soon I'll organize the solution and I'll post here as well.
 
  • #6
As I promisse, follow a solution for this question.

Let us suppose, by contraction, there is ##y \in C## such that ##\langle x-\overline{x}, y - \overline{x} \rangle > 0##.

Let ##z=ty+(1-t)\overline{x}##, where ##t \in (0,1)##.

By hypothesis, ##C## is convex. Therefore, ##z \in C##.

We have:
upload_2018-9-7_13-20-18.png


Then,
upload_2018-9-7_13-20-50.png


By the other hand, we have:
upload_2018-9-7_13-21-19.png


By hypothesis, ##\langle x-\overline{x} , y - \overline{x} \rangle > 0##. Therefore, ##| \langle x-\overline{x} , y - \overline{x} \rangle | = \langle x-\overline{x} , y - \overline{x} \rangle##. Then we have:
upload_2018-9-7_13-24-44.png


Thus,
upload_2018-9-7_13-25-14.png


Taking ##t \in I^{*}##, we have:
upload_2018-9-7_13-26-12.png


Applying ##(II)## in ##(I)##, we have:

upload_2018-9-7_13-27-14.png


Absurd!

Therefore,
upload_2018-9-7_13-27-55.png
 

Attachments

  • #7
Another pretty good exercise it to use the exercise above to solve the following one:


Exercise: Let ##C \subset \mathbb{R}^n## be a convex and closed set. Let ##f : \mathbb{R}^n \to C## be a function defined as ##f(x)=\overline{x}##, where ##\overline{x}## is the unique point of ##C## such that ##|x-\overline{x}|=d(x,C)##. Prove that ##|f(x)-f(y)|\leq |x-y|## for any ##x,y \in \mathbb{R}^n##, i.e., ##f## is uniformly continuous.

I could solve this one as well. I'll let it as an exercise, but if someone tries to solve it and cannot find a way I can post my solution here. Thanks guys!
 
  • #8
tnich
Homework Helper
1,048
336
Another pretty good exercise it to use the exercise above to solve the following one:


Exercise: Let ##C \subset \mathbb{R}^n## be a convex and closed set. Let ##f : \mathbb{R}^n \to C## be a function defined as ##f(x)=\overline{x}##, where ##\overline{x}## is the unique point of ##C## such that ##|x-\overline{x}|=d(x,C)##. Prove that ##|f(x)-f(y)|\leq |x-y|## for any ##x,y \in \mathbb{R}^n##, i.e., ##f## is uniformly continuous.

I could solve this one as well. I'll let it as an exercise, but if someone tries to solve it and cannot find a way I can post my solution here. Thanks guys!
Looks good except for some minor errors (Cauchy - Schwartz inequality would require a ##\leq## sign, ##|y-\overline x|^2## in the denominator). But there are a couple of major ones as well.
1) you have only completed the proof for ##x \notin C##. When ##x\in C##, ##\langle x-\overline{x},y-\overline{x} \rangle = 0## and the chain of inequalities fails. Fortunately, it is easy to prove this special case.
2) Since ##\overline x \in C##, ##y## can be as close to ##\overline x## as you like, meaning that ##|x- \overline x| \leq |y - \overline x|## is not true in general. The proof is still salvageable, though.
 
Last edited:
  • #9
tnich
Homework Helper
1,048
336
Looks good except for some minor errors (Cauchy - Schwartz inequality would require a ##\leq## sign, ##|y-\overline x|^2## in the denominator). But there are a couple of major ones as well.
1) you have only completed the proof for ##x \notin C##. When ##x\in C##, ##\langle x-\overline{x},y-\overline{x} \rangle = 0## and the chain of inequalities fails. Fortunately, it is easy to prove this special case.
2) Since ##\overline x \in C##, ##y## can be as close to ##\overline x## as you like, meaning that ##|x- \overline x| \leq |y - \overline x|## is not true in general. The proof is still salvageable, though.
Try solving this inequality directly for ##t##:
##-2t\langle x-\overline{x} , y - \overline{x} \rangle + t^2|y-\overline x|^2 <0##
 

Related Threads on Convex Set in R^n Problem

  • Last Post
Replies
5
Views
478
  • Last Post
Replies
0
Views
954
  • Last Post
Replies
2
Views
465
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
2
Views
976
Top