ELM 670 Introduction to Convex Optimization HOMEWORK -1

ELM 670 Introduction to Convex Optimization
HOMEWORK -1
Due date: 14th of October, 2014
Note: You can choose and solve only the any four questions among the first six
questions. The question 7 must be solved in any case. (,i.e., you are supposed to deliver
the answers of only five chosen questions including the seventh question.)
1. Let C  n be a convex set, with x1 ,...xk  C , and let 1 ,....,k  satisfy
i  0 , 1  ....  k  1. Show that 1 x1  ...  k xk  C . (The definition of
convexity is that this holds for k = 2; you must show it for arbitrary k.) Hint. Use
induction on k.
2. Show that a set is convex if and only if its intersection with any line is convex.
3. Show that the convex hull of a set S is the intersection of all convex sets that
contain S.
4. Voronoi description of halfspace. Let a and b be distinct points in n . Show
that the set of all points that are closer (in Euclidean norm) to a than b, i.e.,
{x x  a 2  x  b 2 } , is a halfspace. Describe it explicitly as an inequality of
the form cT x  d .
5. Solution set of a quadratic inequality. Let C  n be the solution set of a
quadratic
inequality,
with
C  {x  n xT Ax  bT x  c  0}
A  S n , b  n , c  . Show that C is convex if A 0 .
6. Which of the following sets are convex?
a. A slab, i.e., a set of the form {x  n   aT x   } .
b. The set of points closer to a given point than a given set, i.e.,
{x x  x0 2  x  y 2 for all y  S} where S  n .
7. Show that if S1 and S2 are convex sets in mn , then so is their partial sum
S  {( x, y1  y2 ) x  m , y1 , y2  n ,( x, y1 )  S1,( x, y2 )  S2} .

Download Report