Let $\tilde{\rho}$ and $\rho$ be symmetric positive semidefinite matrices with $\text{tr}(\tilde{\rho})\leq \text{tr}(\rho)\leq 1$.
We diagonalize $\tilde{\rho}-\rho = Z\Lambda Z^\dagger = Z\Lambda^{+}Z^\dagger + Z\Lambda^{-}Z^\dagger$ where $\Lambda$ is diagonal, $\Lambda^{+}$ is diagonal and has all the nonnegative eigenvalues of $\Lambda$ while $\Lambda^-$ is has all negative eigenvalues of $\Lambda$. Define $\rho':= \rho + Z\Lambda^{-}Z^\dagger$.
Claim: $\rho' \geq 0$ i.e. it is positive semidefinite.
Suppose $\rho'\not\geq 0$. Then, it also holds that $Z^\dagger \rho Z\not\geq 0$ since $Z$ is a unitary matrix. There exists some nonzero $x\in \mathbb{C}^{n}$ such that $x^\dagger Z^\dagger \rho'Z x < 0$. Since $Z^\dagger \rho'Z = Z^\dagger \rho Z + \Lambda^-$ and $Z^\dagger\rho Z\geq 0$, we can choose $x\in\text{supp}(\Lambda^-)$ without loss of generality. Since $\text{supp}(\Lambda^+)\cap \text{supp}(\Lambda^-) = \emptyset$, it holds that $x^\dagger\Lambda^+ x = 0$. It follows that $x^\dagger Z^\dagger \tilde{\rho}Z x = x^\dagger Z^\dagger \rho'Z x + x^\dagger\Lambda^+x < 0$ but this contradicts the assumption that $\tilde{\rho}\geq 0$. We conclude that $\rho' \geq 0$.
Unfortunately, this claim is not true since I tried some numerical examples that showed otherwise. What is the mistake in the proof?
EDIT:
Adding a simple example to clarify the support and kernel problem pointed out in the comments. Suppose $Z^\dagger\rho Z$ is a $2\times 2$ positive semidefinite matrix and we have
$$Z^\dagger\rho Z = \begin{bmatrix}1 & -1 \\ -1& 1\end{bmatrix}, \Lambda^- = \begin{bmatrix}0 & 0 \\ 0& -1\end{bmatrix}$$
Let $x = (a, b)$ such that $x^\dagger Z^\dagger\rho' Z x < 0$. I thought I could choose $x = (0, 1)$ without loss of generality but this yields $x^\dagger Z^\dagger \rho' Z x = 0$. On the other hand $x = (1,1)$ yields $x^\dagger Z^\dagger \rho' Z x = -1$. Clearly $(1,1)$ is not contained in the support of $\Lambda^-$.