How to solve this optimization with the orthogonal constraint?

Question

Problem

Supposing that $A$ is a symmetric real matrix and $\{\mathbf{w}\_i\}_{i=1}^n$ is any orthogonal basis on $\mathbb{R}^n$ such that $W^\top W=WW^\top=\mathbf{I}_n$ where $W=\left[\mathbf{w}_1\;\mathbf{w}_2\;\ldots\;\mathbf{w}_n\right]$, what is the maximum of $\sum\_{i=1}^n{\left(\mathbf{w}\_i^\top A\mathbf{w}_i\right)^2}$?

To be concise, we can reformulate it as the following optimization problem: \begin{equation} \begin{split} \max_W&S(W)=\sum\_{i=1}^n{\left(\mathbf{w}\_i^\top A\mathbf{w}_i\right)^2}\\\ \mathrm{s.t.}\\,&W^\top W=WW^\top=\mathbf{I}\_n, \end{split} \end{equation} where $W=\left[\mathbf{w}_1\;\mathbf{w}_2\;\ldots\;\mathbf{w}_n\right]$.

With help of MATLAB, I found that the maximum of $S(W)$ is always obtained when $W=\bar{W}$ such that $\{\mathbf{w}\_i\}\_{i=1}^n$ are the eigenvectors of $A$ and the optimal value is $S(\bar{W})=\sum\_{i=1}^n{\lambda_i^2}=\|A\|_\mathrm{F}^2$. I had ever given a proof but recently I found it was wrong. However, I think the conclusion should be correct. The constraint that $W$ is orthogonal makes the problem difficult.

Since it is obvious that the assumed optimal value $S(W)=\|A\|_\mathrm{F}^2$ is always obtained by choosing $W$ to be the eigenvectors of $A$, if we can prove that $S(W)\leq\|A\|\_\mathrm{F}^2$ for $\forall W$, the problem is solved. However, this seems to be also difficult.

Comments

Actually, the problem may be furthermore simplified as follows.

Assume the spectral decomposition of $A$ is $A=V\Lambda V^\top$ and let $\tilde{W}=V^\top W$ (or $\tilde{\mathbf{w}}_i=V^\top\mathbf{w}_i$), then we have $S(W)=\sum\_{i=1}^n{\left(\tilde{\mathbf{w}}_i^\top\Lambda\tilde{\mathbf{w}}_i\right)^2}$ where $\Lambda$ is a diagonal matrix contaning the eigenvalues of $A$.

Since $V$ is orthogonal, we can solve for $\tilde{W}$ instead of $W$. Then the problem turns to be \begin{equation} \begin{split} \max_\tilde{W}&S(\tilde{W}) =\sum\_{i=1}^n{\left(\tilde{\mathbf{w}}\_i^\top \Lambda\tilde{\mathbf{w}}_i\right)^2} =\sum\_{i=1}^n{\left(\sum\_j^n{\lambda_j\tilde{w}_{ij}^2}\right)^2}\\\ \mathrm{s.t.}\\,&\tilde{W}^\top\tilde{W}=\tilde{W}\tilde{W}^\top=\mathbf{I}\_n, \end{split} \end{equation} where $\Lambda$ is diagonal and $\tilde{\mathbf{w}}\_i=\left[\tilde{w}\_{i1}\;\tilde{w}\_{i2}\;\ldots\;\tilde{w}\_{in}\right]^\top$.

However, this problem seems to be also difficult to solve. Please help me to give some suggestions about this problem.

Thank you very much!

Answer 1

I am sorry to trouble you all and I found the answer to this question finally which is very simple.

Due to the orthogonality of $\tilde{W}$, it is straightforward that $\sum\_{i=1}^n{\tilde{w}\_{ij}^2}=1,\forall j$ and $\sum\_{j=1}^n{\tilde{w}\_{ij}^2}=1,\forall i$.

Then for $\forall i$, from the convexity of $f(x)=x^2$, we have \begin{equation*} \left(\sum\_{j=1}^n{\tilde{w}\_{ij}^2\lambda\_j}\right)^2\leq\sum\_{j=1}^n{\tilde{w}\_{ij}^2\lambda\_j^2}, \end{equation*} and thus \begin{equation*} S(\tilde{W}) =\sum\_{i=1}^n{\left(\sum\_{j=1}^n{\lambda_j\tilde{w}\_{ij}^2}\right)^2} \leq\sum\_{i=1}^n{\sum\_{j=1}^n{\tilde{w}\_{ij}^2\lambda\_j^2}} =\sum\_{j=1}^n{\sum\_{i=1}^n{\tilde{w}\_{ij}^2\lambda\_j^2}} =\sum\_{j=1}^n{\lambda\_j^2} =\|A\|\_\mathrm{F}^2 \end{equation*}

Since $\|A\|\_\mathrm{F}^2$ provides an upper bound for $S(\tilde{W})$ and this value is always obtainable by choosing $\left\{\mathrm{w}_i\right\}\_{i=1}^n$ as the eigenvectors of $A$, this is the maximum value.