EE236A Linear Programming Midterm

EE236A Linear Programming Problem 1 (7 points): Can you express the following problems as LPs? (If yes do so, if not, explain why). Note that we do not ask you to solve these problems, only to express them as LPs if possible. 1. (2 points) Let x 2 Rn. min cT x subject to jjxjj1 ≤ 100 2. (2 points) For x1, x2 2 R min −2x1 − 3x2 subject to minfx1; x2g ≤ 4 x1; x2 ≥ 0 3. (3 points) Assume that we want to design a game, where the output x takes one of n possible values ai, with probability prob(x = ai) = pi, i = 1 : : : ; n. We also want that the probability we get the output a1 is higher than the probability we get any other output. Moreover, we want to minimize the expected value of the output, E(x) = nP i=1 piai. Can this optimization be expressed as an LP? 2Solution: 1. Yes, through the following LP min cT x subject to 1T y ≤ 100 −y ≤ x ≤ y 2. No, because the constraint minfx1; x2g ≤ 4 does not specify a convex set. 3. Yes, through the following LP min nP i=1 piai subject to pi ≥ 0; i = 1; · · · ; n nP i=1 pi = 1; p1 ≥ pi; i = 2; · · · ; n 3Problem 2 (8 points): Assume you are given a set P that contains d distinct points pi in Rn, i = 1 : : : d. We want to partition Rn into d regions, so that region Vi contains the point pi and all other points in Rn that are closer in Euclidean distance to pi than any other point in P. In other words, we wish to find the following regions (for i = 1; · · · ; d): Vi = fx 2 Rnj kx − pik2 ≤ kx − pjk2; for all j = 1; · · · ; d; such that j 6= ig (1) This is called the Voronoi region of the point pi. The Voronoi diagram is the partition of Rn into Voronoi regions. In what follows, assume that d > n. 1. (2 points) Prove that the Voronoi regions are polyhedra. The vertices of these polyhedra are called Voronoi vertices. How many Voronoi vertices can these polyhedra have? 2. (3 points) Show that every Voronoi vertex is the center of a circle that goes through at least n + 1 of the points in P. 3. (3 points) Assume that one of the d points pi was lost (e.g. due to storage errors). Let the lost point be pd. This point pd belonged in a closed Voronoi region Vd that has q > n vertices (by closed we mean that the region does not contain infinity). The information that you have retained about the Voronoi regions are: 1) the other d − 1 points (pi, i = 1; · · · ; d − 1), and 2) the set of the q Voronoi vertices for Vd. Let ^ x1; · · · ; x^q be the q Voronoi vertices of Vd. Describe a way by which you can recover the missing point pd given the information that you have. 4Solution: 1. Voronoi regions are indeed polyhedra. In fact, for a given Voronoi region i and a given point j 6= i, we can express the corresponding condition in the definition of Vi as kx−pik2 2 ≤ kx−pjk2 2 (x−pi)T (x−pi) ≤ (x−pj)2(x−pj) xT x + kpik2 2 − 2pT i x ≤ xT x + kpjk2 2 − 2pT j x 2(pj − pi)T x ≤ kpjk2 2 − kpik2 2 Therefore, Vi can be expressed as the intersection of d − 1 halfspaces, thus it is a polyhedron. A vertex has to satisfy at least n inequalities with equalities. Since there are d − 1 distinct points, there can be at most d−n1
Voronoi vertices. 2. A Voronoi vertex is a vertex in the polyhedron describing the Voronoi region. Therefore, it satisfies n inequalities of the polyhedron with equalities. Consider the Voronoi region V1, and let ^ x be a Voronoi vertex of V1. Then it satisfies kx^ − p1k2 = kx^ − pjk2; for j 2 S where S is a set of n indices, each of which are different than 1; without loss of generality, let S = f2; 3; · · · ; n + 1g. Then ^ x is at equal distance from p1; p2; · · · ; pn+1, and therefore there is a circle centered at ^ x and passes by all these n + 1 points. 3. For every Voronoi vertex ^ xj; j = 1; · · · ; q, there are at least n+1 points from the set p1; · · · ; pd that are of equal distance to ^ xj, and one of which is pd. Let this set of points be S(^ xk). Then by definition, pd 2 S(^ xj). If all the sets S(^ xk); k = 1; · · · ; q are known, then one can find the missing point pd by solving the following set of equations kpd − x^jk2 = kpk − x^ik2; for all j = 1; · · · ; q; and for one k 2 S(^ xj): These are q > n equations in n unknowns, and therefore can be used to solve for the point pd. The missing part is to find the sets S(^ xj), which can be accomplished as follows. For each x^j, compute the distance between ^ xj and all points p1; · · · ; pd−1. Then, the points in S(^ xj) will correspond to the set of points in p1; · · · ; pd−1 which has the smallest distance to ^ xj. We prove that this is true by contradiction. That is, assume that there exists a point pk 2 S = (^ xj) where kpk −x^jk < kpd −x^jk. Then this means that ^ xj does not lie in Vd and therefore cannot be a Voronoi vertex of Vd, which is a contradiction. 5Problem 3 (9 points): Consider the following LP, with variables x 2 Rn and z 2 Rn (assume that c 6= 0), max cT x subject to −z ≤ x ≤ z 1T z = 2 z ≤ 1: (2) (a) (2 points) Write the dual of this LP. (b) (4 points) Provide an optimal solution to the primal LP in (2), and argue why the solution you provided is optimal. Hint: you do not need to use the KKT conditions. (c) (1 point) Give an example of a vector c for which the optimal solution of (2) is not unique. (d) (2 points) Argue whether the optimal dual solution of the LP in (2) is unique or notMidterm