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.