MHB Proving Convex Set Properties to Showing the Convexity of X-Y

rputra
Messages
35
Reaction score
0
I need help on this problem:

If $X$ and $Y$ are convex sets, show that $X-Y = Z = \{x-y \mid x \in X, y \in Y\}$ is also convex.

Here are the steps I have gone so far:

Let $p \in Z$ such that $p = x_1 - y_1$, and let $q \in Z$ such that $q = x_2 - y_2$. Assume that $r$ lays in the segment line of $\overline {pq}$ so that there exists $k$ and $k'$, with $k, k' \geq 0$ and $k+k' = 1$, such that $r = kp + (1-k)q$. By way of contradiction, we are going to show that $r \notin Z$, thus implying that $Z$ is indeed concave.

Then,
$$\begin{align}
r &= kp + (1-k)q \\
&= k(x_1 - y_1) + (1-k)(x_2 - y_2) \\
&= x_1k - y_1k + x_2 - y_2 - x_2k + y_2k \\
&= \ldots \\
&= \ldots
\end{align}$$

But then I do not how to follow up. Any help or hint would be very much appreciated. Thank you for your time.
 
Last edited:
Physics news on Phys.org
Tarrant said:
I need help on this problem:

If $X$ and $Y$ are convex sets, show that $X-Y = Z = \{x-y \mid x \in X, y \in Y\}$ is also convex.

Here are the steps I have gone so far:

Let $p \in Z$ such that $p = x_1 - y_1$, and let $q \in Z$ such that $q = x_2 - y_2$. Assume that $r$ lays in the segment line of $\overline {pq}$ so that there exists $k$ and $k'$, with $k, k' \geq 0$ and $k+k' = 1$, such that $r = kp + (1-k)q$. By way of contradiction, we are going to show that $r \notin Z$, thus implying that $Z$ is indeed concave.

Then,
$$\begin{align}
r &= kp + (1-k)q \\
&= k(x_1 - y_1) + (1-k)(x_2 - y_2) \\
&= x_1k - y_1k + x_2 - y_2 - x_2k + y_2k \\
&= \ldots \\
&= \ldots
\end{align}$$

But then I do not how to follow up. Any help or hint would be very much appreciated. Thank you for your time.

I am not sure why are you invoking the contradiction approach. It's rather straightforward. And you have to show that $Z$ is convex and not concave!

Here is what you do

$$\begin{align}
r &= kp + (1-k)q \\
&= k(x_1 - y_1) + (1-k)(x_2 - y_2) \\
&= [kx_1 +(1-k)x_2 ]- [ky_1+ (1-k)y_2] \\
&= x-y
\end{align}$$
where $x=kx_1+(1-k)x_2$ and $y=ky_1+(1-k)y_2$. Note that $x\in X$ and $y\in Y$ since $X$ and $Y$ are convex. Thus $kp+(1-k)q$ lies in $X-Z=Y$, showing that $Z$ is convex.
 
caffeinemachine said:
I am not sure why are you invoking the contradiction approach. It's rather straightforward. And you have to show that $Z$ is convex and not concave!

Here is what you do

$$\begin{align}
r &= kp + (1-k)q \\
&= k(x_1 - y_1) + (1-k)(x_2 - y_2) \\
&= [kx_1 +(1-k)x_2 ]- [ky_1+ (1-k)y_2] \\
&= x-y
\end{align}$$
where $x=kx_1+(1-k)x_2$ and $y=ky_1+(1-k)y_2$. Note that $x\in X$ and $y\in Y$ since $X$ and $Y$ are convex. Thus $kp+(1-k)q$ lies in $X-Z=Y$, showing that $Z$ is convex.

My bad, my bad! Sorry for the dumb opinion. Thank you for pointing that out! Just to let you know that I forgot to mention that $X$ and $Y$ are in vector space. (Or perhaps you have already known it by implication?) That means that $X$ and $Y$ are closed under addition and scalar multiplication, am I correct in these? Thanks again and again for your time and effort.
 
Tarrant said:
My bad, my bad! Sorry for the dumb opinion. Thank you for pointing that out! Just to let you know that I forgot to mention that $X$ and $Y$ are in vector space. (Or perhaps you have already known it by implication?) That means that $X$ and $Y$ are closed under addition and scalar multiplication, am I correct in these? Thanks again and again for your time and effort.
The implication that $X-Y$ is convex follows from the convexity of $X$ and $Y$ alone. We do not need to assume that $X$ and $Y$ are vector spaces. If something is confusing you then you may start from the beginning in the next post.
 
Back
Top