Minimize Frobenius norm

Here's one approach to solve this problem.

Since $U$ is a thin matrix with orthogonal columns each of which has unit norm it spans a $d$ dimensional subspace within the $n$ dimensional ambient subspace. Now we can see that the constraint that $U^TXU \succeq 0$ is a looser constraint than $X \succeq 0$ since $X$ only needs to be positive definite for vectors $v \in \mathbb{R}^n$ lying in the span of columns of $U$. Clearly, the solution to this problem is guaranteed to be a better minima than the solution obtained by setting negative eigen values to zero.

Essentially we are saying that eigen-values corresponding to those eigen-vectors of $X$ that are orthogonal to $U$ can be anything. And Eigen-values for those eigen-vectors of$X$ that lie in the span of $U$ must be positive.

So immediately we get the following procedure for solving this problem.

1. Do Eigen decomposition of $M$ to get $n$ eigen-vectors $q_i$
2. If $U^Tq_i \ne 0$ then modify the corresponding eigen-value $\lambda_i$ to $\max(0, \lambda_i)$, Otherwise the sign does not matter, we can leave as is.

This is guaranteed to be a feasible solution, and its guaranteed to be better than the vanilla algorithm outlined in the question.

Although this procedure is an improvement its not guaranteed to be minima of the original problem. To get a true minima some more thought is needed. I will update when I get a chance to think more about this.