MS&E 211 Homework #2 Course Instructor : Yinyu Ye Due Date: Oct 20th, 2016 Problem 1. Which of the following sets are convex? If they are convex explain why, otherwise give a counter-example. (a) The set of points closer to a given point x0 than another point y: W = {x| kx x0 k2 kx yk2 } Hint: can you transform the constraint into a linear inequality? (b) The set of points closer to a given point than a given set, i.e., U = {x| kx x0 k2 kx yk2 for all y S} where S Rn . Hint: what can we say about the intersection of convex sets? (c) The set of points closer to one set than another, i.e., V = {x| dist(x, S) dist(x, T )} where S, T Rn , and dist(x, S) = min{kx zk2 |z S}. Hint: consider S, T {1, 2, 3} Problem 2. Consider the standard form polyhedron P = {~x : A~x = ~b, ~x ~0}. Suppose that the matrix A has dimensions m n and that its rows are linearly independent. For each one of the following statements, state whether it is true or false. If true, provide a brief reason; else, provide a counterexample. (a) The set of all optimal solutions is always bounded. (b) At every optimal solution, no more than m variables can be positive. (c) If there is more than one optimal solution, then there are infinitely many optimal solutions. (d) Consider the problem of minimizing max{~cT ~x, d~T ~x} over the set P . If this problem has an optimal solution, it must have an optimal solution which is an extreme point of P . Problem 3. Use Simplex method with starting basis {1, 2} to solve the following problem. Please use Dantzig's pivoting rule (see lecture 4 notes). minimize: 5x1 x2 4x3 subject to: x1 + 2x3 = 4 x1 + x2 = 5 xj 0, j = 1, 2, 3 Problem 4. (a) Starting from the solution with xi = 0 use the simplex method, to solve the following problem. Please use Dantzig's pivoting rule (see lecture 4 notes). maximize: 2x1 + 4x2 + x3 + x4 subject to: x1 + 3x2 + x4 4 2x1 + x2 3 x2 + 4x3 + x4 3 xi 0, i = 1, 2, 3, 4 (b) What are the optimal dual prices? Problem 5. Let f (x) = 5 + 2x x2 and g(x) = 5 2x + x2 . Let A = {(x, y) : 1 x 3, 0 y f (x)} and B = {(x, y) : 1 x 3, 0 y g(x)}. (a) Is f (x) a concave function? Is g(x) a concave function? Why or why not? (b) Is A a convex set? Is B a convex set? Why or why not