4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Could you tell us sth about the matrices $S_{ij}$? $\endgroup$ – The Pheromone Kid Apr 13 '15 at 9:45
  • $\begingroup$ So, what are our variables? The vector $\mathbf y$ or the matrices $S_{ij}$? $\endgroup$ – Kitegi Apr 13 '15 at 9:48
  • $\begingroup$ 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]$. $\endgroup$ – RTJ Apr 13 '15 at 10:07
  • $\begingroup$ Have you tried using $\rho (S)= ||S||_2$? Since $S$ is symmetric. $\endgroup$ – Kitegi Apr 13 '15 at 10:12
  • $\begingroup$ @Farnight, how this could help me? $\endgroup$ – Alex Silva Apr 13 '15 at 10:14
4
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Alex Silva Apr 20 '15 at 12:52
  • $\begingroup$ 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} $. $\endgroup$ – The Pheromone Kid Apr 20 '15 at 13:28
  • $\begingroup$ I inserted a short proof in my original post, please let me know if things are clearer now. $\endgroup$ – The Pheromone Kid Apr 21 '15 at 10:39
  • $\begingroup$ Adrian, before your edition, I got the proof by myself. Thanks anyway!+1 $\endgroup$ – Alex Silva Apr 21 '15 at 11:55
  • $\begingroup$ Anyway good that posted your concerns, I think the statement in my post is now easier to believe. $\endgroup$ – The Pheromone Kid Apr 21 '15 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.