Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Convex sets

  1. Oct 22, 2005 #1
    Hello! I've got some questions concerning convex sets.
    We've had a lecture about convex sets this week, and got a some basic problems to solve. I think I can't use the material in the lecture to solve the problem. I'm just not sure about whether I fully understand the concept and can use it properly.
    In the lecture the prof presented a proof for the fact that for every [itex]t\in\matbb{R}[/itex] the interval [itex]I=[0,t]:=\{s|s\in\mathbb{R},0\le{s}\le{t}\}[/itex] is convex.
    The proof went like this.
    Let [itex]s_1,s_2\in[0,t][/itex] and [itex]\lambda\in[0,1][/itex]. The following holds: [itex]0\le{s_1}[/itex] and [itex]s_2\le{t}[/itex].
    [itex]\lambda{s_1}+(1-\lambda){s_2}\le\lambda{t}+(1-\lambda)t=t[/itex]. Hence, the interval is convex.
    Now, the first question.
    Why cannot we simply check whether the condition holds for [itex]\lambda=0[/itex] or [itex]\lambda=1[/itex] ?
    It's [itex]\lambda\cdot{0}+(1-\lambda)t[/itex]. Then for [itex]\lambda=0[/itex] t is in I and for [itex]\lambda=1[/itex] 0 is in I.
    It's now asked to show that a hyperplane [itex]E\subseteq\mathbb{R}^n[/itex], [itex]E:=\{(x_1,...,x_n)\in\mathbb{R}^n|a_1{x_1}+...+a_n{x_n}=b\}[/itex], where [itex]a_1,...,a_n,b\in\mathbb{R}[/itex] and [itex](a_1,...,a_n)\neq(0,...,0)[/itex] is a convex set.
    Here, equally, it seems too easy just to put in two elements, say [itex]x_1[/itex] and [itex]x_n[/itex] and let [itex]\lambda[/itex] be either 0 or 1. If it's wrong to take this way, how can I show that E is convex differently?
  2. jcsd
  3. Oct 22, 2005 #2


    User Avatar
    Science Advisor

    You are given that the two points corresponding to[itex]\lambda= 0[/itex] and [itex]\lambda= 1[/itex] are in the set! The thing you want to prove is that every point on the interval between them is in the set- that corresponds to [itex]0< \lamba< 1[/itex].
    Suppose you were asked to prove that the set [0, 1)union(1,2] was not convex. What would you do?

    First, x1 and x2 are not "elements" of Rn. They are simply components of a single point. You would have to take two arbitrary points, say (x1,x,...,xn) and (y1, y2, ... , yn) in the set and show that any point on the line segment between them (which can be written (x1+ [itex]\lambda[/itex](y1-x1), x2+ [itex]\lambda[/itex](y2-x2), ..., xn+ [itex]\lambda[/itex](yn-n1)) for [itex]0< \lambda< 1[/itex]. [itex]\lamba[/itex]= 0 or 1 just gives the points you started with. By hypothesis, they are in the set.
  4. Oct 23, 2005 #3
    Thanks for your reply!

    OK, for the union [itex]I=[0,1)\cup(1,2][/itex] is it right if I do it this way?:
    Let [itex]s_1,s_2\in{I}[/itex] be two elements, such that [itex]0\le{s_1}<1[/itex] and [itex]1<s_2\le{2}[/itex]. If the union is convex, then the following holds: [itex]0\le\lambda{s_1}+(1-\lambda)s_2\le{2}[/itex]. We have [itex]0\le\lambda{s_1}<1[/itex], but at the same time [itex]1<(1-\lambda)s_2\le{2}[/itex] does not hold for all [itex]\lambda\in[0,1][/itex], since [itex]0\le(1-\lambda)s_2<1[/itex] for some [itex]\lambda\in[0,1][/itex]. This means that [itex]s_2\notin{I}[/itex] for some [itex]\lambda\in[0,1][/itex], which contradicts the assumption.

    Now to the hyperplane.
    So you mean that given two points [itex](x_1,...,x_n)[/itex] and [itex](y_1,...,y_n)[/itex] [itex]\lambda(x_1,...,x_n)+(1-\lambda)(y_1,...,y_n)[/itex] must be in the set, because [itex]a_1(\lambda{x_1}+(1-\lambda)y_1)+...+a_n(\lambda{x_n}+(1-\lambda)y_n)=b[/itex] for any two such points? As it seems from what you said we don't have to prove this last statement about the sum. Why? I mean it's clear that for every [itex]a_1,...,a_n,\in\mathbb{R}[/itex], [itex](a_1,...,a_n)\neq(0,...,0)[/itex] there is always a real number b, is it really enough for the proof?

    What about half space [itex]H: =\{(x_1,...,x_n)\in\mathbb{R}^n|a_1{x_1}+...+a_n{x_n}\ge{b}\}[/itex], where [itex]a_1,...,a_n,b\in\mathbb{R}[/itex] and [itex](a_1,...,a_n)\neq(0,...,0)[/itex], which is one part of the space split by the hyperplane? Does the check for convexity of the hyperplane automatically yield the same result for this halfspace, i.e. the fact that it is convex too, or is there anything more to be done here?
    Last edited: Oct 23, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook