I'm trying to prove that for the optimization problem $$\max \{\sum_{i,j=1}^n A_{ij}<x_i,y_j> \mid x_1,\dots x_n,y_1,\dots y_n\in S^{2n-1}\}$$ that if $A$ is PSD, then there exists an optimal solution where $x_i = y_i \forall i\in \{1,...n\}$.
what I have figured out that I feel is going somewhere but I havent shown:
- by cauchy schwarz, you have $-1 \leq <x_i,y_j> \leq 1 \quad \forall i,j$
- you can split $\sum_{i,j=1}^n A_{ij}<x_i,y_j> = \sum_{i=1}^n A_{ii}<x_i,y_i> + \frac{1}{2}\sum_{i=1}^n\sum_{j\neq i} A_{ij} (<x_i,y_j>+<x_j,y_i>)$ using the fact that $A$ is symmetric as well.
but i feel like i am forgetting a key feature of positive semidefiniteness that will be the solution of a lifetime.
hopefully someone can help me, hints are also very much welcome! cheers and stay healthy!
last edit: $S^{2n-1} = \{x\in \mathbb{R}^{2n} \mid \|x\|=1\}$
$$ \max \{\sum_{i,j=1}^n A_{ij}<x_i,y_j> \mid x_1,\dots x_n,y_1,\dots y_n\in S^{n-1}\} $$ can be rewritten as $$ \max \left\{ (x_1^H,\dots,x_n^H)(A\otimes I)\left(\begin{array}c y_1\\ \vdots\\ y_n\end{array}\right) \mid x_1,\dots x_n,y_1,\dots y_n\in S^{n-1}\right\} $$ The matrix $A\otimes I$ is SPD, so for any couples of vectors $v,w$ we have $$ (v-w)^H (A\otimes I) (v-w)\ge 0 \implies \frac{v^H(A\otimes I)v + w^H(A\otimes I)w}2 \ge v^HAw $$ so $v^H(A\otimes I)w$ is necessarily less or equal than $v^H(A\otimes I)v$ or $w^H(A\otimes I)w$. As a consequence, if the maximum is $v^H(A\otimes I)w$, it is equal to both $v^H(A\otimes I)v$ and $w^H(A\otimes I)w$.