Convex envelop of Tr(XY)? How would one go about calculating the convex envelop of $f(X,Y) = Tr(XY)$, where both $X \in R^{ n \times n}$ and $Y \in R^{ n \times n}$ define the domain of $f$ and are both symmetric PSD? I am trying to calculate a global under-estimator of $f$.

It's well known that $\mbox{tr}(XY) \geq 0$ for all PSD pairs $(X,Y)$.  Unfortunately, you can't do any better than that in finding the convex envelope.  Let $g(X,Y)$ be the convex envelope of $f(X,Y)$.  I claim that $g(X,Y)=0$.
Take any pair $(X,Y)$ in the domain of $f$.  The pairs $(2X,0)$ and $(0,2Y)$ are also in the domain of $f$.  
$f(2X,0)=0$
$f(0,2Y)=0$
$f(X,Y)=f((2X,0)/2+(0,2Y)/2)$
Thus $g(X,Y) \leq 0$. 
