Monotonicity property for a simple semidefinite program (SDP) Let $A \in S^{n}_{+}$ be a positive semi-definite matrix. Consider the following simple semi-definite program (SDP)
$$\begin{array}{ll} f(A) = &\underset{T \text{ is diagonal}}{\text{minimize}} \;\; \mbox{Tr}(T)\\ &\text{subject to} \;\; A \preceq T\end{array}$$
The dual problem is
$$\begin{array}{ll} \underset{X \in S^{n}_{+}}{\text{maximize}} & \mbox{Tr} (A X)\\ \text{subject to} & X_{ii} = 1, \quad \forall\, i \leq n\end{array}$$
Suppose $A_1$ and $A_2$ are two positive semi-definite matrices, and the eigenvalues of $A_1$ are pairwisely larger than the eigenvalues of $A_2$. In another word, let $\lambda_i(A)$ denote the $i$-th largest eigenvalue of a symmetric matrix $A$; then we have $\lambda_i(A_1) \geq \lambda_i(A_2) \geq 0$ for all $i \leq n$.
I wonder if the above implies $f(A_1) \geq f(A_2)$? This monotonicity property seems intuitive to me, and I wonder if there is a way to formally prove or disprove this. The difficulty I met is that the fact that $A_1$ has larger eigenvalues does not mean the difference $A_1 - A_2$ is positive semi-definite, so this monotonicity property is not immediately obvious.
(A related question is asked here, which is on whether the above problems have analytical solutions).
 A: I think in general we do not have the implication $f(A_1)\ge f(A_2)$. The issue is what you alluded to, namely $A_1$ and $A_2$ may not be simultaneously diagonalizable, i.e. there may not be an orthogonal matrix $V$ such that
$$A_k = V\Sigma_k V^\top, \;\; \text{for $k=1,2,$}\quad (1)$$
where $\Sigma_k$ is a diagonal matrix  with eigenvalues of $A_k$ on the diagonal.
First, if there does exist such a $V$ that $(1)$ holds. Then, since $\text{Tr}(AX)=\text{Tr}(V\Sigma V^\top X)=\text{Tr}(\Sigma (V^\top X V))$, we can rewrite the dual problem as
$$\begin{align*} f(A_k) = \max_{X\succeq 0} \quad & \text{Tr}(\Sigma_k (V^\top X V))\\ \text{s.t.} \quad & X_{ii}=1, \;\;\forall i\\
= \max_{Y\succeq 0} \quad & \text{Tr}(\Sigma_k Y)\\ \text{s.t.}\quad & (VYV^\top)_{ii}=1, \;\;\forall i\end{align*}$$
From this we can see that if $\Sigma_1 \succeq \Sigma_2$, then $\text{Tr}(\Sigma_1 Y)\ge \text{Tr}(\Sigma_2 Y)$ for all $Y\succeq 0$. Therefore, $f(A_1)\ge f(A_2)$.
Second, if (1) does not hold, then we can look at the simple case where $\Sigma_1 = \Sigma_2 = \Sigma$, but $A_1 = V_1V_1^\top$ and $A_2=V_2V_2^\top$ as their eigendecomposition and $V_1\ne V_2$. Then,
$$\begin{align*} f(A_k) = \max_{Y\succeq 0} \quad & \text{Tr}(\Sigma Y)\\ \text{s.t.}\quad & (V_kYV^\top_k)_{ii}=1, \;\;\forall i\end{align*}$$
But you see that since these two problems now have the same objective function and different linear equality constraints, there is no reason $f(A_1)$ would be equal to $f(A_2)$.
In particular, think about the 2-by-2 case, let $\Sigma=\begin{bmatrix}1 & 0 \\ 0 & 0 \end{bmatrix}$, and $V_1 = I$ and $V_2 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & -1 \\ 1 & 1\end{bmatrix}$, then it can be directly computed that $f(A_1) = 1$ but $f(A_2)=2$. If the computation is correct, then this example indicates that even when $A_1$ and $A_2$ share the same set of eigenvalues, $f(A_1)-f(A_2)$ can be either positive, negative, or zero.
