# maximize the eigenvalue of a symmetric matrix

• May 31st 2009, 02:53 AM
Min.Lu
maximize the eigenvalue of a symmetric matrix
A Coarse Idea

We meet with an integer optimizing problem, which is defined as follows:

$y^{*}= \textrm{argmax}_{\begin{subarray}{c}{y \in \mathcal{Y}}\end{subarray}}\quad \frac{y^TX^T\left(\sum_{k=1}^{N}{b_kw_k^{\phantom{ k}T}}\right)Xy}{\sqrt{y^TX^TXy}}$

Where $\mathcal{Y}$ denotes $\displaystyle n(n-1)/2$ dimensional column parameter vector, each entry taking value from $\left\{{-1,1}\right\}$. $y^{*}$ represents the optimal solution. $b_i, w_i$ denote $m$ dimensional column vector, whose values are known. The matrix $X \in \mathcal{R}^{m \times n(n-1)/2}$ is defined on $m$ dimensional column vectors $x_{1},x_{2} \ldots x_{n}$, where each column vector is definitively. The columns of $X$ are calculated by substraction of every two column vector $x_{i}, x_{j} \textrm{ when } i. It is listed as follows:

$X =\left[\begin{array}{cccccccc}
|&\ldots&|&|&\dots&|&\ldots&|\\ x_{1}-x_{2}&\ldots&x_{1}-x_{n}&x_{2}-x_{3}&\dots&x_{2}-x_{n}&\ldots&x_{n-1}-x_{n}\\ |&\ldots&|&|&\dots&|&\ldots&|\\ \end{array}\right]$

The Goal
Our goal is to build an algorithm, which can solve the optimization problem in polynomial order time with $m$, $n$ and $N$. What's happiest, you can yield an analytical solution to the optimization problem.