Question

For each of the following sets, prove that thay are convex sets or not. Also graph the sets.

a) ? 1= {(?1 , ?2 ): ?1 ^2 + ?2^2 ≥ 1}

b)?2 = {(?1 ,?2 ): ?1 ^2 + ?2^ 2 = 1}

c)?3 = {(?1 , ?2 ): ?1 ^2 + ?2 ^2 ≥ 1}

Answer 1

Convex Sets

Intuitively, if we think of R2 or R3, a convex set of vectors is a set that contains all the points of any line segment joining two points of the set (see the next figure).

To be more precise, we introduce some definitions. Here, and in the following, V will always stand for a real vector space.

Definition 1.1 Let u, v ∈ V . Then the set of all convex combinations of u and v is the set of points

{wλ ∈V : wλ = (1−λ)u+λv,0≤λ≤1}. (1.1)

1

In, say, R2, this set is exactly the line segment joining the two points u and v. (See the examples below.)
Next, is the notion of a convex set.

Definition 1.2 Let K ⊂ V . Then the set K is said to be convex provided that given two points u,v ∈ K the set (1.1) is a subset of K.

We give some simple examples:

Examples 1.3

(a) An interval of [a,b] ⊂ R is a convex set. To see this, let c,d ∈ [a,b] and assume, without loss of generality, that c < d. Let λ ∈ (0, 1). Then,

a ≤ c = (1−λ)c+λc < (1−λ)c+λd < (1−λ)d+λd = d
≤ b.

2

(b) A disk with center (0, 0) and radius c is a convex subset of R . This may be easily
checked by using the usual distance formula in R2 namely ∥x−y∥ := ?(x1 − y1)2 + (x2 − y2)2 and the triangle inequality ∥u + v∥ ≤ ∥u∥ + ∥v∥. (Exercise!)

(c)InRn thesetH:={x∈Rn : a1x1+...+anxn =c}isaconvexset. Forany n

particular choice of constants ai it is a hyperplane in R . Its defining equation is a generalization of the usual equation of a plane in R3, namely the equation ax + by + cz + d = 0.

ToseethatHisaconvexset,letx(1),x(2) ∈Handdefinez∈R3 byz:=(1− (1) (2)

λ)x +λx .Then nn

= c. Hence z ∈ H.

ii i=1 i=1

? ai[(1 − λ)x(1) + λx(2)] = ?(1 − λ)aix(1) + λaix(2) iiii

z =
= (1−λ)?aix(1) +λ ?aix(2) = (1−λ)c+λc

i=1 i=1 nn

