EE364a Homework 1 solutions - Stanford Engineering …

1 EE364a , Winter 2007-08 Prof. S. BoydEE364a Homework 1 LetC Rnbe a convex set, withx1, .. , xk C, and let 1, .. , k Rsatisfy i 0, 1+ + k= 1. Show that 1x1+ + kxk C. (The definition of convexity is thatthis holds fork= 2; you must show it for arbitraryk.) induction is readily shown by induction from the definition of convex set. Weillustrate the idea fork= 3, leaving the general case to the reader. Suppose thatx1, x2, x3 C, and 1+ 2+ 3= 1 with 1, 2, 3 0. We will show thaty= 1x1+ 2x2+ 3x3 C. At least one of the iis not equal to one; without loss ofgenerality we can assume that 16= 1. Then we can writey= 1x1+ (1 1)( 2x2+ 3x3)where 2= 2/(1 1) and 2= 3/(1 1). Note that 2, 3 0 and 1+ 2= 2+ 31 1=1 11 1= convex andx2, x3 C, we conclude that 2x2+ 3x3 C.

2 Since this pointandx1are inC,y Show that a set is convex if and only if its intersection withany line is convex. Showthat a set is affine if and only if its intersection with any line prove the first part. The intersection of two convex sets is ifSis a convex set, the intersection ofSwith a line is , suppose the intersection ofSwith any line is convex. Take any two distinctpointsx1andx2 S. The intersection ofSwith the line throughx1andx2is convex combinations ofx1andx2belong to the intersection, hence also What is the distance between two parallel hyperplanes{x Rn|aTx=b1}and{x Rn|aTx=b2}? distance between the two hyperplanes is|b1 b2|/kak2. To see this,consider the construction in the figure (b1/kak2)ax2= (b2/kak2)aaTx=b2aTx=b1 The distance between the two hyperplanes is also the distance between the two pointsx1andx2where the hyperplane intersects the line through the origin and parallel tothe normal vectora.

3 These points are given byx1= (b1/kak22)a,x2= (b2/kak22)a,and the distance iskx1 x2k2=|b1 b2| description of distinct points inRn. Show that theset of all points that are closer (in Euclidean norm) toathanb, ,{x|kx ak2 kx bk2}, is a halfspace. Describe it explicitly as an inequality of theformcTx a a norm is always nonnegative, we havekx ak2 kx bk2if andonly ifkx ak22 kx bk22, sokx ak22 kx bk22 (x a)T(x a) (x b)T(x b) xTx 2aTx+aTa xTx 2bTx+bTb 2(b a)Tx bTb , the set is indeed a halfspace. We can takec= 2(b a) andd=bTb makes good geometric sense: the points that are equidistant toaandbare givenby a hyperplane whose normal is in the directionb Which of the following setsSare polyhedra? If possible, expressSin the formS={x|Ax b, F x=g}.

4 (a)S={y1a1+y2a2| 1 y1 1, 1 y2 1}, wherea1, a2 Rn.(b)S={x Rn|x 0,1Tx= 1, ni=1xiai=b1, ni=1xia2i=b2}, wherea1, .. , an Randb1, b2 (c)S={x Rn|x 0, xTy 1 for allywithkyk2= 1}.(d)S={x Rn|x 0, xTy 1 for allywith ni=1|yi|= 1}.Solution.(a)Sis a polyhedron. It is the parallelogram with cornersa1+a2,a1 a2, a1+a2, a1 a2, as shown below for an example simplicity we assume thata1anda2are independent. We can expressSasthe intersection of three sets: S1: the plane defined bya1anda2 S2={z+y1a1+y2a2|aT1z=aT2z= 0, 1 y1 1}. This is a slab paralleltoa2and orthogonal toS1 S3={z+y1a1+y2a2|aT1z=aT2z= 0, 1 y2 1}. This is a slab paralleltoa1and orthogonal toS1 Each of these sets can be described with linear inequalities. S1can be described asvTkx= 0, k= 1.

5 , n 2wherevkaren 2 independent vectors that are orthogonal toa1anda2(which form a basis for the nullspace of the matrix [a1a2]T). Letc1be a vector in the plane defined bya1anda2, and orthogonal example, we can takec1=a1 S2if and only if |cT1a1| cT1x |cT1a1|.3 Similarly, letc2be a vector in the plane defined bya1anda2, and orthogonaltoa1, ,c2=a2 S3if and only if |cT2a2| cT2x |cT2a2|.Putting it all together, we can describeSas the solution set of 2nlinear inequal-itiesvTkx 0, k= 1, .. , n 2 vTkx 0, k= 1, .. , n 2cT1x |cT1a1| cT1x |cT1a1|cT2x |cT2a2| cT2x |cT2a2|.(b)Sis a polyhedron, defined by linear inequalitiesxk 0 and three equality con-straints.(c)Sis not a polyhedron. It is the intersection of the unit ball{x|kxk2 1}andthe nonnegative orthantRn+.

