I have the following trace minization problem
$$ \min_{X,S\in \mathbb{R}^{n\times n}} \text{Trace}(XS)\\ \text{subject to } \begin{bmatrix}X&I\\I&S\end{bmatrix}\geqslant 0,\\ ~~~~~~~~~~~~~~~~~~~~~~~~X=X^T,S=S^T $$ Here $I$ denotes the identity matrix of $\mathbb{R}^{n\times n}$.
Seems that the minimum value of the problem is $n$, but I cannot prove it. Any help are appreciated!
On
Let $(X,S)$ be a feasible solution,
I am going to start by proving that $S$ is strictly positive, indeed for $u\in mathbb R^n $$u^TXu + 2t \left(u^Tu\right) + t^2u^TSu = \begin{bmatrix} u^T & tu^T \end{bmatrix}\begin{bmatrix}X & I \ I & S\end{bmatrix} \begin{bmatrix}u \ tu\end{bmatrix}\ge 0,\quad \forall t\in \mathbb R $$
So $$ u^TXu u^TSu \ge \left(u^Tu\right)^2 $$
So $S$ is strictly positive.
We can write $S = R^TR$ (since is a definite matrix). For $(x,y) \in \mathbb R^n$
$$x^TXx + 2t \left(x^TR^{-1}y\right) + t^2y^Ty = \begin{bmatrix} x^T & ty^T\left(R^T\right)^{-1} \end{bmatrix}\begin{bmatrix}X & I \\ I & S\end{bmatrix} \begin{bmatrix}x \\ tR^{-1}y\end{bmatrix}\ge 0,\quad \forall t\in \mathbb R $$
So by taking $t = - \frac{x^TR^{-1}y}{y^Ty}$, $$\left(x^TXx\right)\left(y^Ty\right) - \left(x^TR^{-1}y\right)^2\ge 0\quad \implies y^T\left(x^TXx\right)y \ge y^T\left(R^{-1}\right)^Txx^TR^{-1}y$$
So $$\left(x^TXx\right)I \succeq \left(R^{-1}\right)^Txx^TR^{-1} = \left(\left(R^{-1}\right)^Tx\right)\left(\left(R^{-1}\right)^Tx\right)^T$$ So $$x^TXx \ge \left(\left(R^{-1}\right)^Tx\right)^T\left(\left(R^{-1}\right)^Tx\right) = x^TR^{-1}\left(R^{-1}\right)^Tx = x^T\left(R^TR\right)^{-1}x = x^{T}S^{-1}x$$
So $$X\succeq S^{-1} \implies RXR^T \succeq R^TS^{-1}R = I \implies \text{Tr}(XS) = \text{Tr}(XR^TR) = \text{Tr}(RXR^T) \ge \text{Tr}(I) = n$$
Let $$ Z = \begin{pmatrix} A & B \\ B^T & C \end{pmatrix}. $$ The Schur complement characterization of block PSD matrices says that $$ Z \geq 0 \iff A \geq 0 \quad \text{and} \quad C \geq B^T A^{-1} B \quad \text{and} \quad (I-AA^{-1}) B = 0 $$ and $$ Z \geq 0 \iff C \geq 0 \quad \text{and} \quad A \geq B C^{-1} B^T \quad \text{and} \quad (I-CC^{-1}) B^T = 0\, $$ where $A^{-1}$ denotes the generalized inverse if $A$ is not invertible.
In the setting of your question the $(I-AA^{-1}) B = 0$, $(I-CC^{-1}) B^T = 0$ conditions imply that $X$ and $S$ are invertible and so $X>0$ and $S>0$, i.e., $X$ and $S$ are both positive definite. Fixing $X$ and optimizing first over $S$, the condition $C \geq B^T A^{-1} B$ tells us that $S\geq X^{-1}$ and so $$ \mathrm{Tr}[XS] = \mathrm{Tr}[X^{1/2} S X^{1/2}] \geq \mathrm{Tr}[X^{1/2}X^{-1}X^{1/2}] = n. $$ Thus for any fixed $X$ the objective value is lower bounded by $n$ (and is achieved by $S = X^{-1}$) and so completing the optimization by optimizing over $X$ we also find $n$.