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
...
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).
[Show More]
