MATP6600/DSES6780 Nonlinear Programming, Homework 4.

Due: Friday, October 23, 2009, in class.

  1. In Homework 3, you determined that the global optimizer of the problem

    min -x1x2x3, subject to x1 + 2x2 + 4x3 ≤ 48, x1,x2,x3 ≥ 0.

    was x* = (16, 8, 4). Only the first constraint is active at x* and it has a KKT multiplier u = 32. Verify the KKT second-order necessary optimality conditions for this solution. Does the KKT second-order sufficient condition hold at x*?

  2. Consider the optimization problem
    2 2 min f (x ) := - x1 + (x2 - x1) subject to x1 ≥ 0, x2 ≥ 0

    1. Show that the optimal value of this problem is unbounded.
    2. Given a feasible point ¯x and feasible direction d, let ϕx¯,d(α) = f(x¯ + αd). Show that ϕ¯x,d(α) has a finite minimal value over α ≥ 0 for any feasible ¯x and d.
  3. Construct the Lagrangian dual problem to the problem in question 2, dualizing both constraints. Verify that the dual problem is infeasible.
  4. Use AMPL to solve the quadratically constrained nonlinear program
    min cTx subject to 1xTM x ≤ m (N LP ) 21 T 2x Qx ≤ q,

    with

    [ 0 ] [ 13 4 ] [ 3 - 1 ] c = , M = , Q = , m = 14, q = 6. 1 4 7 - 1 3

    (Perhaps the easiest way to solve an NLP in AMPL is to use the NEOS server at http://www-neos.mcs.anl.gov/neos/ which has a selection of solvers available. CPLEX can also solve problems in this form, but it doesn’t give dual variables for this problem because of the way its interior point method is implemented.)

  5. Find the KKT multipliers for problem (NLP) in Question 4 using the AMPL command display. Check the first order necessary conditions. Find the value of the Lagrangian and compare it with the objective function value. (Note: You can display expressions such as c + Mx.)
    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Tuesday 2.0 – 3.0, Wednesday 11.0 – 12.0.