数学代写|ENGG5501 Convex Optimization

(30pts).
(a) (10pts). Let $P \in \mathbb{R}^{n \times n}$ be an orthogonal projection matrix (i.e., $P^2=P$ and $P=P^T$; see Handout B, Section 1.6). Show that $|P| \leq 1$, where $|P|$ is the largest singular value of $P$.
(b) (10pts). Give an example of a projection matrix $P \in \mathbb{R}^{2 \times 2}$ with $|P|>1$. Justify your answer.
(c) (10pts). Let $\Delta=\left{x \in \mathbb{R}^n: e^T x=1, x \geq \mathbf{0}\right}$ be the standard simplex, where $e=(1,1, \ldots, 1)$ is the vector of all ones. Show that for any $v \in \mathbb{R}^n$ and $\delta \in \mathbb{R}$, we have
$$
\Pi_{\Delta}(v)=\Pi_{\Delta}(v+\delta e)
$$

(20pts). Recall that every closed convex set $S$ is the intersection of all the halfspaces containing $S$. The goal of this problem is to verify this result for $\mathcal{S}{+}^n$, the set of $n \times n$ symmetric positive semidefinite matrices. Given any $A, B \in \mathcal{S}^n$, we define $A \bullet B=\operatorname{tr}(A B)$ to be the inner product between $A$ and $B$. (a) (10pts). Show that for any $A, B \in \mathcal{S}{+}^n$, we have $A \bullet B \geq 0$.
(b) (10pts). The result in (a) implies that $\mathcal{S}{+}^n \subseteq\left{X \in \mathcal{S}^n: A \bullet X \geq 0\right}$ for any $A \in \mathcal{S}{+}^n$. Show that in fact
$$
\mathcal{S}{+}^n=\bigcap{A \in \mathcal{S}_{+}^n}\left{X \in \mathcal{S}^n: A \bullet X \geq 0\right}
$$

(30pts). Let $K \subseteq \mathbb{R}^n$ be a closed convex cone. Define
$$
K^{\circ}=\left{w \in \mathbb{R}^n: w^T x \leq 0 \text { for all } x \in K\right}
$$
to be the polar cone of $K$.
(a) (10pts). Show that $K^{\circ}$ is a convex cone.
(b) (10pts). Show that for any $x \in \mathbb{R}^n$, we have $z^=\Pi_K(x)$ if and only if $$ z^ \in K, \quad x-z^* \in K^{\circ}, \quad\left(x-z^\right)^T z^=0 .
$$
(c) (10pts). Using the result in (a), or otherwise, show that for any $x \in \mathbb{R}^n$, we have
$$
x=\Pi_K(x)+\Pi_{K^{\circ}}(x) .
$$
Remark: The above identity shows that a closed convex cone $K$ can be used to decompose any vector $x$ into the orthogonal components $\Pi_K(x)$ and $\Pi_{K^{\circ}}(x)$.

(30pts). Let $A \in \mathbb{R}^{m \times n}$ be given. Show that exactly one system in each of the following pairs has a solution.
(a) (15pts).
(I) $A x<0, x \geq 0$. (II) $A^T y \geq \mathbf{0}, y \geq \mathbf{0}, y \neq \mathbf{0}$. (b) (15pts). (I) $A x \geq 0, A x \neq 0$. (II) $A^T y=\mathbf{0}, y>\mathbf{0}$.