MATP6600/DSES6780 Nonlinear Programming, Homework 1.

Due: Friday, September 11, 2009.

  1. Let S be a convex set in IRn and let A be an m × n matrix. Show that the set AS := {y ∈ IRm : y = Ax for some x ∈ S} is convex. (Hint: Consider two points y1 and y2 in AS. Let z be a convex combination of y1 and y2. Show that z is also in AS.)
  2. Let S consist of the following five points in IR2:
    ( ) ( ) ( ) ( ) ( ) 1 2 2 3 3 5 4 2 5 - 1 x = 0 ,x = 1 ,x = 0 ,x = - 2 ,x = 1 .

    1. Express x1 as a convex combination of three of the other points.
    2. Give an inequality description of conv(S). That is, find A and b so that conv(S) = {x ∈ IR2 : Ax ≤ b}.
  3. Let S be a closed set. Give an example to show that the convex hull of S, conv(S), need not be closed. (Hint: you will need to use an unbounded set S.)
  4. Let S1 and S2 be nonempty subsets in IRn. Show that conv(S 1 ∩S2) ⊆ conv(S1) ∩ conv(S2). Give an example where conv(S1 ∩ S2)≠conv(S1) ∩ conv(S2). (Hint: If x is in conv(S1 ∩ S2) then it can be represented as a convex combination of points which are in both S1 and S2.)
  5. Let ai, i = 1,…,m be vectors in IRn and let b i, i = 1,…,m be scalars. Define the function
    { |z| - a if |z| > a f(z) := 0 if |z| ≤ a

    for scalars z. Show that the nonlinear program

    ∑m T min n f (bi - ai x) x∈IR i=1

    is equivalent to a linear programming problem.

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