MATHEMATICAL PROGRAMMING Depth Exam: Answer any 6 of the following 8 questions Breadth Exam: Answer any 3 of the following 8 questions

1. Solve by the simplex method the following Linear Programming Problem:

max  − 4x_{2} − 2x_{3} − 7x_{4}
s.t. \begin{aligned}2x_{1} & + & x_{2} & + & x_{3} & + & 3x_{4} & = & 3 \\ x_{1} & − & x_{2} & & & + & x_{4} & ≤ & 1 \\ 2x_{1} & + & 2x_{2} & & & + & 4x_{4} & ≤ & 3 \end{aligned}
x_{i} ≥ 0 i = 1,…, 4

Hint: Start with x_{3} as a basic variable even though it also occurs in the objective function.

3. Let f : R^{n} → R be a differentiable convex function on R^{n} and let x^{1},…, x^{k} be k points in R^{n} such that for some ū ∈ R^{k} :

∑_{i=1}^{k} ū_{i}∇f(x^{i}) = 0, ∑_{i=1}^{k} ū_{i} = 1, ū ≥ 0

Give a lower bound to inf_{x∈R^{n}} f(x) in terms of x^{1},…, x^{k} and ū.