Proving Convexity of a Set: A Proof by Contradiction Approach

  • Thread starter Thread starter TaPaKaH
  • Start date Start date
  • Tags Tags
    Set
TaPaKaH
Messages
51
Reaction score
0
How to show that a set ##C=\{(x,y,z)\in\mathbb{R}^3:x\geq0,z\geq0,xz\geq y^2\}## is convex?

I tried a proof by contradiction: Assume that there exist ##c_1=(x_1,y_1,z_1),c_2=(x_2,y_2,z_2)\in C## and ##t\in(0,1)## such that ##tc_1+(1-t)c_2\notin C##.
For this to hold, one would have to have
$$(tx_1+(1-t)x_2)(tz_1+(1-t)z_2)<(ty_1+(1-t)y_2)^2$$ $$t^2x_1z_1+t(1-t)(x_1z_2+x_2z_1)+(1-t)^2x_2z_2<t^2y_1^2+2t(1-t)y_1y_2+(1-t)^2y_2^2.$$ We know that ##x_1z_1\geq y_1^2## and ##x_2z_2\geq y_2^2## but this doesn't seem to help me get any further than ##x_1z_2+x_2z_1<2y_1y_2##, from which I can't see a possible contradiction.
 
Physics news on Phys.org
TaPaKaH said:
How to show that a set ##C=\{(x,y,z)\in\mathbb{R}^3:x\geq0,z\geq0,xz\geq y^2\}## is convex?

I tried a proof by contradiction: Assume that there exist ##c_1=(x_1,y_1,z_1),c_2=(x_2,y_2,z_2)\in C## and ##t\in(0,1)## such that ##tc_1+(1-t)c_2\notin C##.
For this to hold, one would have to have
$$(tx_1+(1-t)x_2)(tz_1+(1-t)z_2)<(ty_1+(1-t)y_2)^2$$ $$t^2x_1z_1+t(1-t)(x_1z_2+x_2z_1)+(1-t)^2x_2z_2<t^2y_1^2+2t(1-t)y_1y_2+(1-t)^2y_2^2.$$ We know that ##x_1z_1\geq y_1^2## and ##x_2z_2\geq y_2^2## but this doesn't seem to help me get any further than ##x_1z_2+x_2z_1<2y_1y_2##, from which I can't see a possible contradiction.

You're on the right track.

Square both sides of ##x_1z_2+x_2z_1<2y_1y_2## to get ##x_1^2z_2^2+2(x_1z_1)(x_2z_2)+x_2^2z_1^2<4y_1^2y_2^2## (*)

By the property of C, ##x_1z_1≥y_1^2## and ##x_2z_2≥y_2^2##. Applying this to (*) and rearranging gives ##x_1^2z_2^2+x_2^2z_1^2<2y_1^2y_2^2##, but ##2y_1^2y_2^2≤2(x_1z_1)(x_2z_2)##, so this gives us ##x_1^2z_2^2-2(x_1z_1)(x_2z_2)+x_2^2z_1^2<0##. Why is this a contradiction?
 
Last edited:
  • Like
Likes 1 person
Got it, thank you!
 
Back
Top