TEST BANK FOR Convex Optimization 1st Edition By Stephen Boyd (Solution Manual)

Convex Optimization
Solutions Manual
Stephen Boyd Lieven Vandenberghe
January 4, 2006
Chapter 2
Convex sets
Exercises
Exercises
Denition of convexity
2.1 Let C Rn be a convex set, with x1; : : : ; xk 2 C, and let 1; : : : ; k 2 R satisfy i 0,
1 + + k = 1. Show that 1x1 + + kxk 2 C. (The denition 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 denition of convex set. We illustrate
the idea for k = 3, leaving the general case to the reader. Suppose that x1; x2; x3 2 C,
and 1 + 2 + 3 = 1 with 1; 2; 3 0. We will show that y = 1x1 + 2x2 + 3x3 2 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 = 1x1 + (1 􀀀 1)(2x2 + 3x3)
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 x2; x3 2 C, we conclude that 2x2 + 3x3 2 C. Since this point
and x1 are in C, y 2 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 ane if and only if its intersection with any line is ane.
Solution. We prove the rst part. The intersection of two convex sets is convex. Therefore
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 x1 and x2 2 S. The intersection of S with the line through x1 and x2 is convex.
Therefore convex combinations of x1 and x2 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 2 C for all 2 [0; 1] and x; y 2 C. Let
(k) be the binary number of length k, i.e., a number of the form
(k) = c12􀀀1 + c22􀀀2 + + ck2􀀀k
with ci 2 f0; 1g, closest to . By midpoint convexity (applied k times, recursively),
(k)x + (1 􀀀 (k))y 2 C. Because C is closed,
lim
k!1
((k)x + (1 􀀀 (k))y) = x + (1 􀀀 )y 2 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 ane, or linear hull of a set S
is the intersection of all conic sets, or ane 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 =
\
fD j D convex; D Sg:
We will show that H = D by showing that H D and D H.
First we show that H D. Suppose x 2 H, i.e., x is a convex combination of some
points x1; : : : ; xn 2 S. Now let D be any convex set such that D S. Evidently, we have
x1; : : : ; xn 2 D. Since D is convex, and x is a convex combination of x1; : : : ; xn, it follows
that x 2 D. We have shown that for any convex set D that contains S, we have x 2 D.
This means that x is in the intersection of all convex sets that contain S, i.e., x 2 D.
Now let us show that D H. Since H is convex (by denition) and contains S, we must
have H = D for some D in the construction of D, proving the claim.