Prove that the sum and difference of two convex sets in R^n are convex.

Thanks =)

---

Request for Question Clarification by elmarto-ga on 04 Oct 2003 15:20 PDT

Hi dime365,
Could you please clarify what do you mean by "sum" or "difference" of
sets? If, for example, you assume the "sum" to be the union of sets,
it's not true that the union of two convex sets is convex.

Best regards,
elmarto

Hi, dime365-ga:

Let A,B be any two convex subsets of R^n.  That is, for any element
x,y of A (resp. of B), and any real scalar t in [0,1], the "convex
combination":

tx + (1-t)y

again belongs to A (resp. to B).

First we will show that the set A+B (formed by taking all terms a+b
where a in A, b in B) is again a convex set.  For suppose x+y and
x'+y' are any two points in A+B, naturally with x,x' in A and y,y' in
B.  Given real t in [0,1], we know:

tx + (1-t)x' belongs to A

ty + (1-t)y' belongs to B

and therefore:

t(x+y) + (1-t)(x'+y') = tx + (1-t)x' + ty + (1-t)y'

will also belong to A+B.  Therefore A+B is shown to be convex.

Finally we can show the difference A-B of convex sets is convex by a
similar argument, or by noting that A-B can be considered a sum of two
convex sets, A and -B, and applying what has already been shown.

If B is convex, then so is any scalar multiple cB, e.g. in particular
(-1)B = -B.  For x belongs to B if and only if -x belongs to -B.  From
this it is easy to see that given two typical elements -x, -x' of -B
and scalar t in [0,1]:

t(-x) + (1-t)(-x') = -( tx + (1-t)x' )

again belongs to -B (because tx + (1-t)x' clearly belongs to convex
B).

Now any element a-b of A-B, where a in A and b in B, is just a + (-b),
the sum of an element from A and one from -B, and conversely.  Thus
A-B = A + (-B), so the difference of two convex sets may be considered
a "case" of the sum of two convex sets.

regards, mathtalk-ga