Optimization, Written Assignment #1


April 3, 2008
All numbered exercises are from Boyd and Vandenberghe.
  1. Problem [2.4]
  2. Problem [2.8]
  3. Which of the following sets are convex? For sets that are not convex, give a counterexample to convexity.
    1. The sets described in [2.12 (a)-(e)].
    2. {x ∈ ℝn|∑n x2 ≤ 1, xi ≥ 0} i=1 i.
    3. { n ∑n 2 } x ∈ ℝ | i=1xi = 1, xi ≥ 0.
    4. ∑ {x ∈ ℝn| ni=1xi ≤ 1, xi ≥ 0}.
    5. {x ∈ ℝn|∑n xi = 1, xi ≥ 0} i=1.
    6. The set Sn of symmetric matrices in ℝn×n.
    7. The set of matrices of rank at most 1 in ℝn×m.
    8. The set of symmetric matrices with minimum eigenvalue at most 1.
    9. Optional: [2.12 (f)-(g)]
    10. Optional (but highly recommended at least to statistics and machine learning students): [2.15]
  4. Problem [2.25] (Do draw the requested illustration, but there is no need to turn it in).
  5. Show that if f1,…,fk are convex functions, then f(x) = maxifi(x) is also convex. Note that this holds also for supremum over an infinite set of functions.
  6. We saw in class that every monotone increasing function on the reals f : ℝ → ℝ is quasiconvex (and in fact, quasi-linear). Give an example of a monotone increasing function that is not convex.
  7. Problem [3.7]
  8. Problem [3.16]
  9. Optional (but highly recommended at least to statistics and machine learning students): [3.24]
  10.  
    1. Problem [3.26 (a) and (b)]. Sn is the set of symmetric matrices in ℝn×n. S++n is the set of symmetric positive definite matrices in ℝn×n.
    2. Show that the function from [3.26 (b)] is not concave over Sn.