Homework 7

Due in class, 12 April, 2012

Do Exercises 1 and 3 from Chapter 5 of the Convex Optimization book:

5.1 Consider the optimization problem

minimize x2 + 1
subject to (x-2)(x-4) ≤ 0

with x ε R.

  1. Give the feasible set, the optimal value, and the optimal solution.
  2. Plot the objective x2 + 1 versus x. On the same plot, show the feasible set, optimal point and value, and plot the Lagrangian L(x, λ) versus x for a few positive values of &lambda. Verify the lower bound property infx L(x, λ) ≤ p* for λ ≥ 0. Derive and sketch the Lagrange dual function g.
  3. State the dual problem and verify that it is a concave maximization problem. Find the dual optimal value and dual optimal solution λ*. Does strong duality hold?
  4. Let p*(u) denote the optimal value of the problem

    minimize x2 + 1
    subject to (x-2)(x-4) ≤ u

    as a function of the parameter u. Plot p*(u) and verify that its derivative at 0 is -λ*.

5.3 Express the dual problem of

minimize cTx
subject to f(x) ≤ 0

with c ≠ 0, in terms of the Fenchel conjugate f*. Explain why the dual problem is convex even if f isn't convex.