Mathematics > QUESTIONS & ANSWERS > EE236A Linear Programming midterm (All)

EE236A Linear Programming midterm

Document Content and Description Below

EE236A Linear Programming midterm 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.

[Show More]

Last updated: 3 years ago

Preview 1 out of 8 pages

Get Access

Instant download after payment

Card Payments

₿ Crypto Accepted

Instant download