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: 2 years ago

Preview 1 out of 8 pages

Buy Now

Instant download

We Accept:

We Accept
document-preview

Buy this document to get the full access instantly

Instant Download Access after purchase

Buy Now

Instant download

We Accept:

We Accept

Reviews( 0 )

$7.00

Buy Now

We Accept:

We Accept

Instant download

Can't find what you want? Try our AI powered Search

84
0

Document information


Connected school, study & course


About the document


Uploaded On

Feb 04, 2023

Number of pages

8

Written in

Seller


seller-icon
destinyd

Member since 4 years

44 Documents Sold

Reviews Received
6
1
0
0
7
Additional information

This document has been written for:

Uploaded

Feb 04, 2023

Downloads

 0

Views

 84

Document Keyword Tags


$7.00
What is Scholarfriends

In Scholarfriends, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.

We are here to help

We're available through e-mail, Twitter, Facebook, and live chat.
 FAQ
 Questions? Leave a message!

Follow us on
 Twitter

Copyright © Scholarfriends · High quality services·