# Maximize the largest eigenvalue of a Hermitian matrix constrained by quadratic polynomials

I am looking for a method to maximize under $\mathbf{y}$ the largest eigenvalue of the following Hermitian matrix

$$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],$$ 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!

• Could you tell us sth about the matrices $S_{ij}$? – The Pheromone Kid Apr 13 '15 at 9:45
• So, what are our variables? The vector $\mathbf y$ or the matrices $S_{ij}$? – Kitegi Apr 13 '15 at 9:48
• Well this is bounded by the largest eigenvalue of the $n^2\times n^2$ matrix $\left[\matrix{S_{11} & \cdots & S_{1n}\\ \vdots & \ddots & \vdots\\ S_{n1} & \cdots & S_{nn}}\right]$. – RTJ Apr 13 '15 at 10:07
• Have you tried using $\rho (S)= ||S||_2$? Since $S$ is symmetric. – Kitegi Apr 13 '15 at 10:12
• @Farnight, how this could help me? – Alex Silva Apr 13 '15 at 10:14

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$.

• It is easy to see that, for fix $\mathbf{y},$ the solution to the optimization problem is given by $\mathbf{x}=\mathcal{P}\{ S(\mathbf{y})\}$.
• Also, for fix $\mathbf{x},$ the solution to the optimization problem is given by $\mathbf{y}=\mathcal{P}\{ S(\mathbf{x})\}$, where $S(\mathbf{x})$ is defined as $$S(\mathbf{x}) = \sum_{i=1,j=i}^n \mathbf{x}_i\mathbf{x}_j S_{i,j}.$$

Then, an iterative algorithm would be

• Create random $\mathbf{x}_{0}$, with $\lVert \mathbf{x}_{0} \rVert = 1$.
• For iteration index $k=1,2...$ do
1. Compute $S(\mathbf{x}_{k-1})$ and $\mathbf{y}_k=\mathcal{P}\{ S(\mathbf{x}_{k-1})\}$.
2. Compute $S(\mathbf{y}_{k})$ and $\mathbf{x}_k=\mathcal{P}\{ S(\mathbf{y}_{k})\}$.

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.

• Adrian, thanks for the answer, but how do you know that the quantity $\mathbf{x}_{k}^{T}S(\mathbf{y}_{k})\mathbf{x}_{k}$ does not decrease in some iteration? – Alex Silva Apr 20 '15 at 12:52
• Actually, both in step 1) and 2) the function value increases. As we always select the principle eigenvector (and therefore the optimum solution) we have the chain $\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}$. – The Pheromone Kid Apr 20 '15 at 13:28
• I inserted a short proof in my original post, please let me know if things are clearer now. – The Pheromone Kid Apr 21 '15 at 10:39
• Adrian, before your edition, I got the proof by myself. Thanks anyway!+1 – Alex Silva Apr 21 '15 at 11:55
• Anyway good that posted your concerns, I think the statement in my post is now easier to believe. – The Pheromone Kid Apr 21 '15 at 12:47