EE236A Linear Programming

EE236A Linear Programming EE236A Linear Programming Quiz 2 Solutions This quiz has 3 questions, for a total of 20 points. Open book. The exam is for a total of 1:00 hour. Please, write your name and UID on the to ...

EE236A Linear Programming EE236A Linear Programming Quiz 2 Solutions This quiz has 3 questions, for a total of 20 points. Open book. The exam is for a total of 1:00 hour. Please, write your name and UID on the top of each sheet. Good luck! Problem Mark Total P1 6 P2 7 P3 7 Total 20 1Problem 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. minx1;x2;y1;y2 −cT (x1 − x2) subject to A(x1 − x2) + y1 − y2 = 0 y1 + y2 = λ1 x1 ≥ 0; x2 ≥ 0; y1 ≥ 0; y2 ≥ 0 (11) maxz cT z subject to kAzk1 ≤ λ (12) Solution: We will start from the first problem (11), and show that a feasible solution allows to construct a feasible solution for the program in (12) that achieves the same objective function value. For this, we will select z = x1 − x2. Consider x1; x2; y1; y2 are feasible and set z = x1 − x2, then we have that Az = y2 − y1. Because y1; y2 are positive, then −y1 − y2 ≤ y2 − y1 ≤ y1 + y2. Moreover y1 + y2 = λ1 which also implies that −y1 −y2 = −λ1. Then we have −λ1 ≤ y2 −y1 ≤ λ1. This gives us −λ1 ≤ AT z ≤ λ1, and thus kAT zk1 ≤ λ. That is, z is feasible in (12). Moreover a minimization problem can be converted to a maximization problem by negating the objective function, and the objective function value is the same. This concludes the first direction. Second, we start from a feasible solution in (12) and argue that we can achieve a feasible solution in (11) that achieves the same objective function value. Again, a maximization problem can be converted to a minimization problem by negating the objective function. Let y1 be a nonnegative variable y1 such that AT z + 2y1 = λ · 1 and let y2 be a nonnegative variable y2 such that AT z − 2y2 = −λ · 1. By summing up those two constraints we get that 2(AT z + y1 − y2) = 0; by subtracting them we get that y1 + y2 = λ1. Next, we select nonnegative variables x1 and x2, such that x1 : x1i = maxfzi; 0g, and x2 : x2i = maxf−zi; 0g. Clearly z = x1 − x2 and thus A(x1 − x2) + y1 − y2 = 0. From construction, we also have that x1 ≥ 0; x2 ≥ 0; y1 ≥ 0; y2 ≥ 0. Thus the selected variables are feasible in (11) and achieve the same objective function value.