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 L
...
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]
