Homework 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Homework 1 (out of 100 points)
Problem 1 (convex sets) 20 points
• Convex Sets
1. Show that if Si ⊆ R n, i ∈ I is a collection of convex sets, then their intersection ∩i∈ISi is also convex.
2. Show that if S1 ⊆ R n and S2 ⊆ R n are convex, then so is S1 + S2.
3. Let A ∈ R m×n. Show that if S ⊆ R m is convex then so is A−1 (S) = {x ∈ R n : Ax ∈ S}, which is called the preimage of S under the map A : R n → R m.
4. Let A ∈ R m×n. Show that if S ⊆ R n is convex then so is A(S) = {Ax : x ∈ S}, called the image of S under A.
• Polyhedra:
1. Show that if P ⊆ R n is a polyhedron, and A ∈ R m×n, then A(P) is a polyhedron. Hint: you may use the fact that
P ⊆ R m+n is a polyhedron ⇒ {x ∈ R n : (x, y) ∈ P for some y ∈ R m} is a polyhedron.
2. Show that if Q ⊆ R m is a polyhedron, and A ∈ R m×n, then A−1 (Q) is a polyhedron.
Problem 2 (Radon’s Theorem) [20 points]
In this problem we prove Radon’s theorem stated below: Any set X of n + 2 points in R n can be partitioned into two sets whose convex hulls intersect.
Show the following steps and conclude that Radon’s theorem hold:
• Let X = {x 1 , . . . , x n+2}. Show that the set of multipliers
is nonempty.
• Let (α1, . . . , αn+2) be an element of this set and let X+ be the set of points in X whose multiplier is positive and X− = X \X+ be the rest of the points. Shows that these two sets are nonempty. Conclude the proof by showing that the convex hull of these two sets include the point
Problem 3 (Pertubation can remove degeneracy) [20 points]
Consider a polyhedron P = {x|Ax ≥ b}, with A ∈ R m×n. Given any > 0, show that there exists some ¯b such that |bi − ¯bi | ≤ for all 1 ≤ i ≤ m and every basic feasible solution in P¯ = {x|Ax ≥ ¯b} is nondegenerate. (A basic solution is nondegenerate if it has more than n active constraints.)
Problem 4 (Sum of Polyhedra) [20 points]
Let P and Q be polyhedra in R n. Let P + Q = {x + y|x ∈ P, y ∈ Q}. Show that
1. P + Q is a polyhedron.
2. Every extreme point in P + Q is the sum of an exteme point of P and an extreme point of Q.
Problem 5 [20 points]
Let [n] = {1, . . . n}. Given a ∈ R n + and b ∈ R m+ , consider the optimization problem
1. Prove that any basic solution has at most n + m + 1 non-zero entries.
2. Suppose that we add the constraints xij ≤ aj , ∀i ∈ [m], j ∈ [n] into the optimization problem. Does the previous statement still hold?
Problem 6 (Inconsistent systems of linear inequalities) [20 points]
Let a1, . . . , am be vectors in R n, with m ≥ n + 1. Suppose that the system of inequalities, a > x ≥ bi , for i = 1, . . . m, does not have any feasible solution. Show that we can choose n + 1 of these inequalities such that the resulting system of inequalities has no solutions.
Problem 7 (Helly’s Theorem) [20 points]
1. Prove Helly’s theorem stated below: For any collection of m ≥ n+ 1 nonempty polyhedra {P1, . . . , Pm} in R n with the property that the intersection of any n + 1 sets from this collection is nonempty, we have
Hint: Use the previous probelm 3. Alternatively, you may use Radon’s Theorem.
2. For n = 2, Helly’s theorem asserts that for if every three of the polyhedra in {P1, . . . , Pm} have a point in common, then all of them have a point in common. Construct an example (for n = 2), where every two of the polyhera have a point in common, but
Problem 8 (Saddle points of the Lagrangean) [20 points]
Recall that a linear program in standard form can be formulated as
where L(x, y) := c > x+y T (b− Ax) is the Lagrangean function. A pair of (x ∗ , y ∗ ) is called a saddle point if
Show that (x ∗ , y ∗ ) is a saddle point if and only if x ∗ and y ∗ are optimal solutions of the primal and the dual of the LP, respectively.
2023-10-24