Problem 1 [55 points] Convex sets

(a) [5 x 5 = 25 points] Prove or disprove set convexity

For each of the following, state clearly if the set is convex or not. Then prove your statement.

(i) Rectangle: (vector inequality is to be understood elementwise)

$$\{x\in\mathbb{R}^{n} \mid \alpha \leq x \leq \beta, \quad \alpha,\beta\in\mathbb{R}^{n}\}.$$

(ii) Wedge:

$$\{x\in\mathbb{R}^{n} \mid a_{1}^{\top}x \leq b_{1}, \quad a_{2}^{\top}x \leq b_{2}, \quad a_{1},a_{2}\in\mathbb{R}^{n}, \quad b_{1},b_{2}\in\mathbb{R}\}.$$

(iii) Set of points closer to a given point than a given set:

$$\{x\in\mathbb{R}^{n} \mid \| x - x_{0}\|_{2} \:\leq\: \| x - y\|_{2}, \quad \forall\: y\in\mathcal{S}\subseteq\mathbb{R}^{n}, \quad x_{0}\in\mathbb{R}^{n}\}.$$

(iv) Set of points closer to one set than another:

$$\{x\in\mathbb{R}^{n} \mid \text{dist}\left(x,\mathcal{A}\right)\leq \text{dist}\left(x,\mathcal{B}\right), \quad \mathcal{A},\mathcal{B}\subset\mathbb{R}^{n}\}, \quad \text{dist}\left(x,\mathcal{A}\right):= \underset{a\in\mathcal{A}}{\inf}\|x-a\|_{2}.$$

(v) The set: $$\{c\in\mathbb{R}^{n+1} \mid c_{0} + c_{n} = 1, \big|c_{0} + c_{1}x + c_{2}x^{2} + ... + c_{n}x^{n}\big| \leq 1 \;\text{for}\; 2020\leq x\leq 2021\}.$$

(b) [10 + 10 + 10 = 30 points] Support function

The support function of a compact convex set $\mathcal{X}\subset\mathbb{R}^{n}$ is defined as

$$h(y) := \sup_{x\in\mathcal{X}}\:\{x^{\top}y \:\mid y\in\mathbb{R}^{n}\},$$

which can be geometrically interpreted as the perpendicular distance from the origin to the supporting hyperplane of $\mathcal{X}$. Therefore, the support function uniquely determines a convex set.

(i) Suppose two compact convex sets $\mathcal{X}_{1},\mathcal{X}_{2}\subset\mathbb{R}^{n}$ have support functions $h_1(\cdot)$ and $h_2(\cdot)$, respectively. Derive the support function $h(\cdot)$ for the set sum/Minkowski sum $\mathcal{X}_{1}+\mathcal{X}_{2}$ (which is a convex set, see Lec. 6, p. 4). In other words, express $h(\cdot)$ in terms of $h_{1}(\cdot)$ and $h_2(\cdot)$.

(ii) Prove that $h(y+z) \leq h(y) + h(z)$ for any compact convex set $\mathcal{X}\subset\mathbb{R}^{n}$, and any $y,z\in\mathbb{R}^{n}$.

(iii) Derive the support function $h(y)$ for the Euclidean ball $\mathcal{B}(0,r)\subset\mathbb{R}^{n}$ (see Lec. 5, p. 12) with center at origin and radius $r>0$. (Hint: Cauchy-Schwarz inequality)

Problem 2 [3 x 15 = 45 points] Convex functions

For each of the following, state clearly if the function is convex or concave or both or neither. Then prove your statement.

(i) $f(x,t) = \log\left(\dfrac{1}{t^{2} - x^{\top}x}\right)$ over ${\rm{\mathbf{dom}}}(f) = \{(x,t) \in \mathbb{R}^{n} \times \mathbb{R} \:\mid\: \parallel x\parallel_{2} \:<\: t\}$.

(ii) $f(p,q) = \displaystyle\sum_{i=1}^{n} p_{i}\log\left(\displaystyle\frac{p_{i}}{q_{i}}\right)$ over ${\rm{\mathbf{dom}}}(f) = \{(p,q)\in\mathbb{R}_{\geq 0}^{n}\times\mathbb{R}_{\geq 0}^{n} \:\mid\: \mathbf{1}^{\top}p = \mathbf{1}^{\top}q = 1\}$.

(iii) $f(x) = \dfrac{1}{x}\displaystyle\int_{0}^{x}\!g(t)\:{\mathrm{d}}t$ over ${\rm{\mathbf{dom}}}(f) = \mathbb{R}_{>0}$, where $g:\mathbb{R}\mapsto\mathbb{R}$ is convex and differentiable.