Some Math Facts on Linear Algebra and Optimization

Posted on Edited on

1. Norm

Definition: For vector $x\in\mathbb{R}^n$, $p\in(0,\infty]$

\begin{gather*}
||x||_p=\left(
x_1^p+\cdots+x_n^p
\right)^{\frac{1}{p}}.
\end{gather*}

When $p\in[1,\infty]$, $||x||_p$ is a norm.

Theorem: .
Proof of the Theorem Consider the auxiliary vectors . Note that each entry of $y$ is less than 1:

The following inequality holds for each entry:

࢘

2. Cone

Definition: A set $\mathcal{K}$ is called cone if for all $x\in \mathcal{K},\theta\geq 0$, it holds that
\begin{gather*}
\theta x\in \mathcal{K}
\end{gather*}

Definition: Let $\mathcal{K}$ be a cone, the dual cone $\mathcal{K}^*$ is
\begin{gather*}
\mathcal{K}^*:= \left\{y\mid \langle x,y\rangle \geq 0, \forall x\in\mathcal{K}\right\}
\end{gather*}

Definition: Let $\mathcal{K}$ be a cone, the polar cone $\mathcal{K}^o$ is
\begin{gather*}
\mathcal{K}^o:= \left\{y\mid \langle x,y\rangle \leq 0, \forall x\in\mathcal{K}\right\}
\end{gather*}

Apparently, by the definition, $\mathcal{K}^o=-\mathcal{K}^*$.

Definition: Let $C$ be a set, for any $x\in C$ the normal cone $\mathcal{N}_C(x)$ at this point is:
\begin{gather*}
\mathcal{N}_C(x):= \left\{y\mid \langle y,c-x\rangle\leq 0, \forall c\in\mathcal{K}\right\}
\end{gather*}

Lemma: If $\mathcal{K}$ is convex and closed, then $\mathcal{K}^{**}=\mathcal{K}$.
Proof Just use the definition, it is easy to verify that $\mathcal{K}\subseteq \mathcal{K}^{**}$. To show that they are actually the same set. Suppose there exists $x\in\mathcal{K}^{**},x\notin \mathcal{K}$. By Hyperplane separation theorem, there exists $c$ such that \begin{gather*} \mathcal{K}\subseteq H^+=\left\{z\mid c^Tz\geq 0\right\},\\ c^Tx < 0. \end{gather*} From the first relation, it holds that $c\in \mathcal{K}^*$. However, the second relation indicates that such $x\notin \mathcal{K}^{**}$ which contradicts the assumption. Therefore $\mathcal{K}^{**}=\mathcal{K}$.
Lemma: The normal cone for a cone $\mathcal{K}$ is: \begin{gather*} \mathcal{N}_{\mathcal{K}} (x)=\left\{ \begin{array}{lc} \left\{y\mid\langle y,x \rangle=0\right\}&x\in \mathcal{K}\\ \phi&x\notin \mathcal{K} \end{array} \right. \end{gather*}
Proof We only need to show that there does not exists such $y\in\mathcal{N}_{\mathcal{K}}$ that $\langle y,x\rangle < 0$. Suppose there exists, then for $x\in \mathcal{K}$, $$ \langle y, \frac{1}{2}x - x\rangle=\langle y, -\frac{1}{2}x \rangle > 0 $$ which contradicts the definition of the normal cone, as $\frac{1}{2}x\in \mathcal{K}$.

3. Positive Definite Matrix

Lemma: Given $A\succeq 0,B\succeq 0$, $AB=0$ iff. $tr(AB)=0$.
Proof of the Lemma $\Rightarrow$: This is trivial by imposing the trace operation to $AB$.
$\Leftarrow$: Let $A=PP^T,B=QQ^T$, where $P,Q$ can be chosen such as Cholesky decomposition or square root of the corresponding matrice. It holds that \begin{gather*} tr(AB)=tr(PP^TQQ^T)=tr(Q^TPP^TQ)=tr(P^TQ)^2=\|P^TQ\|_F^2=0\\ \Rightarrow AB=PP^TQQ^T=P 0 Q^T=0. \end{gather*}

3.1. Linear Matrix Inequality(LMI) and SemiDefinite Programming(SDP)