Dual of a positive semidefinite cone

Question

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?

Answer 1

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 $$