Proving Convexity of a Set: Is the Set {(x,y) : y >/= e^x} Convex?

[economist13]

Homework Statement

prove the set is convex or give a counter example:

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

Homework Equations

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

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?

 

[Office_Shredder]

EDIT: Whoops, I misread your post :/

 

[economist13]

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.

 

[Office_Shredder]

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 x₁ x and x₂ y here, for the sake of less subscripts:
We want to prove that
te^x + (1-t)e^y \geq e^{tx + (1-t)y}=e^{tx-ty}e^y

Dividing both sides by e^y, we see this holds true if and only if

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

But x and y (x₁ and x₂ are arbitrary, so e^x-y could be any positive number. So what we want to prove is that

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

Can you use analysis here? When k is very large, kt>=k^t since this is saying t>= k^t-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) + k^t 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

 

[economist13]

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)

 

[Office_Shredder]

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=e^x 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 1\geq t(1-k) + k^t 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

 

[lanedance]

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) similar argument working back from x2 and i think that does it?

 

[economist13]

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?

 

[Office_Shredder]

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

 

[economist13]

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...

 

[lanedance]

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:
f(x) = \frac{e^b&#039;-e^a}{b&#039;-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)

at c'
f(c&#039;) = e^a(\frac{e^b-1}{b}c +1)
y(c&#039;) = e^c&#039; = e^a.e^c

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

show when c<b that
\frac{e^c-1}{c} &lt; \frac{e^b-1}{b}

not totally sure from here, but looks doable?