6 This follows from the following fact, which followsfrom the Cauchy-Schwarz inequality:xTy 1 for allywithkyk2= 1 kxk2 in this example we defineSas an intersection of halfspaces, it is not apolyhedron, because the definition requires infinitely many halfspaces.(d)Sis a the intersection of the set{x||xk| 1, k= 1, .. , n}and the nonnegative orthantRn+. This follows from the following fact:xTy 1 for allywithn i=1|yi|= 1 |xi| 1, i= 1, .. , can prove this as follows. First suppose that|xi| 1 for alli. ThenxTy= ixiyi i|xi||yi| i|yi|= 1if i|yi|= , suppose thatxis a nonzero vector that satisfiesxTy 1 for allywith i|yi|= 1. In particular we can make the following choice fory: letkbean index for which|xk|= maxi|xi|, and takeyk= 1 ifxk>0,yk= 1 ifxk<0,andyi= 0 fori6=k.

7 With this choice ofywe havexTy= ixiyi=ykxk=|xk|= maxi|xi|.4 Therefore we must have maxi|xi| this implies that we can describeSby a finite number of linear inequalities:it is the intersection of the nonnegative orthant with the set{x| 1 x 1}, , the solution of 2nlinear inequalities xi 0, i= 1, .. , nxi 1, i= 1, .. , that as in part (c) the setSwas given as an intersection of an infinitenumber of halfspaces. The difference is that here most of the linear inequalitiesare redundant, and only a finite number are needed to of these sets are affine sets or subspaces, except in some trivial cases. For example,the set defined in part (a) is a subspace (hence an affine set), ifa1=a2= 0; the setdefined in part (b) is an affine set ifn= 1 andS={1}; that thehyperbolic set{x R2+|x1x2 1}is convex.

8 As ageneralization, show that{x Rn+| ni=1xi 1}is , b 0 and0 1, thena b1 a+ (1 )b; see (a) We prove the first part without using the hint. Consider a convex combinationzof two points (x1, x2) and (y1, y2) in the set. Ifx y, thenz= x+ (1 )y yand obviouslyz1z2 y1y2 1. Similar proof ify xandx6 y, , (y1 x1)(y2 x2)<0. Then( x1+ (1 )y1)( x2+ (1 )y2)= 2x1x2+ (1 )2y1y2+ (1 )x1y2+ (1 )x2y1= x1x2+ (1 )y1y2 (1 )(y1 x1)(y2 x2) 1.(b) Assume that ixi 1 and iyi 1. Using the inequality in the hint, we have i( xi+ (1 )yi) x iy1 i= ( ixi) ( iyi)1 Which of the following sets are convex?(a) Aslab, , a set of the form{x Rn| aTx }.(b) Arectangle, , a set of the form{x Rn| i xi i, i= 1, .. , n}. Arectangle is sometimes called ahyperrectanglewhenn >2.

9 (c) Awedge, ,{x Rn|aT1x b1, aT2x b2}.5(d) The set of points closer to a given point than a given set, ,{x|kx x0k2 kx yk2for ally S}whereS Rn.(e) The set of points closer to one set than another, ,{x|dist(x, S) dist(x, T)},whereS, T Rn, anddist(x, S) = inf{kx zk2|z S}.(f) The set{x|x+S2 S1}, whereS1, S2 RnwithS1convex.(g) The set of points whose distance toadoes not exceed a fixed fraction of thedistance tob, , the set{x|kx ak2 kx bk2}. You can assumea6=band0 (a) A slab is an intersection of two halfspaces, hence it is a convex set and a polyhe-dron.(b) As in part (a), a rectangle is a convex set and a polyhedron because it is a finiteintersection of halfspaces.(c) A wedge is an intersection of two halfspaces, so it is convex and a polyhedron.

10 Itis a cone ifb1= 0 andb2= 0.(d) This set is convex because it can be expressed as y S{x|kx x0k2 kx yk2}, , an intersection of halfspaces. (Recall from exercise that,for fixedy, theset{x|kx x0k2 kx yk2}is a halfspace.)(e) In general this set is not convex, as the following exampleinRshows. WithS={ 1,1}andT={0}, we have{x|dist(x, S) dist(x, T)}={x R|x 1/2 orx 1/2}which clearly is not (f) This set is +S2 S1ifx+y S1for ally S2. Therefore{x|x+S2 S1}= y S2{x|x+y S1}= y S2(S1 y),the intersection of convex setsS1 y.(g) The set is convex, in fact a ball.{x|kx ak2 kx bk2}={x|kx ak22 2kx bk22}={x|(1 2)xTx 2(a 2b)Tx+ (aTa 2bTb) 0}If = 1, this is a halfspace. If <1, it is a ball{x|(x x0)T(x x0) R2},with centerx0and radiusRgiven byx0=a 2b1 2,R=( 2kbk22 kak221 2+kx0k22)1 sets of probability a real-valued random variable withprob(x=ai) =pi,i= 1.