Minimización de Trace(XS) sujeto a [X,I;I,S]>=0

Question

Tengo el siguiente problema de minización de rastros

$$ \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 $$ Aquí $I$ denota la matriz de identidad de $\mathbb{R}^{n\times n}$ .

Parece que el valor mínimo del problema es $n$ pero no puedo probarlo. Se agradece cualquier ayuda.

Answer 1

Dejemos que $(X,S)$ sea una solución factible,

Voy a empezar por demostrar que $S$ es estrictamente positivo, de hecho para $u\in mathbb R^n $$ u^TXu + 2t \\N izquierda(u^Tu\ derecha) + t^2u^TSu = \begin{bmatrix} u^T & tu^T \end{bmatrix}\begin{bmatrix} X & I \N y S\Nend{bmatrix} \begin{bmatrix}u \ tu\end{bmatrix} $$

Así que $$ u^TXu u^TSu \ge \left(u^Tu\right)^2 $$

Así que $S$ es estrictamente positivo.

Podemos escribir $S = R^TR$ (ya que es una matriz definida). Para $(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 $$

Así que al tomar $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$$

Así que $$\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$$ Así que $$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$$

Así que $$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$$

Answer 2

Dejemos que $$ Z = \begin{pmatrix} A & B \\ B^T & C \end{pmatrix}. $$ El Caracterización del complemento de Schur de las matrices PSD en bloque dice que $$ 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 $$ y $$ 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\, $$ donde $A^{-1}$ denota la inversa generalizada si $A$ no es invertible.

En el marco de su pregunta, el $(I-AA^{-1}) B = 0$ , $(I-CC^{-1}) B^T = 0$ implica que $X$ y $S$ son invertibles y por tanto $X>0$ y $S>0$ es decir, $X$ y $S$ son ambas positivas definidas. Fijando $X$ y optimizando primero sobre $S$ la condición $C \geq B^T A^{-1} B$ nos dice que $S\geq X^{-1}$ y así $$ \mathrm{Tr}[XS] = \mathrm{Tr}[X^{1/2} S X^{1/2}] \geq \mathrm{Tr}[X^{1/2}X^{-1}X^{1/2}] = n. $$ Por lo tanto, para cualquier $X$ el valor objetivo está acotado por $n$ (y se consigue mediante $S = X^{-1}$ ) y así completar la optimización optimizando sobre $X$ también encontramos $n$ .