Take Home Due: Beginning of class, Friday, 4 November 2011.

This is to be all your own work. You may use any result from class, homeworks, or the books on reserve in the library. I will have my usual office hours on Tuesday from 12-2pm and Wednesday from 2–4pm. Do not consult anybody or anything else. The exam consists of four questions and is worth a total of 100 points.

1. (25 points) Let A be a rational m × n matrix. Use the Farkas Lemma to show that exactly one of the following systems has a solution:

   (I) Ax < 0, x ≥ 0
   (II) A^T y ≥ 0, y ≥ 0, y≠0.

2. (25 points) Let C be a positive semidefinite symmetric real n×n matrix. Let ₊ⁿ denote the convex set of symmetric n × n positive semidefinite real matrices. Let

   be a real-valued function on ₊ⁿ, where X² = XX. Prove that f is a convex function.

3. (25 points; each part is worth 5 points.) Consider the nonlinear programming problem
   1. What are the first order necessary Karush-Kuhn-Tucker conditions for this problem?
   2. Show that there are exactly two points which satisfy the first order necessary KKT conditions.
   3. Use the second order KKT conditions to determine whether either, neither, or both of these points are local minimizers.
   4. Is either of the KKT points a global minimizer?
   5. Is f(x) convex in the region x₁ ≥ a, x₂ ≥ 0 for some a > 0?
4. (25 points) Consider the quadratically constrained quadratic program

   where Q is an indefinite symmetric rational n × n matrix. Show that the primal and dual optimal values are equal for this nonconvex program.