MATP6600/DSES6780 Nonlinear Programming, Homework 2.

Due: Friday, September 25, 2009, in class.

  1. Let f(x) := cT x + 1 2xT Qx for all x ∈ IRn. Show directly that the epigraph of f(x) is convex if and only if Q is positive semidefinite. (By “show directly”, I mean show that the line segment between any two points in the epigraph is contained in the epigraph.)
  2. Let
    S := {x ∈ IR3 : 4x1 + 5x2 + 7x3 ≤ 13,xi = 0 or 1,i = 1,...,3}.

    Show that the point x¯ = (0.7, 0.7, 0.7)T is not in the convex hull of S, by finding a hyperplane which separates the point from the set.

  3. Let ai, i = 1,…,m be vectors in IRn and let b i, i = 1,…,m be scalars. Let α be a positive scalar. Define the function f : IR → IR as
    { f(z) := |z| - α if |z| > α 0 if |z| ≤ α

    Show that the function g(x) := ∑ i=1mf(b i - aiT x) is convex.

  4. Consider the problem min{f(x) := x2 - ln(x + 2) : x ≥ 0}.
    1. Show that f(x) is a strictly convex function for x ≥ 0.
    2. We want to get a lower bound on the optimal value of this problem. Use the subgradient inequality
      f(x) ≥ f(¯x) + ∇f (¯x)T (x - ¯x)

      to find an interval [a,a + 0.1] that contains the optimal solution. What lower bound do you get on the optimal value from your interval?

  5. Let f : IRn → IR be a convex function and let g : IR → IR be a convex nondecreasing function. Define the function h : IRn → IR by h(x) := g(f(x)). Prove that h(x) is a convex function. Hence show that ex2-4xy+5y2 is a convex function on IR2.
  6. Let the cone K ⊆ IRn be defined as
    n n∑-1 2 2 K := {x ∈ IR : x i ≤ xn, xn ≥ 0}. i=1

    Show that K is convex and find the polar cone K0 to K.

    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Tuesday 2.0 – 3.0, Wednesday 11.0 – 12.0.