Due: Friday, September 9, 2011.

Let S₁ and S₂ be two convex sets in IRⁿ. Show that S₁ + S₂ and S₁ - S₂ are convex.
Let S consist of the following five points in IR²: $( ) ( ) ( ) ( ) ( ) x1 = 2 ,x2 = 3 ,x3 = 5 ,x4 = 2 ,x5 = - 1 . 0 1 0 - 2 1$
1. Express x¹ 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 IR² : Ax ≤ b}.
Let S be a closed set. Give an example to show that the convex hull of S need not be closed. (Hint: you will need to use an unbounded set S.)
Let C₁,…,C_k be convex sets in IRⁿ. Let C = ∪_i=1^kC_i. Let x conv(C). Show that x can be expressed as a convex combination of at most n + 1 points in C, with at most one point in the combination from each C_i. (Hint: You are trying to get a set of points which satisfies two different criteria. It is possible to make the set satisfy one criterion first and then work on it to get it to satisfy the other one.)
Let aⁱ, i = 1,…,m be given vectors in IRⁿ, let b_i, i = 1,…,m be given scalars, and let d be a given scalar. Define the function ${ |z| - d if |z| > d f (z) := max {0, |z| - d} = 0 if |z| ≤ d$
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.

Office hours: Tuesday 12.0 – 2.0, Wednesday 2.0 – 4.0.