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\}.$$Prove that $\mathcal{X}$ is a convex set.
(i) Is $\mathcal{X}$ a cone? Why/why not?
(ii) Is $\mathcal{X}$ a polyhedron? Why/why not?
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.
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)$.
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?
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.
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$.
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.)
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.)