Exam (elaborations) 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
Definition of convexity
2.1 Let C ⊆ Rn be a convex set, with x1 , . . . , xk ∈ C, and let θ1 , . . . , θk ∈ R satisfy θi ≥ 0,
θ1 + · · · + θk = 1. Show that θ1 x1 + · · · + θk xk ∈ 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 , x2 , x3 ∈ C,
and θ1 + θ2 + θ3 = 1 with θ1 , θ2 , θ3 ≥ 0. We will show that y = θ1 x1 + θ2 x2 + θ3 x3 ∈ 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 x1 + (1 − θ1 )(µ2 x2 + µ3 x3 )
where µ2 = θ2 /(1 − θ1 ) and µ2 = θ3 /(1 − θ1 ). Note that µ2 , µ3 ≥ 0 and
θ2 + θ 3 1 − θ1
µ1 + µ 2 = = = 1.
1 − θ1 1 − θ1
Since C is convex and x2 , x3 ∈ C, we conclude that µ2 x2 + µ3 x3 ∈ C. Since this point
and x1 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 x1 and x2 ∈ 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 ∈ 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) = c1 2−1 + c2 2−2 + · · · + ck 2−k
with ci ∈ {0, 1}, closest to θ. By midpoint convexity (applied k times, recursively),
θ(k) x + (1 − θ (k) )y ∈ C. Because C is closed,
lim (θ(k) x + (1 − θ (k) )y) = θx + (1 − θ)y ∈ C.
k→∞


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 x1 , . . . , xn ∈ S. Now let D be any convex set such that D ⊇ S. Evidently, we have
x1 , . . . , xn ∈ D. Since D is convex, and x is a convex combination of x1 , . . . , xn , 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.