The PSD cone is the set of all positive semidefinite matrices. The dual is the set of all matrices $A$ such that tr($A^T X$) $\geq 0$ for all positive semidefinite matrices $X$.
How to prove that the PSD cone is self-dual,i.e. the dual is also the set of all positive semidefinite matrices?
$\endgroup$1 Answer
$\begingroup$First note that a symmetric matrix $X\in \mathbb S^n$ is PSD if and only if it is a sum of outer products $X = \sum_{i=1}^n x_i x_i^T$ (proof via cholesky). By definition (using the fact that $\operatorname{tr}(A^TX)=\langle A, X\rangle$ is the natural inner product (Frobenius) on $\mathbb S^n$):
- $\operatorname{PSD}=\{X\in\mathbb S^n\mid \langle X, uu^T\rangle\ge 0\forall u\in\mathbb R^n \} $
- $\operatorname{PSD}'=\{A\in\mathbb S^n\mid \langle A, Z\rangle\ge 0\forall Z\in\operatorname{PSD} \} $
Then
- Let $X, Z\in\operatorname{PSD}$ be arbitray. Since $X=\sum_i x_ix_i^T$, we have $\langle Z, X\rangle= \sum_i \langle Z, x_ix_i^T \rangle \ge 0$, hence $X\in\operatorname{PSD}'$
- Let $A\in\operatorname{PSD}'$. Then $\langle A, X\rangle\ge 0$ for all $X\in\operatorname{PSD}$, so in particular any $X=xx^T$. Hence $A\in\operatorname{PSD}$
So in essence it boils down to the equivalence
$$ \langle X, uu^T\rangle\ge 0\forall u\in\mathbb R^n\iff \sum_{i=1}^N\langle X, u_iu^T_i\rangle\ge 0\forall u_i\in\mathbb R^n $$
$\endgroup$ 2
