Exercises
Exercises
Definition of convexity
2.1 Let C ⊆ R
n
be a convex set, with x
1
, . . . , x
k
∈ C, and let θ
1
, . . . , θ
k
∈ R satisfy θ
i
≥ 0,
θ
1
+ ··· + θ
k
= 1. Show that θ
1
x
1
+ ··· + θ
k
x
k
∈ C. (The definition of convexity is that
this holds for k = 2; you must show it for arbitrary k.) Hint. Use induction on k.
Solution. This is readily shown by induction from the definition of convex set. We illus-
trate the idea for k = 3, leaving the general case to the reader. Suppose that x
1
, x
2
, x
3
∈ C,
and θ
1
+ θ
2
+ θ
3
= 1 with θ
1
, θ
2
, θ
3
≥ 0. We will show that y = θ
1
x
1
+ θ
2
x
2
+ θ
3
x
3
∈ C.
At least one of the θ
i
is not equal to one; without loss of generality we can assume that
θ
1
6= 1. Then we can write
y = θ
1
x
1
+ (1 − θ
1
)(µ
2
x
2
+ µ
3
x
3
)
where µ
2
= θ
2
/(1 − θ
1
) and µ
2
= θ
3
/(1 − θ
1
). Note that µ
2
, µ
3
≥ 0 and
µ
1
+ µ
2
=
θ
2
+ θ
3
1 − θ
1
=
1 − θ
1
1 − θ
1
= 1.
Since C is convex and x
2
, x
3
∈ C, we conclude that µ
2
x
2
+ µ
3
x
3
∈ C. Since this point
and x
1
are in C, y ∈ C.
2.2 Show that a set is convex if and only if its intersection with any line is convex. Show that
a set is affine if and only if its intersection with any line is affine.
Solution. We prove the first part. The intersection of two convex sets is convex. There-
fore if S is a convex set, the intersection of S with a line is convex.
Conversely, suppose the intersection of S with any line is convex. Take any two distinct
points x
1
and x
2
∈ S. The intersection of S with the line through x
1
and x
2
is convex.
Therefore convex combinations of x
1
and x
2
belong to the intersection, hence also to S.
2.3 Midpoint convexity. A set C is midpoint convex if whenever two points a, b are in C, the
average or midpoint (a + b)/2 is in C. Obviously a convex set is midpoint convex. It can
be proved that under mild conditions midpoint convexity implies convexity. As a simple
case, prove that if C is closed and midpoint convex, then C is convex.
Solution. We have to show that θx + (1 − θ)y ∈ C for all θ ∈ [0, 1] and x, y ∈ C. Let
θ
(k)
be the binary number of length k, i.e., a number of the form
θ
(k)
= c
1
2
−1
+ c
2
2
−2
+ ··· + c
k
2
−k
with c
i
∈ {0, 1}, closest to θ. By midpoint convexity (applied k times, recursively),
θ
(k)
x + (1 − θ
(k)
)y ∈ C. Because C is closed,
lim
k→∞
(θ
(k)
x + (1 − θ
(k)
)y) = θx + (1 − θ)y ∈ C.
2.4 Show that the convex hull of a set S is the intersection of all convex sets that contain S.
(The same method can be used to show that the conic, or affine, or linear hull of a set S
is the intersection of all conic sets, or affine sets, or subspaces that contain S.)
Solution. Let H be the convex hull of S and let D be the intersection of all convex sets
that contain S, i.e.,
D =
\
{D | D convex, D ⊇ S}.
We will show that H = D by showing that H ⊆ D and D ⊆ H.
First we show that H ⊆ D. Suppose x ∈ H, i.e., x is a convex combination of some
points x
1
, . . . , x
n
∈ S. Now let D be any convex set such that D ⊇ S. Evidently, we have
x
1
, . . . , x
n
∈ D. Since D is convex, and x is a convex combination of x
1
, . . . , x
n
, it follows
that x ∈ D. We have shown that for any convex set D that contains S, we have x ∈ D.
This means that x is in the intersection of all convex sets that contain S, i.e., x ∈ D.
Now let us show that D ⊆ H. Since H is convex (by definition) and contains S, we must
have H = D for some D in the construction of D, proving the claim.
