suppose X,Y are two convex sets
x1, x2 in X and y1, y2 in Y
defn of X and Y being convex:
tx1+(1-t)x2 in X
ty1+(1-t)y2 in Y
it is clear that:
1) X+Y is convex.
2) X intersection Y is convex
3) question: I know A union B is not convex but I don't understand why
AUB = A+B - A(intersection)B
but both on RHS are convex and subtraction of convex sets is convex. so shoudn't AUB also be convex?
how about A\B?
A\B = A - A(intersection)B again both on RHS are convex so shouldn't A\B be convex?
QN: for a convex set P, 2P belongs to P+P? How? How it it that 2P is not equal to P+P?
EDIT:
is A-B not a convex set? I thought it would be.
ta1+(1-t)a2 in A tb1+(1-t)b2 in B
WTS t*(a1-b1)+(1-t)(a2-b2) in A-B
but t*(a1-b1)+(1-t)(a2-b2) = t(a1)+(1-t)a2 - [t*b1+(1-t)b2]
first half in RHS is in A and second half in RHS is in B so whole thing is in A - B hence A-B is convex? no?
$\endgroup$3 Answers
$\begingroup$I don't think subtraction of convex sets is convex.
Let's look at a particular example in 1 dimension of a union of convex sets not being convex:
The intervals $[0,1]$ and $[2,3]$ are both convex because they satisfy your definition. But $[0,1] \cup [2,3]$ is not convex because, for example, $t \cdot 1 + (1 - t)\cdot 2$ is not in $[0,1] \cup [2,3]$ for any $t \in (0,1)$ (we chose $1$ and $2$ because $1$ is in the first set of the union, and $2$ is in the second set).
Intuitively, if the two sets have some "space" between them, then any line you draw between a point in one space and a point in the other will have points not in either.
As to why set difference of convex sets is not convex, we can use a similar idea. Consider the convex set $[0,3]$. Inside of it we have the interval $[1,2]$, which is also convex. But if we remove $[1,2]$ from $[0,3]$, we are left with $[0,1) \cup (2,3]$ which is not convex since, for example, we can find $t \in (0,1)$ such that $t \cdot \frac{1}{2} + (1 - t) \cdot \frac{5}{2}$ is not in this new set.
EDIT
For your last question: $2P$ is basically the set where you take each element of $P$ and multiply it by $2$, or, say, add it to itself once. But $P + P$ is the set where you take any two elements of $P$ and add them. If $P$ has more than one elememt, then $2P$ is a proper subset of $P + P$ because if you have two elements $p_{1}, p_{2}$ in $P$ that are not equal, then $p_{1} + p_{2}$ is in $P + P$ but not $2P$. Do you understand why?
$\endgroup$ 4 $\begingroup$Take the disjoint union of two squares, say at x=0, x=100, each with sides = 1. The point x=50 is in the convex hull of these two squares but isn't in the disjoint union, so the disjoint union isn't convex.
Again, for A\B, take two squares, A with sides 2, B with sides 1, if they are both centered at x=0 the point x=0,y=0 is in the convex hull of A\B yet isn't in A\B, so A\B isn't convex
If you define A such that $ S=A-B= a-b; a \epsilon A,b \epsilon B $ [in this content some authors use - with circle in "$\ominus$" to differentiate A\B] and A and B are both convex sets, then S is convex.
Proof: Let $ x = a-b $ and $ y= a'-b$ $\lambda \epsilon [0,1] $ $z = \lambda x + (1-\lambda)y = \lambda (a-b) + (1-\lambda) (a'-b') z \epsilon A \ominus B $
and we can modify z as $z=[\lambda a+(1-\lambda)a']-[\lambda b+(1-\lambda)b']$
let $ a''=[\lambda a+(1-\lambda )a']$ and $b'' = [\lambda b+(1-\lambda)b'] $
Therefore, $ z= a''-b''\epsilon A \ominus B,$ where $a'' \epsilon A$ and $ b'' \epsilon B $
$\endgroup$ 1
