EE236A Linear Programming Quiz 2 Solutions - UCLA

Linear Programming Quiz 2 Solution 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 through 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). 2• (i) (2 points) Consider m points in Rn with m > n. The convex hull of these points is a polyhedron with exactly m vertices. • (ii) (2 points) The minimal face of a polyhedron is always a single point. • (iii) (3 points) Let P ⊆ Rd and Q ⊂ Re be polytopes. Then the following set S ⊆ Rd+e+1 is also a polytope, where: S = 8><>: z 2 Rd+e+1jz = 0B@ x 0 0 1CA + 0B@ 0 y 1 1CA ; with x 2 P and y 2 Q 9>=>; (5) Solution: • The statement is FALSE because some of these points can belong in the convex hull of others, and will not be vertices in this case (eg consider three points on the same line). • The statement is FALSE. The polyhedron should be a pointed polyhedron in order for the minimal face to be a single point. Consider the following polyhedron. P = x 2 Rn j aT x ≤ b (6) For this polyhedron, the minimal face will be a hyperplane. • The statement is TRUE. If a set is a polytope, it means it is a bounded polyhedron. Therefore, the elements of a vector z in the polytope cannot go to infinity. In (5), the first d elements of a vector z are elements of a vector x from polytope P, therefore, they won’t go to infinity. The next e elements of the vector z are elements of a vector y from polytope Q and they won’t go to infinity as well. Finally, the last element of the vector z is a scalar constant and it won’t go to infinity. Hence, the set of points z is from a bounded set defined with hyperplanes i.e. (5) is indeed a polytope. To see that the region is indeed a polyhedron, let us define polyhedrons P and Q: P = nx 2 Rd j Apx ≤ bpo (7) Q = fy 2 Re j Aqy ≤ bqg (8) Then we can write the polyhedron for z as follows: Z = nz 2 Rd+e+1 j Azz ≤ bzo (9) where: Az = 0BBBB@ A p 0 : : : 0 0 : : : A q 0 0 : : : 0 : : : 1 0 : : : 0 : : : −1 1CCCCA and bz = 0BBBB@ b p b q 1 − 1 1CCCCA (10) 3Problem 3 (7 points) Assume x1; x2; y1; y2; z 2 Rn, A is a given m × n matrix, λ is a constant and c is a given column vector of dimension n × 1. Prove that the following two programs, (11) and (12), are equivalent.