1. Convex Sets 3

(1.3) Some interesting examples. Sometimes, it is very easy to see whether

the set is convex or not (see Figure 1).

convex convex non-convex

Figure 1. Two convex and one non-convex set

Sometimes, however, this is not so easy to see (cf. Problems 3, 4 and 5 below),

or a convex set may have a number of equivalent descriptions and their equivalence

may be not obvious (cf. Problems 6 and 7 below).

PROBLEMS.

We will encounter many of the harder problems later in the text.

1◦.

Prove that the convex hull of a set is a convex set.

2◦.

Let c1,... , cm be vectors from

Rd

and let β1,... , βm be numbers. The set

A = x ∈

Rd

: ci,x ≤ βi for i = 1, . . . , m

is called a polyhedron. Prove that a polyhedron is a convex set.

3. Let v1,... , vm ∈ Rd be points. Let us fix positive numbers ρ1,... , ρm and

let us define a map: H : Rd −→ Rd by

H(x) =

1

f(x)

m

i=1

ρi exp x, vi vi, where f(x) =

m

i=1

ρi exp x, vi .

a◦)

Prove that the image of H lies in the convex hull of v1,... , vm.

b∗)

Prove that the image of H is convex and that for 0 and for any

y ∈ conv

(

v1,... , vm

)

there exists an x ∈ Rd such that dist

(any

H(x),y

)

.