Mathematics > QUESTIONS & ANSWERS > Quiz 2 Solutions (All)

Quiz 2 Solutions

Document Content and Description Below

Problem 1 (6 points) The following two questions are not related. 1) (3 points) Consider the set C = fx 2 Rn j kxk1 ≤ ng (1) Argue that this set is a pointed polyhedron in Rn, by expressing it th... rough a set of linear inequalities in Rn. Find what form the vertices of this polyhedron have. How many vertices are there? 2) (3 points) Is the point x0 = 0B@ 1 1 1 1CA a vertex in the polyhedron P described next? P = 8><>: x = 0B@ x1 x2 x3 1CA 2 R3 j xi ≥ 0; x1 + x2 ≥ 2; x1 + x3 ≥ 2; 3x1 + 2x2 + x3 ≥ 6 9>=>; (2) Solution: 1) Since kxk1 = maxi fjxijg and kxk1 ≤ n, we see that jxij ≤ n for i = 1; ::; n. Therefore, −n ≤ xi ≤ n for i = 1; :::; n and the set C can be expressed as in the following format. C = fx 2 Rn j Ax ≤ ng (3) where A = I −I !. To prove that the set C is a pointed polyhedron, we need to check its linearity space L which is the nullspace of matrix A. Since matrix A is full rank, its nullspace constains only the zero vector. Therefore, set C is indeed a pointed polyhedron. Each vertex of the set C should satisfy n linearly independent constraints with equality due to the rank condition. If we look at the constraints that define the set C, each xi should be between −n and n. Since xi cannot be equal to −n and n at the same time, each xi will be −n or n if x is a vertex so that it can satisfy n linearly independent constraints. Since each element xi can be −n or n, the set C has 2n vertices. 2) First we note that this is a pointed polyhedron, as the linearity space is empty, and thus has vertices. We then need to check the rank condition to understand if x0 is a vertex. Therefore, we first need to determine the active constraints. x0 satisfies the last three constraints with equality. Therefore, these constraints are active and we will use them to create the AJ matrix. According to rank condition, if a point is a vertex, the rank of the matrix AJ should be equal to n which is equal to 3 in this question. However, the rank of matrix AJ in (4) is 2, therefore, x0 is not a vertex. AJ = 0B@ −1 −1 0 −1 0 −1 −3 −2 −1 1CA (4) Problem 2 (7 points): Which of the following statements are true and which are false? Give a brief justification (answers without justification do not get points). [Show More]

Last updated: 2 years ago

Preview 1 out of 4 pages

Buy Now

Instant download

We Accept: