1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that set is convex

  1. Apr 19, 2012 #1
    Let [itex]\alpha[/itex]>0 and [itex]\gamma[/itex]>0 and [itex]\beta[/itex]>0 be real numbers. Let M={x∈R[itex]^{2}_{+}[/itex] ∶[itex]\alpha[/itex]x[itex]_{1}[/itex]+[itex]\gamma[/itex]x[itex]_{2}[/itex][itex]\leq[/itex][itex]\beta[/itex]}. Prove M is a convex set. Prove that M is bounded. What does this set resemble (in economics)?

    I have a little idea of how to show that this set is convex, although, I know the condition for a convex set (ax1+(1-a)x2, 0<a<1). It is clear to me that this set resembles PPF, so can you just show me how to prove that it is convex, please.
     
    Last edited: Apr 19, 2012
  2. jcsd
  3. Apr 20, 2012 #2
    pick any two points in your set, x=(x1,x2), y=(y1,y2), prove that a*x+(1-a)*y is also in that set for any 0<a<1.
     
  4. Apr 21, 2012 #3
    And how do I prove these arbitrary point s are in the set? Should I make some kind of inequality?
     
  5. Apr 21, 2012 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You know that (x1,x2) and (y1,y2) satisfy the inequality that defines M. Write down those conditions. Then write down the inequality that the convex combination of these points has to satisfy, and prove that this inequality is true by using the two inequalities that you know are true.

    The proof is basically three lines, if you write everything down and try some algebra and it doesn't work post what you've done and we can help you
     
  6. Apr 21, 2012 #5
    I wrote that proof, but I am unable to make this inequality work out. Thats what I got:
    u=(u[itex]_{1}[/itex],u[itex]_{2}[/itex]), f(u)=[itex]\alpha[/itex]u[itex]_{1}[/itex]+[itex]\gamma[/itex]u[itex]_{2}[/itex]-[itex]\beta[/itex]

    v=(v[itex]_{1}[/itex],v[itex]_{2}[/itex]), f(v)=[itex]\alpha[/itex]v[itex]_{1}[/itex]+[itex]\gamma[/itex]v[itex]_{2}[/itex]-[itex]\beta[/itex]

    Inequality that the convex function has to satisfy is:

    [itex]\lambda[/itex]f(u)+(1-[itex]\lambda[/itex])f(v)[itex]\geq[/itex]f[[itex]\lambda[/itex]u+(1-[itex]\lambda[/itex])v]

    or

    [itex]\lambda[/itex]([itex]\alpha[/itex]u[itex]_{1}[/itex]+[itex]\gamma[/itex]u[itex]_{2}[/itex]-[itex]\beta[/itex])+(1-[itex]\lambda[/itex])([itex]\alpha[/itex]v[itex]_{1}[/itex]+[itex]\gamma[/itex]v[itex]_{2}[/itex]-[itex]\beta[/itex])[itex]\geq[/itex][itex]\alpha[/itex]([itex]\lambda[/itex]u[itex]_{1}[/itex]+(1-[itex]\lambda)[/itex]v[itex]_{1}[/itex])+[itex]\gamma[/itex]([itex]\lambda[/itex]u[itex]_{2}[/itex]+(1-[itex]\lambda[/itex])v[itex]_{2}[/itex])-[itex]\beta[/itex]

    So I cannot make this inequality work out. What I get is that 0[itex]\geq[/itex]0. Does it mean that the inequality is satisfied since it is bigger or EQUAL?
     
    Last edited: Apr 21, 2012
  7. Apr 21, 2012 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't understand why you are introducing convex functions to the problem. Set convexity and function convexity are related but distinct concepts.

    If [itex] (x_1,x_2)\ , (y_1,y_2) \in M[/itex] we get
    [tex] \alpha x_1 + \gamma x_2 \leq \beta [/tex]
    [tex] \alpha y_1 + \gamma y_2 \leq \beta[/tex]

    Now for any 0<a<1 we want to prove
    [tex] \alpha( a x_1 + (1-a) y_1)) + \gamma ( a x_2 + (1-a) y_2 ) \leq \beta [/tex]
    There are two things that you should do: understand why this is what we need to prove, and then prove it using the first two inequalities that I posted
     
  8. Apr 21, 2012 #7
    Oh I did not actually realize these are two different concepts.

    Alright, I got the solution. To prove this inequality I first expanded the LHS and rearranged the terms:(instead of [itex]\alpha[/itex] I will use [itex]\lambda[/itex] to avoid confusion)

    [tex] \lambda ( a x_1 + (1-a)y_1) + \gamma( ax_2+(1-a)y_2) =
    \lambda ax_1 + \gamma ax_2 + \lambda( 1-a) y_1 + \gamma( 1-a) y_2\ =
    a(\lambda x_1+\gamma x_2) + (1-a)(\lambda y_1 + \gamma y_2)[/tex]

    Now I need to show that the last expression above is less than β. To do that I used the two inequalities that I know are true.

    [tex] \alpha x_1 + \gamma x_2 \leq \beta [/tex]
    [tex] \alpha y_1 + \gamma y_2 \leq \beta[/tex]

    Multiply the first one by a and we get:
    [tex] a(\alpha x_1 + \gamma x_2) \leq a\beta [/tex]

    Multiply the second one by (1-a) and we get:
    [tex] (1-a)(\alpha y_1 + \gamma y_2) \leq (1-a) \beta[/tex]

    Add them up and we get:
    [tex]a(\lambda x_1+\gamma x_2) + (1-a)(\lambda y_1 + \gamma y_2) \leq a\beta + (1-a) \beta [/tex]

    The LHS looks exactly like the LHS of the inequality we need to prove.
    So now If we expand the RHS we get β and the inequality looks like:
    [tex]a(\lambda x_1+\gamma x_2) + (1-a)(\lambda y_1 + \gamma y_2) \leq \beta[/tex]

    Exactly like the inequality we need to prove and did so. Since we know that the two inequalities with points (x1,x2) and (y1,y2) are true adding them up will be also true and after we added them up the resultant inequality looks exactly like the one we needed to prove after we rearranged terms.
     
    Last edited: Apr 21, 2012
  9. Apr 22, 2012 #8
    This set resembles a budget constraint (not PPF) and is bounded by:
    at x[itex]_{2}[/itex]=0, x[itex]_{1}\leq[/itex][itex]\frac{\beta}{\alpha}[/itex]
    at x[itex]_{1}[/itex]=0, x[itex]_{2}\leq[/itex][itex]\frac{\beta}{\gamma}[/itex]
     
  10. Apr 22, 2012 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    By far, the easiest way to deal with questions like the one you asked is to proceed in small steps: (1) prove that a half-space [itex] a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b[/itex] is a convex set in [itex] (x_1, x_2, \ldots, x_n)-\text{space}[/itex] (where the [itex] a_i, b[/itex] are constants); then prove (2): the intersection of convex sets is convex. With hardly any work at all you then can say that the set of [itex](x_1,x_2,\ldots,x_n)[/itex] that satisfy the equalities and inequalities
    [tex]\begin{array}{l}
    a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n \leq b_1,\\
    a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n \leq b_2, \\
    \vdots\\
    a_{r1} x_1 + a_{r2} x_2 + \cdots + a_{rn} x_n \leq b_r,\\
    c_{11} x_1 + c_{12} x_2 + \cdots + c_{1n} x_n = d_1, \\
    \vdots\\
    c_{s1} x_1 + c_{s2} x_2 + \cdots + c_{sn} x_n = d_s
    \end{array}
    [/tex]
    is convex if it is not empty.

    RGV
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook