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!

Proving convexity of a set

  1. Oct 4, 2009 #1
    1. The problem statement, all variables and given/known data

    prove the set is convex or give a counter example:

    1. S = {(x,y) : y >/= e^x}
    2. T = {(x,y) : y </= ln(x)}

    2. Relevant equations

    defn. of convexity
    (x1, y1) and (x2, y2) in S => (tx1 +(1-t)x2, ty1 + (1-t)y2) in S, 0 </= t </= 1

    3. The attempt at a solution

    I think 2 will be pretty easy once a I get 1, so I don't really need anyone to do 2 for me...just help with 1.

    anyways, I know that for the convex combination to be in the set, then

    ty1 + (1-t)y2 >/= exp[tx1 +(1-t)x2]

    so we want to show that t * exp[x1] + (1-t) * exp[x2] >/= exp[tx1 +(1-t)x2]

    I made a few different attempts at it...

    now i have 1 - t + t*exp[x1 - x2] >/= exp[tx1-tx2]

    ....but I'm stuck, perhaps there's a better way to go about it?
     
    Last edited: Oct 5, 2009
  2. jcsd
  3. Oct 4, 2009 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    EDIT: Whoops, I misread your post :/
     
  4. Oct 5, 2009 #3
    I know that if I can get 1 I can get 2, and vice-versa. The problem is I can't seem to get either...at least in terms of a mathematical proof. I can look at the graph and see that the set is convex...but that won't suffice on my HW.
     
  5. Oct 5, 2009 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I know, after I posted I realized I misread something.

    What you reduced to is too far.... if t=0 your final inequality no longer holds true. I'm going to think a bit about an algebraic argument.

    Ok, here's a start

    Calling x1 x and x2 y here, for the sake of less subscripts:
    We want to prove that
    [tex]te^x + (1-t)e^y \geq e^{tx + (1-t)y}=e^{tx-ty}e^y[/tex]

    Dividing both sides by ey, we see this holds true if and only if

    [tex] te^{x-y} + 1-t \geq e^{t(x-y)} = (e^{x-y})^t[/tex]

    But x and y (x1 and x2 are arbitrary, so ex-y could be any positive number. So what we want to prove is that

    [tex]tk +1-t \geq k^t[/tex] when k>0 and t between 0 and 1. This is equivalent to saying that [itex] 1 \geq t(1-k) + k^t [/itex]

    Can you use analysis here? When k is very large, kt>=kt since this is saying t>= kt-1 and this is k to a negative exponent (unless t=1 which is trivial) so as k goes to infinity, the right hand side goes to zero. This means that the maximum of t(1-k) + kt will be a local maximum on the (k,t) plane so differentiating with respect to k and setting that equal to zero gives you what you want. Maybe that's too much for the course you're in though, I don't know
     
    Last edited: Oct 5, 2009
  6. Oct 5, 2009 #5
    hmmm, well, I'm an undergrad in a PhD microeconomics class...though only about half of the grad students have had analysis (I'm in the intro to analysis class now...)

    what you said makes sense...and I thought something along those lines, though didn't really know how to phrase it into a logical/precise argument...

    does this help....? we can assume k > 1, because we can assume wlog that x1 > x2 (x1=x2 is trivial, and thus (x1-x2)>0 => e^(x1-x2) > 1)
     
    Last edited: Oct 5, 2009
  7. Oct 5, 2009 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The only other argument I can think of is a geometric one.... if a line connecting two points in the set goes outside the set, it must cross the curve y=ex twice (once to get outside, and then again to get inside) and hence drawing a line segment between those two points gives you a line connecting points on a concave up curve that lies beneath the curve. But this is a contradiction since connecting points on a concave up curve always gives a line lying above the curve. This is nice and simple, but the devil is in the details

    If you need to prove this, you have to reach back into analysis (at least I do): A concave up curve can only hit a line up to two times, since if it reaches a line then reaches it again it must have a derivative greater than or equal to the slope of the line somewhere between those two points (mean value theorem). Then the derivative of the function can only be greater than that of the line past your second point, so the line can never reach the curve a third time. Now imagine that we look at the first (i.e. lesser x value) point where the line hits the curve. We know that somewhere between here and the later intersection point the derivative of the curve must be equal to the slope of the line, which means that at this intersection point the derivative of your concave up curve is less than the slope of the line. Hence locally when you look to the right the line lies above the curve, and the line must then lie above the curve until the curve intersects it again (intermediate value theorem) and this intersection point is exactly the other intersection point we were interested in (since the line only intersects the curve twice).

    I think more people are willing to accept without rigorous proof the geometric argument than a statement that [itex] 1\geq t(1-k) + k^t[/itex] holds true for all t between 0 and 1 and k positive without proof. I don't know, maybe someone has an easier way to do this
     
  8. Oct 5, 2009 #7

    lanedance

    User Avatar
    Homework Helper

    I was thinking the same thing as office_shredder, so pretty much just repeating the steps:

    1) only have to show for points on the boundary of the set (as any line must cross the boundary to show non-convexivity), so work on y(x) =e^x
    2) pick arbitrary x1<x2, which should prove for all values
    3) find m = slope of line
    4) show y'(x1) < m < y'(x2)
    5) show y''(x) > 0
    6) MVT - mean value theorem, there is a solution to y'(c) = m, with x1<c<x2
    7) in fact as y' is monotone increasing this is the only solution
    8) for all x<c, y'(x) < m, this shows that for all values of x : x1<x<c, e^x is below the line.
    9) simlar argument working back from x2 and i think that does it?
     
  9. Oct 5, 2009 #8
    I think this is what I'm going to say...

    suppose to the contrary that e^x is not convex,

    i.e., suppose there exists a t in the closed interval 0 to 1 such that

    t * exp[x1] + (1-t) * exp[x2] < exp[tx1 +(1-t)x2]. also assume wlog that x2<x1

    note that when t=0 and t=1, the two equations are equal. so then there must be a t such that 0< t <1 so that

    t * exp[x1] + (1-t) * exp[x2] < exp[tx1 +(1-t)x2],

    since at t=1 exp[tx1 +(1-t)x2] = t * exp[x1] + (1-t) * exp[x2],

    and at some t<1, exp[tx1 +(1-t)x2] > t * exp[x1] + (1-t) * exp[x2],

    and since x1 > x2, tx1 +(1-t)x2 is increasing in t,

    then there must be some t -value that would make e^x decrease.

    but e^x is strictly increasing, so then t * exp[x1] + (1-t) * exp[x2] >= exp[tx1 +(1-t)x2] for t in (0,1)...

    I'm not assuming my answer am I?
     
  10. Oct 5, 2009 #9

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Both the left and right hand sides of your inequality are increasing, so that doesn't work. You could take the derivative of both sides and demonstrate that one is increasing faster than the other or something like that, but as is you don't have a solid proof
     
  11. Oct 5, 2009 #10
    yeah, it was really late when i pieced those ideas together, so I didn't think they were exactly right...I'll post the "solution" when they are posted if you're interested...
     
  12. Oct 5, 2009 #11

    lanedance

    User Avatar
    Homework Helper

    how about this (not quite there but close)

    pick a<c'<b', and let the points be described by their increments
    c' = a+c
    b' = a+b

    then the line, f(x), from a to b on y= e^x is given by:
    [tex] f(x) = \frac{e^b'-e^a}{b'-a}(x-a) + e^a = \frac{e^{a+b}-e^a}{a+b-a}(x-a) + e^a = e^a(\frac{e^b-1}{b}(x-a) +1) [/tex]

    at c'
    [tex] f(c') = e^a(\frac{e^b-1}{b}c +1) [/tex]
    [tex] y(c') = e^c' = e^a.e^c [/tex]

    so it remains to show that f(c') > y(c'), which reduces to:

    show when c<b that
    [tex] \frac{e^c-1}{c} < \frac{e^b-1}{b} [/tex]

    not totally sure from here, but looks doable?
     
    Last edited: Oct 5, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook