Homework 6

Convexity

The first six exercises are from Beck, Introduction to Nonlinear Optimization.

  1. (Convexity of set operations) Exercise 6.1

  2. (Convex hull) Exercise 6.4

  3. (Normal cone) Exercise 6.10 (You only need to show that the normal cone is a convex cone, not that it’s closed.)

  4. (Convex functions) Exercise 7.1 (i–ii)

  5. (Affine functions) Exercise 7.3

  6. (Strict convexity) Exercise 7.7

  7. (Entropy) Show that the function \[ f(x) = -\sum_{i=1}^n x_i\log x_i \] is concave over the probability simplex \(\bar\Delta_n=\{ x\in \R^n_+\mid \sum_{i=1}^n x_i = 1 \}\).

  8. (Log-Sum-Exp) Show that the function \[ f(x) = \log\left(\sum_{i=1}^m e^{a_i^T x}\right) \] is convex in \(\R^n\), where \(a_1,\ldots,a_m\in\R^n\).