I am not sure if this helps, but it will be good if your $C$ have some nice properties. Define the matrix $X=[x_1,x_2,...,x_n]$ with the vectors under question as columns. Then you can rewrite your problem as
\begin{align}
\min_{X}~trace(CX^{T}MX)
\end{align}
Define $M=F^{T}F$ ($M$ being a psd matrix, you will be able to find such a $F$). Define $Y=FX$. You get the above problem as
\begin{align}
\min_{Y}~trace(CY^{T}Y)
\end{align}
Now $trace(CY^{T}Y)=trace(YCY^{T})$, (circularity of trace). At this point, to progress any further, we need to have some properties on $C$. For instance, if $C$ is symmetric, you can decompose as you did with $M$ and come up with a even simpler condition.
EDIT---
Starting from the last point, define $Z=Y^{T}Y$. Then you can rewrite the problem as
\begin{align}
\min_{Z}~trace(CZ) \\
subject ~to~Z\geq0
\end{align}
where $Z\geq 0$ means it should be psd. This is a convex optimization problem with a linear objective and a semi-definite constraint. It is referred to as semi-definite programming. If you do not have any nice properties on $C$, I think this is what you can do.