Name:

MATP6600/DSES6780 Nonlinear Programming,
Final Exam, Friday, December 11, 2009.

Please do all three problems. You must show all work to obtain full credit. Results from class or the text may be used if properly stated. No books or calculators allowed. The exam lasts one hour and 50 minutes.

(40 points; each part is worth 10 points.) Consider the unconstrained problem $min f (x) := 1(x - 2)2 + x4, (P ) 2$
where x IR. We are going to investigate a bundle method for solving this problem. Let = 0 be the current point. A bundle subproblem for (P) is
$1 2 minx,z z + 2(x - ¯x) (BQP ) subject to - z - 2x ≤ - 2$
where z and x are variable scalars.
1. Show that the optimal solution to the bundle subproblem (BQP) is to take x = 2.
2. Show that the objective function value for x = 2 predicted by the bundle subproblem is noticeably less than the actual value f(2).
3. What is the valid subgradient inequality generated at the point x = 2? Show that the inequality is violated by the solution to (BQP).
4. Add the constraint found in part 1c to (BQP) and find the new optimal solution, assuming a null step was taken so we still have = 0.
(40 points.) Consider the quadratic programming problem $T 1 T min c x + 2x Qx (QP ) s.t. Ax ≥ b$
where x and c are n-vectors, Q is symmetric and positive semidefinite, b is an m-vector, and A is m × n.
1. (20 points) Show that the Lagrangian dual of (QP) can be written $maxx,u bTu - 12xTQx subject to c + Qx - AT u = 0 (QD ) u ≥ 0$
2. (10 points) Let , be a feasible solution to (QD). Assume there exists an n-vector d_x with d_x^TQd_x = 0. Show that Qd_x = 0. Assume there also exists a nonnegative m-vector d_u with b^Td_u > 0 and A^Td_u = 0. What does this imply about (QD) and about (QP)?
3. (10 points) Assume there exists a vector d satisfying c^Td < 0, d^TQd = 0, and Ad ≥ 0. What does this imply about (QD)? Assume further that there exists an satisfying A > b. What does your result about (QD) then imply about (QP)?
(20 points; each part is worth 10 points.) The function f : IRⁿ → IR is convex and the function ϕ : IR → IR is convex and monotonically strictly increasing. Define g(x) := ϕ(f(x)), so g : IRⁿ → IR. The problems of minimizing f(x) and of minimizing g(x) are equivalent, with the same optimal points. Assume f, g, and ϕ are all smooth functions.
1. How do the steepest descent directions for f(x) and g(x) compare?
2. How do the Newton directions for f(x) and g(x) compare? (Hint: If M is an invertible n × n matrix and a is an n-vector, then $(M + aaT)-1 = M - 1 - -----1------M - 1aaT M -1 1 + aTM - 1a$
  provided 1 + a^TM^-1a≠0.)