[Math] Maximize the largest eigenvalue of a Hermitian matrix constrained by quadratic polynomials

eigenvalues-eigenvectorsoptimizationquadratic-forms

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

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

Related Question