MATP6600 / DSES6780 Nonlinear Programming

Midterm Exam, Fall 2009

Take Home Due: Beginning of class, Friday, 6 November 2009.

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 2-3pm and Wednesday from 11am-noon. Do not consult anybody or anything else. The exam consists of four questions and is worth a total of 100 points.

  1. (20 points)
    Assume both the primal and dual linear programming problems are feasible in the following primal-dual pair
    T T minx c x maxy,s b y s.t. Ax = b (P) s.t. AT y + s = c (D ) x ≥ 0 s ≥ 0

    where x, s, and c are n-vectors, y and b are m-vectors, A is m × n of rank m, and n ≥ m ≥ 1. Let C be the set of feasible solutions to (P) and W be the set of feasible solutions to (D). Show that for any component i, either xi is unbounded in C or si is unbounded in W.

  2. (20 points)
    Let ¯x be a feasible solution to the quadratic programming problem
    minx cT x + 1xT Qx 2 subject to Ax ≥ b

    where x,c ∈ IRn, b is an m-vector, A is m×n of rank n, and Q is a symmetric n×n matrix with k negative eigenvalues. Assume p of the linear constraints are active at x¯, and the active constraints are linearly independent. Show that if p < k then ¯x cannot satisfy the second order necessary KKT conditions.

  3. (40 points)
    Consider the nonlinear programming problem
    min 4x1x2 - x1 - 2x2 subject to - x + x ≤ 0 (N LP ) 1 2 0 ≤ x1,x2 ≤ 1

    1. (10 points) Find all the KKT points for (NLP). Which of them satisfy the second order sufficient conditions?
    2. (5 points) What is the global solution to (NLP)? Justify your answer.
    3. A Lagrangian dual function can be constructed as
      min 4x1x2 - x1 - 2x2 + u(- x1 + x2) θ(u) := subject to 0 ≤ x1,x2 ≤ 1 (LR (u))

      1. (5 points) Use the result of Question 2 to show that the optimal solution x to (LR(u)) must be on the boundary of the feasible region.
      2. (10 points) Find θ(u) for all u ≥ 0.
      3. (5 points) Show that the optimal dual value is smaller than the optimal primal value.
      4. (5 points) Show explicitly that ξ = 0 is in the convex hull of subgradients of θ(u) arising from optimal solutions to (LR(u)) at the optimal u.
  4. (20 points)
    Let f : IRn → IR be a convex function. Define the function g(x,s) = sf(1 sx) where x ∈ IRn and s is a positive scalar. Prove that g is a convex function of x and s. Hence show that the function h(x1,x2) := x12∕x 2 is convex for x2 > 0, where x1 and x2 are scalars. Is h(x1,x2) strictly convex for x2 > 0?
    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Tuesday 2.0 – 3.0, Wednesday 11.0 – 12.0.