I am looking for a method to maximize under $\mathbf{y}$ the largest eigenvalue of the following Hermitian matrix
\begin{equation}
S = \left [ \begin{array}{ccc}
\mathbf{y}^{H}S_{11}\mathbf{y} & \ldots & \mathbf{y}^{H}S_{1n}\mathbf{y}\\
\vdots & \ddots & \vdots\\
\mathbf{y}^{H}S_{n1}\mathbf{y} & \ldots & \mathbf{y}^{H}S_{nn}\mathbf{y}\\
\end{array} \right],
\end{equation} for $\|\mathbf{y}\|_{2} = 1$. All matrices $S_{ij}, 1 \leq i,j \leq n$ are Hermitian and $S_{ij} = S_{ji}$.
I just need some hints (papers, books, strategies, etc) to treat this problem. Thanks in advance!
Best Answer
As noticed in the comments, your optimization problem can be formulated as $${\rm max}_{\mathbf{x},\mathbf{y}} \mathbf{x}^T S(\mathbf{y}) \mathbf{x} ~~~{\rm s.t.} \|\mathbf{y}\|_{2} = 1,\|\mathbf{x}\|_{2} = 1,$$ where $$ S(\mathbf{y})= S = \left [ \begin{array}{ccc} \mathbf{y}^{H}S_{11}\mathbf{y} & \ldots & \mathbf{y}^{H}S_{1n}\mathbf{y}\\ \vdots & \ddots & \vdots\\ \mathbf{y}^{H}S_{n1}\mathbf{y} & \ldots & \mathbf{y}^{H}S_{nn}\mathbf{y}\\ \end{array} \right].$$
If we decouple the optimization of $\mathbf{x}$ and $\mathbf{y},$ it is easy to derive an iterative algorithm: Let $\mathcal{P}\{M\}$ denote the eigenvector associated with the largest eigenvalue $\lambda_{\rm max}\{M\}$ of $M$.
Then, an iterative algorithm would be
This algorithm has the useful property that the value $ \mathbf{x}_k^T S(\mathbf{y}_k) \mathbf{x}_k$ increases (or remains at least the same) in every iteration.
$Proof:$ From the definition, it is clear that $ \mathbf{x}^T S(\mathbf{y}) \mathbf{x} = \mathbf{y}^T S(\mathbf{x}) \mathbf{y}$.
Let us now consider $\mathbf{x}_{k-1}^T S(\mathbf{y}_{k-1}) \mathbf{x}_{k-1} = \mathbf{y}_{k-1}^T S(\mathbf{x}_{k-1}) \mathbf{y}_{k-1}.$ We choose $\mathbf{y}_{k} = \mathcal{P}\{ S(\mathbf{x}_{k-1}) \}$ (of course with $\lVert\mathbf{y}_{k} \rVert =1$) and have $\mathbf{y}_{k}^T S(\mathbf{x}_{k-1}) \mathbf{y}_{k} = \lambda_{\rm max}\{S(\mathbf{x}_{k-1}) \} $ and, consequently $\mathbf{y}_{k}^T S(\mathbf{x}_{k-1}) \mathbf{y}_{k} \geq \mathbf{y}_{}^T S(\mathbf{x}_{k-1}) \mathbf{y}_{} $ for all $\mathbf{y}_{}$ with unit norm. In particular, we have $\mathbf{x}_{k-1}^T S(\mathbf{y}_{k}) \mathbf{x}_{k-1} = \mathbf{y}_{k}^T S(\mathbf{x}_{k-1}) \mathbf{y}_{k} \geq \mathbf{y}_{k-1}^T S(\mathbf{x}_{k-1}) \mathbf{y}_{k-1} = \mathbf{x}_{k-1}^T S(\mathbf{y}_{k-1}) \mathbf{x}_{k-1}. $
In analogues, we can show that $\mathbf{x}_{k-1}^T S(\mathbf{y}_{k}) \mathbf{x}_{k-1} \leq \mathbf{x}_{k}^T S(\mathbf{y}_{k}) \mathbf{x}_{k}$ holds true as $\mathbf{x}_{k} = \mathcal{P}\{ S(\mathbf{y}_{k}) \}$ .
Finally, we conclude $\mathbf{x}_{k-1}^T S(\mathbf{y}_{k-1}) \mathbf{x}_{k-1} \leq \mathbf{x}_{k-1}^T S(\mathbf{y}_{k}) \mathbf{x}_{k-1} \leq \mathbf{x}_{k}^T S(\mathbf{y}_{k}) \mathbf{x}_{k}$.
Even though this algorithm computes a sequence of vectors that lead to monotonically increasing const function of the optimization probelm, it is unlikly that the algorithm finds the global optimum.