第1页 / 共302页
第2页 / 共302页
第3页 / 共302页
第4页 / 共302页
第5页 / 共302页
第6页 / 共302页
第7页 / 共302页
第8页 / 共302页
凸优化 王书宁 答案.pdf
Chapter 4
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 illus-
trate 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
where 2 = 2=(1 1) and 2 = 3=(1 1). Note that 2; 3 0 and
y = 1x1 + (1 1)(2x2 + 3x3)
1 + 2 =
= 1:
2 + 3
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. 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 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) = c121 + c222 + + ck2k
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.
x2 = (b2=kak2)a
PSfrag replacements
a
x1 = (b1=kak2)a
aT x = b2
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
aT x = b1
and the distance is
x1 = (b1=kak2
2)a;
x2 = (b2=kak2
2)a;
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
In other words, if a and ~a are not
suciently large t > 0 or suciently small t < 0.
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
2 > ~b, so ^x ta 62 ~H. Again, this shows H 6 ~H.
we will have ~aT (^x ta) = ~aT ^x + tkak2
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 kxak2 kxbk2g,
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 ak2
2, so
2 kx bk2
kx ak2
2 kx bk2
2 () (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:
2.8 Which of the following sets S are polyhedra? If possible, express S in the form S =
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.
fx j Ax b; F x = gg.
(a) S = fy1a1 + y2a2 j 1 y1 1; 1 y2 1g, where a1; a2 2 Rn.
i=1 xia2
i = b2g, where
a1; : : : ; an 2 R and b1; b2 2 R.
(b) S = fx 2 Rn j x 0; 1T x = 1; Pn
(d) S = fx 2 Rn j x 0; xT y 1 for all y with Pn
(c) S = fx 2 Rn j x 0; xT y 1 for all y with kyk2 = 1g.
i=1 xiai = b1; 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.
c2
a2
a1
PSfrag replacements
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
a2 and orthogonal to S1
S3 = fz + y1a1 + y2a2 j aT
a1 and orthogonal to S1
1 z = aT
1 z = aT
2 z = 0;1 y1 1g. This is a slab parallel to
2 z = 0;1 y2 1g. This is a slab parallel to
Each of these sets can be described with linear inequalities.
S1 can be described as
vT
k x = 0; k = 1; : : : ; n 2
where vk are n 2 independent vectors that are orthogonal to a1 and a2 (which
form a basis for the nullspace of the matrix [a1 a2]T ).
2 Convex sets
Let c1 be a vector in the plane dened by a1 and a2, and orthogonal to a2. For
example, we can take
Then x 2 S2 if and only if
c1 = a1
aT
1 a2
ka2k2
2
a2:
jcT
1 a1j cT
1 x jcT
1 a1j:
Similarly, let c2 be a vector in the plane dened by a1 and a2, and orthogonal
to a1, e.g.,
Then x 2 S3 if and only if
c2 = a2
aT
2 a1
ka1k2
2
a1:
jcT
2 a2j cT
2 x jcT
2 a2j:
Putting it all together, we can describe S as the solution set of 2n linear inequalities
vT
k x 0; k = 1; : : : ; n 2
vT
k x 0; k = 1; : : : ; n 2
1 x jcT
cT
cT
1 x jcT
cT
2 x jcT
cT
2 x jcT
1 a1j
1 a1j
2 a2j
2 a2j:
(b) S is a polyhedron, dened by linear inequalities xk 0 and three equality con-
straints.
(c) S is not a polyhedron. It is the intersection of the unit ball fx j kxk2 1g and the
+. This follows from the following fact, which follows from
nonnegative orthant Rn
the Cauchy-Schwarz inequality:
xT y 1 for all y with kyk2 = 1 () kxk2 1:
Although in this example we dene S as an intersection of halfspaces, it is not a
polyhedron, because the denition requires innitely many halfspaces.
(d) S is a polyhedron. S is the intersection of the set fx j jxkj 1; k = 1; : : : ; ng and
+. This follows from the following fact:
the nonnegative orthant Rn
xT y 1 for all y with
jyij = 1 () jxij 1;
i = 1; : : : ; n:
We can prove this as follows. First suppose that jxij 1 for all i. Then
xT y =Xi
jxijjyij Xi
jyij = 1
nXi=1
xiyi Xi
ifPi jyij = 1.
Pi jyij = 1. In particular we can make the following choice for y: let k be an index
Conversely, suppose that x is a nonzero vector that satises xT y 1 for all y with
for which jxkj = maxi jxij, and take yk = 1 if xk > 0, yk = 1 if xk < 0, and yi = 0
for i 6= k. With this choice of y we have
xT y =Xi
xiyi = ykxk = jxkj = max
i
jxij:
Exercises
Therefore we must have maxi jxij 1.
All this implies that we can describe S by a nite number of linear inequalities: it
is the intersection of the nonnegative orthant with the set fx j 1 x 1g, i.e.,
the solution of 2n linear inequalities
xi 0;
xi 1;
i = 1; : : : ; n
i = 1; : : : ; n:
Note that as in part (c) the set S was given as an intersection of an innite number of
halfspaces. The dierence is that here most of the linear inequalities are redundant,
and only a nite number are needed to characterize S.
None of these sets are ane sets or subspaces, except in some trivial cases. For example,
the set dened in part (a) is a subspace (hence an ane set), if a1 = a2 = 0; the set
dened in part (b) is an ane set if n = 1 and S = f1g; etc.
2.9 Voronoi sets and polyhedral decomposition. Let x0; : : : ; xK 2 Rn. Consider the set of
points that are closer (in Euclidean norm) to x0 than the other xi, i.e.,
V = fx 2 Rn j kx x0k2 kx xik2; i = 1; : : : ; Kg:
V is called the Voronoi region around x0 with respect to x1; : : : ; xK .
(a) Show that V is a polyhedron. Express V in the form V = fx j Ax bg.
(b) Conversely, given a polyhedron P with nonempty interior, show how to nd x0; : : : ; xK
so that the polyhedron is the Voronoi region of x0 with respect to x1; : : : ; xK .
(c) We can also consider the sets
Vk = fx 2 Rn j kx xkk2 kx xik2; i 6= kg:
The set Vk consists of points in Rn for which the closest point in the set fx0; : : : ; xKg
is xk.
The sets V0; : : : ; VK give a polyhedral decomposition of Rn. More precisely, the sets
k=0 Vk = Rn, and int Vi \ int Vj = ; for i 6= j, i.e., Vi and Vj
i=1 Pi = Rn, and int Pi \
int Pj = ; for i 6= j. Can this polyhedral decomposition of Rn be described as
the Voronoi regions generated by an appropriate set of points?
Vk are polyhedra,SK
Suppose that P1; : : : ; Pm are polyhedra such that Sm
intersect at most along a boundary.
Solution.
(a) x is closer to x0 than to xi if and only if
kx x0k2 kx xik2 () (x x0)T (x x0) (x xi)T (x xi)
i x + xT
i xi
() xT x 2xT
0 x + xT
() 2(xi x0)T x xT
0 x0 xT x 2xT
i xi xT
0 x0;
which denes a halfspace. We can express V as V = fx j Ax bg with
A = 22664
x1 x0
x2 x0
...
xK x0
3775 ;
b =2664
1 x1 xT
xT
2 x2 xT
xT
0 x0
0 x0
...
K xK xT
xT
0 x0
3775 :
2 Convex sets
(b) Conversely, suppose V = fx j Ax bg with A 2 RKn and b 2 RK . We can pick
any x0 2 fx j Ax bg, and then construct K points xi by taking the mirror image
of x0 with respect to the hyperplanes fx j aT
i x = big. In other words, we choose xi
of the form xi = x0 + ai, where is chosen in such a way that the distance of xi to
the hyperplane dened by aT
i x = bi is equal to the distance of x0 to the hyperplane:
bi aT
Solving for , we obtain = 2(bi aT
i xi bi:
2, and
i x0 = aT
i x0)=kaik2
2(bi aT
kaik2
xi = x0 +
i x0)
ai:
(c) A polyhedral decomposition of Rn can not always be described as Voronoi regions
generated by a set of points fx1; : : : ; xmg. The gure shows a counterexample in
R2.
P1
P2
~P1
P3
~P2
H1
PSfrag replacements
P4
H2
R2 is decomposed into 4 polyhedra P1; : : : ; P4 by 2 hyperplanes H1; H2. Suppose
we arbitrarily pick x1 2 P1 and x2 2 P2. x3 2 P3 must be the mirror image of x1
and x2 with respect to H2 and H1, respectively. However, the mirror image of x1
with respect to H2 lies in ~P1, and the mirror image of x2 with respect to H1 lies in
~P2, so it is impossible to nd such an x3.
2.10 Solution set of a quadratic inequality. Let C Rn be the solution set of a quadratic
inequality,
C = fx 2 Rn j xT Ax + bT x + c 0g;
with A 2 Sn, b 2 Rn, and c 2 R.
(a) Show that C is convex if A 0.
(b) Show that the intersection of C and the hyperplane dened by gT x + h = 0 (where
g 6= 0) is convex if A + ggT 0 for some 2 R.
Are the converses of these statements true?
Solution. A set is convex if and only if its intersection with an arbitrary line f^x + tv j t 2
Rg is convex.
(a) We have
(^x + tv)T A(^x + tv) + bT (^x + tv) + c = t2 + t +
where
= vT Av;
= bT v + 2^xT Av;
= c + bT ^x + ^xT A^x:
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
