Maximizar la traza de la ecuación matricial dadas dos restricciones

Question

Dejemos que $\mathbf{Q}$ sea una matriz de rotación y $\mathbf{A}$ y $\mathbf{B}$ sean dos matrices de valor real del mismo tamaño. Quiero maximizar la función $$ f(\mathbf{Q})=tr\;\mathbf{QA} \qquad \text{s.t.} \; \mathbf{Q}'\mathbf{Q} = \mathbf{I} \quad \text{and} \quad tr\; \mathbf{QB} \geq 0 $$

Si sólo se impone la restricción de ortogonalidad, la solución es $$ \mathbf{Q} = \mathbf{VU}' $$

(véase por ejemplo Cliff, 1966 ) con $\mathbf{U}$ y $\mathbf{V}$ de la descomposición del valor singular de $\mathbf{A} = \mathbf{U \Lambda V}'$ .

Pregunta : ¿Cómo puedo encontrar una solución que incluya también la segunda restricción, es decir $tr\; \mathbf{QB} \geq 0$ ¿a qué se debe su existencia?

Nota: No soy un matemático, así que por favor, sea verboso en su respuesta, para que tenga la oportunidad de seguirla :)

Literatura

Cliff, N. (1966). Rotación ortogonal a la congruencia. Psychometrika, 31(1), 33-42. http://doi.org/10.1007/BF02289455

Answer 1

El SVD de $A$ es $A=U\Lambda V^T$ . Si $\det(A)\not=0$ entonces la llamada solución $Q_0=VU^T$ es s.t. $\det(Q_0)=signum(\det(A))=\pm 1$ entonces asumo que $Q\in O(n)$ .

Dejemos que $C=U^TBV,R=V^TQU\in O(n)$ . Si $tr(Q_0B)=tr(C)\geq 0$ entonces la solución es $Q_0$ .

Supongamos que $tr(C)<0$ . Uno tiene $tr(QA)=tr(R\Lambda)$ el sup se alcanza cuando $tr(QB)=tr(VRU^TB)=tr(RC)=0$ (no exactamente; cf. EDIT 1. abajo).

Entonces queda por encontrar $\sup_{R\in O(n)}tr(R\Lambda)$ con la condición de que $tr(RC)=0$ .

EDIT 1. Supongamos que el sup de $g(R)=tr(R\Lambda)$ se alcanza en $R=R_1$ con $tr(R_1C)>0$ . Entonces $g(R_1)$ es un sup local libre de $g$ .

Caso 1. $R_1\in O^+(n)$ . Desde $O^+(n)$ es un conjunto conectado, $g(R_1)=g(I)=tr(\Lambda)$ . Si $\Lambda=diag(\lambda_1,\cdots,\lambda_k,0,\cdots,0)$ donde $\lambda_i>0$ entonces $R_1=diag(I_k,S)$ donde $S\in O^+(n-k)$ .

Caso 2. $R_1\in O^-(n)$ . Entonces $g(R_1)=g(J)$ donde $J=diag(u_1,\cdots,u_n)$ con $u_i=\pm 1$ .

Por desgracia, puede darse el caso 2. Por ejemplo, $\Lambda=diag(1,1,0,0,0),C=diag(-3,-3,-2,-2,-3)$ . Entonces el sup se alcanza en un único punto $R_1=diag(1,1,-1,-1,-1)$ con $tr(R_1C)=1$ .

EDIT 2. Respuesta a Mark. Estoy de acuerdo con el caso $tr(C)\geq 0$ y su punto A.

Sobre su punto B donde necesariamente $tr(R_1C)>0$ .

Caso 1: $R_1\in O^+(n)$ . Entonces, necesariamente $R_1=diag(I_k,S)$ y buscas $S$ s.t. $tr(R_1C)>0$ . Si $S$ existe, entonces $\max(g)=tr(\Lambda)$ , si no $R_1$ no existe.

Caso 2: $R_1\in O^-(n)$ . Entonces, necesariamente $(\star)$ $g(R_1)=max_k(g(J_k))$ donde $J_k$ es la matriz diagonal s.t. $(J_k)_{i,i}=1$ si $i\not= k$ y $(J_k)_{k,k}=-1$ . Usted busca $R_1$ satisfaciendo $(\star)$ y s.t. $tr(R_1C)>0$ ...

Finalmente, se elige "el" mejor candidato. Ten en cuenta que el punto A no es fácil de resolver.

EDITAR 3. Mark, no quiero escribir detalles; de hecho, utilizo los siguientes resultados (que no son obvios de probar):

1. Dejemos que $O\in O^+(n)$ . Existe una función continua $f:[0,1]\rightarrow O^+(n)$ s.t. $f(0)=O,f(1)=I$ y s.t., para cada $i$ la función $f_{i,i}$ es no decreciente.

Tras discutirlo con un colega, una afirmación correcta es:

2. Dejemos que $O\in O^-(n)$ . Existe una función continua $f:[0,1]\rightarrow O^-(n)$ s.t. $f(0)=O$ , $f(1)$ tiene espectro $\{1,\cdots,1,-1\}$ y s.t., para cada $i$ la función $f_{i,i}$ es no decreciente.

NB. Durante tal deformación, $tr(R\Lambda)$ es no decreciente.