Problem 1 [20 points] A set of matrices

Consider the following set of matrices:

$$\mathcal{X} := \bigg\{X\in\mathbb{R}^{n\times n} \mid X_{ij}\geq 0, \quad \displaystyle\sum_{i=1}^{n}X_{ij} = \displaystyle\sum_{j=1}^{n}X_{ij} = 1, \quad \text{for all}\quad i,j=1, ...,n\bigg\}.$$

(a) [10 points] Convexity

Prove that $\mathcal{X}$ is a convex set.

(b) [(1+4) + (1+4) = 10 points] What kind of convex set

(i) Is $\mathcal{X}$ a cone? Why/why not?

(ii) Is $\mathcal{X}$ a polyhedron? Why/why not?

Problem 2 [50 points] Hulls

(a) [1+4 = 5 points] Affine hull

What is ${\rm{aff}}\left(\mathbb{S}^{n}_{+}\right)$, the affine hull of the set of $n\times n$ positive semidefinite matrices? Give reasons to support your answer.

(b) [10 + 10 + 10 = 30 points] Properties of convex hull

Consider nonempty sets $\mathcal{A},\mathcal{B},\mathcal{X},\mathcal{Y} \subseteq \mathbb{R}^{n}$.

(i) Prove that if $\mathcal{X}\subseteq \mathcal{Y}$, then ${\rm{conv}}\left(\mathcal{X}\right) \subseteq {\rm{conv}}\left(\mathcal{Y}\right)$.

(ii) Use (i) to prove that ${\rm{conv}}\left(\mathcal{A}\cap\mathcal{B}\right) \subseteq {\rm{conv}}\left(\mathcal{A}\right) \cap {\rm{conv}}\left(\mathcal{B}\right)$.

(iii) Use (i) to prove that ${\rm{conv}}\left(\mathcal{A}\cup\mathcal{B}\right) = {\rm{conv}}\left({\rm{conv}}\left(\mathcal{A}\right) \cup {\rm{conv}}\left(\mathcal{B}\right)\right)$.

(c) [12 + (1+2) = 15 points] Convex hull of roots

Consider a nonconstant univariate polynomial $p\in\mathbb{R}[x]$ (this notation means that the polynomial $p$ is in variable $x$, and it has real coefficients).

Suppose $\mathcal{R}=\{r_1,r_2,...\}$ is the set of all roots of the polynomial $p$. In general, some roots are real, and some complex conjugates.

(i) Prove that all critical points (roots of the derivative) of $p$ must lie in ${\rm{conv}}(\mathcal{R})$, the convex hull of $\mathcal{R}$.

(To help you visualize the statement above, in the following figure, we plotted the roots (blue dots) of a randomly generated 10th degree polynomial, and its critical points (red dots) in the complex plane. In this plot, ${\rm{conv}}(\mathcal{R})$ is the polygon with sides depicted as the blue solid lines.)

(ii) Will the statement in (c)(i) change if $p\in\mathbb{C}[x]$, that is, if the polynomial has complex coefficients? Why/why not?

Problem 3 [30 points] Vector unit norm balls revisited

In this exercise, we take a closer look at the vector unit norm balls encountered in HW1, Prob. 2.

For $i=1,...,n$, we use the symbol $e_{i}$ to denote the $i$th standard basis vector in $\mathbb{R}^{n}$. You can simply think of $e_{i}$ as the $i$th column of the $n\times n$ identity matrix.

(a) [10 points] $p$ norm ball is a convex set for any $p\geq 1$

From the plots in HW1, Prob. 2, we intuitively expect the unit $p$ norm balls to be convex sets for $p\geq 1$, and nonconvex sets for $0\leq p<1.$ This is indeed true.

Use the Minkowski inequality (which can be thought of as the triangle inequality for $p$-norms whenever $p\geq 1$):

$$\|u+v\|_{p} \leq \|u\|_{p} + \|v\|_{p}, \quad \forall u,v\in\mathbb{R}^{n}, \quad p\geq 1,$$

to prove that the vector unit norm balls are convex sets for any $p\geq 1$.

(b) [5 + 5 = 10 points] $1$ norm ball is a polyhedron

Let us establish in two different ways that the $1$ norm ball $\{x\in\mathbb{R}^{n}\mid \|x\|_{1} \leq 1\}$ is a polyhedron.

(i) Write the $1$ norm ball as the intersection of $2n+1$ halfspaces in $\mathbb{R}^{2n}$. Hint: introduce $n$ additional variables.

(From Lec. 5, p. 13-14, this allows us to conclude that the $1$ norm ball is a polyhedron.)

(ii) Write the $1$ norm ball as the convex hull of $2n$ points in $\mathbb{R}^{n}$ in terms of the vectors $e_i$.

(From Lec. 6, p. 1, this allows us to conclude that the $1$ norm ball is a polyhedron.)

(c) [5 + 5 = 10 points] $\infty$ norm ball is a polyhedron

Let us establish in two different ways that the $\infty$ norm ball $\{x\in\mathbb{R}^{n}\mid \|x\|_{\infty} \leq 1\}$ is a polyhedron.

(i) Write the $\infty$ norm ball as the intersection of $2n$ halfspaces in $\mathbb{R}^{n}$ in terms of the vectors $e_{i}$.

(From Lec. 5, p. 13-14, this allows us to conclude that the $\infty$ norm ball is a polyhedron.)

(ii) Write the $\infty$ norm ball as the convex hull of $2^{n}$ points in $\mathbb{R}^{n}$.

(From Lec. 6, p. 1, this allows us to conclude that the $\infty$ norm ball is a polyhedron.)