MHB Proving Convexity: Steps and Conditions for a Set to be Convex

  • Thread starter Thread starter rputra
  • Start date Start date
rputra
Messages
35
Reaction score
0
I would like getting for this problem: Consider $\mathscr D := \{(x,y) \mid x, y \in \mathbb R^2 \}$ with $x+y \geqslant 0$, $x+y \leq 7$ and $x \geqslant 2$. Show that the set is convex. The standard steps say that there exist $k_1, k_2 \geqslant 0$ with $k_1 + k_2 = 1$, and I have to prove that $xk_1 + y(1-k_1) \in \mathscr D$ in order to show convexity. Please help me on going forward from here, thank you very much for your time and effort.
 
Physics news on Phys.org
Tarrant said:
I would like getting for this problem: Consider $\mathscr D := \{(x,y) \mid x, y \in \mathbb R^2 \}$ with $x+y \geqslant 0$, $x+y \leq 7$ and $x \geqslant 2$.
This definition should say
\[
\mathscr D=\{(x,y)\in\mathbb{R}^2\mid x+y \geqslant 0,x+y \leq 7,x \geqslant 2\}.
\]

Tarrant said:
Show that the set is convex.
Note that $\mathscr D=D_1\cap D_2\cap D_3$ where $D_1=\{(x,y)\mid x+y \geqslant 0\}$, $D_2=\{(x,y)\mid x+y \leq 7\}$ and $D_3=\{(x,y)\mid x \geqslant 2\}$. I suggest proving a general fact that that intersection of convex sets is convex, so it would be sufficient to prove that each of $D_i$ is convex.

Tarrant said:
The standard steps say that there exist $k_1, k_2 \geqslant 0$ with $k_1 + k_2 = 1$, and I have to prove that $xk_1 + y(1-k_1) \in \mathscr D$ in order to show convexity.
Yes, points lying on the segment between $(x_1,y_2)$ and $(x_2,y_2)$ have coordinates $((1-k)x_1+kx_2,(1-k)y_1+ky_2)$ for $0\le k\le 1$. Use this definition to to prove that sets $D_i$ are convex. For example, for $D_2$ you need to show that $x_1+y_1\le 7$ and $x_2+y_2\le 7$ imply
\[
(1-k)x_1+kx_2+(1-k)y_1+ky_2\le7.
\]
 
Last edited:
Evgeny.Makarov said:
Yes, points lying on the segment between $(x_1,y_2)$ and $(x_2,y_2)$ have coordinates $((1-k)x_1+kx_2,(1-k)y_2+ky_2)$ for $0\le k\le 1$. Use this definition to to prove that sets $D_i$ are convex. For example, for $D_2$ you need to show that $x_1+y_1\le 7$ and $x_2+y_2\le 7$ imply
\[
(1-k)x_1+kx_2+(1-k)y_2+ky_2\le7.
\]

Thank you for your quick response! I understand the first part and second part of your solution, but on the third part (quoted above,) how do you get from $x_1+y_1\le 7$ and $x_2+y_2\le 7$ to implying that $(1-k)x_1+kx_2+(1-k)y_2+ky_2\le7$? I would appreciate if you could provide me with additional steps. Thank you again and again for your time and effort.

PS: I am sorry I get back late answering your question.
 
Tarrant said:
how do you get from $x_1+y_1\le 7$ and $x_2+y_2\le 7$ to implying that $(1-k)x_1+kx_2+(1-k)y_2+ky_2\le7$?
There was a typo in the coordinates of a point on the segment and in the inequality to be proved. The point has coordinates $((1-k)x_1+kx_2, (1-k)y_1+ky_2)$ ($y_1$ instead of $y_2$), and the claim should read
\[
(1-k)x_1+kx_2+(1-k)y_1+ky_2\le7.
\]
Note that $(1-k)x_1+kx_2+(1-k)y_1+ky_2=(1-k)(x_1+y_1)+k(x_2+y_2)$. Now use conditions on $(x_1,y_1)$ and $(x_2,y_2)$ and the fact that $0\le k\le 1$ (it is essential).
 
Last edited:
Evgeny.Makarov said:
There was a typo in the coordinates of a point on the segment and in the inequality to be proved. The point has coordinates $((1-k)x_1+kx_2, (1-k)y_1+ky_2)$ ($y_1$ instead of $y_2$), and the claim should read
\[
(1-k)x_1+kx_2+(1-k)y_1+ky_2\le7.
\]
Note that $(1-k)x_1+kx_2+(1-k)y_1+ky_2\le7=(1-k)(x_1+y_1)+k(x_2+y_2)$. Now use conditions on $(x_1,y_1)$ and $(x_2,y_2)$ and the fact that $0\le k\le 1$ (it is essential).

Thank you again. Let me think about it and get back with you soon. Thanks again.
 
Evgeny.Makarov said:
...
Note that $(1-k)x_1+kx_2+(1-k)y_1+ky_2\le7=(1-k)(x_1+y_1)+k(x_2+y_2)$. Now use conditions on $(x_1,y_1)$ and $(x_2,y_2)$ and the fact that $0\le k\le 1$ (it is essential).

I know easily that because $0 \leq k \leq 1$ and $0 \leq (1-k) \leq 1$ therefore $(1-k)(x_1+y_1) \leq (x_1+y_1) \leq 7$ and $k(x_2+y_2) \leq (x_2+y_2) \leq 7$, hence $(1-k)(x_1+y_1) \leq 7$ and $k(x_2+y_2) \leq 7$. And then, what is next? How do you go from here to get to the claim $(1-k)x_1+kx_2+(1-k)y_1+ky_2\leq 7$? I am sorry but I am still confused. Thanks again in advance for all your time and help.s
 
Tarrant said:
I know easily that because $0 \leq k \leq 1$ and $0 \leq (1-k) \leq 1$ therefore $(1-k)(x_1+y_1) \leq (x_1+y_1) \leq 7$
Instead of $(1-k)(x_1+y_1) \leq (x_1+y_1)$ try $(1-k)(x_1+y_1) \leq 7(1-k)$ and similarly for $k(x_2+y_2)$.
 
Back
Top