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

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.
2 Convex sets
Examples
2.5 What is the distance between two parallel hyperplanes fx 2 Rn j aT x = b1g and fx 2
Rn j aT x = b2g?
Solution. The distance between the two hyperplanes is jb1 􀀀 b2j=kak2. To see this,
consider the construction in the gure below.
PSfrag replacements
a x1 = (b1=kak2)a
x2 = (b2=kak2)a
aT x = b2
aT x = b1
The distance between the two hyperplanes is also the distance between the two points
x1 and x2 where the hyperplane intersects the line through the origin and parallel to the
normal vector a. These points are given by
x1 = (b1=kak22
)a; x2 = (b2=kak22)a;
and the distance is
kx1 􀀀 x2k2 = jb1 􀀀 b2j=kak2:
2.6 When does one halfspace contain another? Give conditions under which
fx j aT x bg fx j ~aT x ~ bg
(where a 6= 0, ~a 6= 0). Also nd the conditions under which the two halfspaces are equal.
Solution. Let H = fx j aT x bg and ~H = fx j ~aT x ~ bg. The conditions are:
H ~H if and only if there exists a > 0 such that ~a = a and ~b b.
H = ~H if and only if there exists a > 0 such that ~a = a and ~b = b.
Let us prove the rst condition. The condition is clearly sucient: if ~a = a and ~b b
for some > 0, then
aT x b =) aT x b =) ~aT x ~b;
i.e., H ~H.
To prove necessity, we distinguish three cases. First suppose a and ~a are not parallel. This
means we can nd a v with ~aT v = 0 and aT v 6= 0. Let ^x be any point in the intersection
of H and ~H, i.e., aT ^x b and ~aT x ~ b. We have aT (^x + tv) = aT ^x b for all t 2 R.
However ~aT (^x + tv) = ~aT ^x + t~aT v, and since ~aT v 6= 0, we will have ~aT (^x + tv) > ~b for
suciently large t > 0 or suciently small t < 0. In other words, if a and ~a are not
parallel, we can nd a point ^x + tv 2 H that is not in ~H, i.e., H 6 ~H.
Next suppose a and ~a are parallel, but point in opposite directions, i.e., ~a = a for some
< 0. Let ^x be any point in H. Then ^x􀀀ta 2 H for all t 0. However for t large enough
we will have ~aT (^x 􀀀 ta) = ~aT ^x + tkak22
>~ b, so ^x 􀀀 ta 62 ~H. Again, this shows H 6 ~H.
Exercises
Finally, we assume ~a = a for some > 0 but ~b < b. Consider any point ^x that satises
aT ^x = b. Then ~aT ^x = aT ^x = b > ~ b, so ^x 62 ~H.
The proof for the second part of the problem is similar.
2.7 Voronoi description of halfspace. Let a and b be distinct points in Rn. Show that the set
of all points that are closer (in Euclidean norm) to a than b, i.e., fx j kx􀀀ak2 kx􀀀bk2g,
is a halfspace. Describe it explicitly as an inequality of the form cT x d. Draw a picture.
Solution. Since a norm is always nonnegative, we have kx 􀀀 ak2 kx 􀀀 bk2 if and only
if kx 􀀀 ak22
kx 􀀀 bk22
, so
kx 􀀀 ak22
kx 􀀀 bk22
() (x 􀀀 a)T (x 􀀀 a) (x 􀀀 b)T (x 􀀀 b)
() xT x 􀀀 2aT x + aT a xT x 􀀀 2bT x + bT b
() 2(b 􀀀 a)T x bT b 􀀀 aT a:
Therefore, the set is indeed a halfspace. We can take c = 2(b 􀀀 a) and d = bT b 􀀀 aT a.
This makes good geometric sense: the points that are equidistant to a and b are given by
a hyperplane whose normal is in the direction b 􀀀 a.
2.8 Which of the following sets S are polyhedra? If possible, express S in the form S =
fx j Ax b; Fx = gg.
(a) S = fy1a1 + y2a2 j 􀀀 1 y1 1; 􀀀 1 y2 1g, where a1; a2 2 Rn.
(b) S = fx 2 Rn j x 0; 1T x = 1;
Pn
i=1 xiai = b1;
Pn
i=1 xia2
i = b2g, where
a1; : : : ; an 2 R and b1; b2 2 R.
(c) S = fx 2 Rn j x 0; xT y 1 for all y with kyk2 = 1g.
(d) S = fx 2 Rn j x 0; xT y 1 for all y with
Pn
i=1 jyij = 1g.
Solution.
(a) S is a polyhedron. It is the parallelogram with corners a1 + a2, a1 􀀀 a2, 􀀀a1 + a2,
􀀀a1 􀀀 a2, as shown below for an example in R2.
PSfrag replacements
a1
a2 c2
c1
For simplicity we assume that a1 and a2 are independent. We can express S as the
intersection of three sets:
S1: the plane dened by a1 and a2
S2 = fz +y1a1 +y2a2 j aT
1 z = aT
2 z = 0;􀀀1 y1 1g. This is a slab parallel to
a2 and orthogonal to S1
S3 = fz +y1a1 +y2a2 j aT
1 z = a