(d) As a generalization of the preceeding example, let A be an m × n matrix, b ∈ Rm, andletS:={(x∈Rn : Ax=b}. (ThesetSisjustthesetofallsolutionsof

n

A?(1−λ)x(1) +λx(2)? = (1−λ)A?x(1)?+λA?x(2)? = (1−λ)b+λb=b. Note: In (c) above, we can take A = (a1, a2, . . . , an) so that with this choice, the

present example is certainly a generalization.

We start by checking some simple properties of convex sets.
A first remark is that Rn is, itself, obviously convex. Moreover, the unit ball in Rn, namely B1 := {x ∈ Rn | ∥x∥ ≤ 1} is likewise convex. This fact follows immediately from the triangle inequality for the norm. Specifically, we have, for arbitrary x,y ∈ B1 and λ ∈ [0,1]

∥(1−λ)x+λy∥≤(1−λ)∥x∥+λ∥y∥≤(1−λ)+λ = 1. The ball B1 is a closed set. It is easy to see that, if we take its interior

B◦ := {x ∈ Rn | ∥x∥ < 1} ,
then this set is also convex. This gives us a hint regarding our next result.

Proposition 1.4 If C ⊂ Rn is convex, the cl(C), the closure of C, is also convex.

Proof: Suppose x, y ∈ cl(C). Then there exist sequences {xn}∞n=1 and {yn}∞n=1 in C such thatxn →xandyn →yasn→∞. Forsomeλ,0≤λ≤1,definezn :=(1−λ)xn+λyn. Then, by convexity of C,zn ∈ C. Moreover zn → (1−λ)x+λy as n → ∞. Hence this latter point lies in cl(C). P

The simple example of the two intervals [0, 1] and [2, 3] on the real line shows that the union of two sets is not necessarily convex. On the other hand, we have the result:

Proposition 1.5 The intersection of any number of convex sets is convex.

the linear equation Ax = b.) Then the set S is a convex subset of R . Indeed, let x(1),x(2) ∈S. Then

Proof: Let {Kα}α∈A be a family of convex sets, and let K := ∩α∈AKα. Then, for any x,y ∈ K by definition of the intersection of a family of sets, x,y ∈ Kα for all α ∈ A and each of these sets is convex. Hence for any α ∈ A,and λ ∈ [0,1], (1−λ)x+λy ∈ Kα. Hence (1 − λ)x + λy ∈ K. P Relative to the vector space operations, we have the following result:

Proposition 1.6 Let C, C1, and C2 be convex sets in Rn and let β ∈ R then (a) βC:={z∈Rn|z=βx,x∈C}isconvex.

(b) C1 + C2 := {z ∈ Rn | z = x1 + x2, x1 ∈ C1, x2 ∈ C2} is convex.

Proof: We leave part (a) to the reader. To check that part (b) is true, let z1,z2 ∈ C1 +C2 and take 0 ≤ λ ≤ 1. We take z1 = x1 + x2 with x1 ∈ C1, x2 ∈ C2 and likewise decompose z2 = y1 + y2. Then

(1−λ)z1 +λz2 = (1−λ)[x1 +x2]+λ[y1 +y2]
= [(1−λ)x1 +λy1]+[(1−λ)x2 +λy2]∈C1 +C2,

since the sets C1 and C2 are convex. P

We recall that, if A and B are two non-empty sets, then the Cartesian product of these two sets A × B is defined as the set of ordered pairs {(a,b) : a ∈ A,b ∈ B}. Notice that order does matter here and that A × B ̸= B × A! Simple examples are

1. LetA=[−1,1],B=[−1,1]sothatA×B={(x,y) : −1≤x≤1,−1≤y≤1} which is just the square centered at the origin, of side two.

2. R2 itself can be identified (and we usually do!) with the Cartesian product R × R.

3. let C ⊂ R2 be convex and let S := R+ × C. Then S is called a right cylinder and is just{(z,x)∈R3 : z>0,x∈C}. If,inparticularC={(u,v)∈R2 : u2+v2 ≤1}, then S is the usual right circulinder lying above the x, y-plane (without the bottom!).

This last example shows us a situation where A × B is convex. In fact it it a general result that if A and B are two non-empty convex sets in a vector space V , then A × B is likewise a convex set in V × V .

Exercise 1.7 Prove this last statement.

While, by definition, a set is convex provided all convex combinations of two points in the set is again in the set, it is a simple matter to check that we can extend this statement to include convex combinations of more than two points. Notice the way in which the proof is constructed; it is often very useful in computations!

p Proposition 1.8 Let K be a convex set and let λ1,λ2, ... ,λp ≥ 0 and ?λi = 1. If

x1,x2, ... xp ∈ K then

i=1

p
?λixi ∈K. (1.2)

i=1

Proof: We prove the result by induction. Since K is convex, the result is true, trivially,

for p = 1 and by definition for p = 2. Suppose that the proposition is true for p = r

(induction hypothesis!) and consider the convex combination λ1x1 +λ2x2 +. . .+λr+1xr+1. r r+1r

Define Λ := ? λi. Then since 1 − Λ = ? λi − ? λi = λr+1, we have i=1 i=1 i=1

??r? ??rλi?
λi xi +λr+1 xr+1 = Λ Λxi +(1−Λ)xr+1.

i=1 i=1
Note that ?ri=1 ?λi ? = 1 and so, by the induction hypothesis, ?ri=1 ?λi ? xi ∈ K. Since

ΛΛ
xr+1 ∈ K it follows that the right hand side is a convex combination of two points of K

and hence lies in K P Remark: We will also refer to combinations of the form (1.2) as convex combinations

of the p points x1,x2,...,xp.

For any given set which is not convex, we often want to find a set which is convex and which contains the set. Since the entire vector space V is obviously a convex set, there is always at least one such convex set containing the given one. In fact, there are infinitely many such sets. We can make a more economical choice if we recall that the intersection of any number of convex sets is convex.

Intuitively, given a set C ⊂ V , the intersection of all convex sets containing C is the “smallest” subset containing C. We make this into a definition.