Is there guaranteed global solver for such an eigenvalue problem?

Question

The original nonlinear optimization problem I have is as follows:

For constant symmetric matrices $A=A^T, B_i=B_i^T(\forall i\in\mathbb{N}) \in \mathbb{R}^{n\times n}, \text{rank}(A)=n,$ $$\arg\min\limits_{x\in\mathbb{R}^n}\dfrac{x^TAx}{\sum\limits_{i=1}^{m}\left(x^TB_ix\right)^2}$$

Someone said this problem can be converted into an eigenvalue problem by Cholesky factorizing $A=LL^T, $ and substituting $y=L^Tx, x=L^{-T}y, Q_i=L^{-1}B_iL^{-T}$, then it is equivalent to:

$$\arg\max\limits_{\left\|y\right\|_2=1}\sum\limits_{i=1}^{m}\left(y^TQ_iy\right)^2=\arg\max\limits_{\|y\|_2=1}y^T\left(\sum\limits_{i}^m(Q_iyy^TQ_i)\right)y$$

So is it strictly or only approximately an eigenvalues problem (EVP)?

If it is an EVP, is there any guaranteed global solver in polynomial time for such problem?

Answer 1

For generic data the optimal value (in the limit) is zero, which is achieved by any vector with arbitrarily large elements. Just pick a random vector $x_0$ and use $x=\alpha x_0$ where $\alpha$ tends to $\infty$. Am I missing something?

The eigenvalue discussion you have is not correct (there is no reason that you should be allowed to add the constraint $y^Ty=1$ as you do, it seems to be blindly done by mimicking what is done when you have a ratio of two quadratics, of which one is $y^Ty$, and the objective thus is homogenous and unaffected by scaling $y$)

Answer 2

You can look at your problem in a different way. Look at the definition of norm , and then you can define your norm as:

$ \| x \|_{\mathcal{B}} = \sqrt{\sum_i \| x \|_{B_i}^2} = \sqrt{\sum_i \left( x^T,B_ix \right)^2} $

where $\mathcal{B} = \{B_i\}_i$ is the set of matrices $B_i$ that you have. You can do it if your matrices $B_i$ are definite positive, or semidefinite positives and at least one of the definite positive. In other case you are not sure that you can define the norm (the same happens for your matrix $A$). Because they are symmetric and rank complete, I think it is enough.

Then you can rewrite your problem as

$$ \arg \min_{x\in \mathbb{R}} \frac{x^T A x }{\sum_i \left( x^T,B_ix \right)^2} = \arg \min_{\|y\|_{\mathcal{B}}=1} y^T A y $$

where you have used that

$$ y = \frac{x}{\sqrt{\sum_i \left( x^T,B_ix \right)^2}} . $$

It is strictly an eigenvalue problem. I am not sure about if the eigenvalues for the matrix A are always the same whithout taking into account the norm that you use to define the problem. I dont think so. Anyway, you can use the power iteration method, and define yourself the norm as in the explanation to normalize the eigenvector. It should work.

EDIT:

I think that it will work. You start with a initial guess $y_0$. Then you iterates, solving the systems. At iteration $i$ you do

$$\hat{y} = A^{-1}y_i $$ $$\lambda_i = \|\hat{y}\|_{\mathcal{B}}$$ $$y_{i+1} = \frac{y_i}{\lambda_i}$$ $$\varepsilon = \left\|\frac{\lambda_{i}-\lambda_{i-1}}{\lambda_{i}}\right\|$$

until $\varepsilon$ is small enough. Once you converge, your eigenpair $(\lambda,y)$ is the one with minimum eigenvector satisfying $$A y = \lambda y$$ for a vector $y$ satisfying $$\|y\|_{\mathcal{B}} = 1$$

It is the same as $$\lambda = y^T A y $$

EDIT2:

Sorry, the previous is wrong as @Johan said in his answer, because the different exponent of $x$ in the numerator and the denominator. The answer would be valid if the problem is

$$ \arg \min_{x\in \mathbb{R}} \frac{x^T A x }{\sum_i \left( x^T,B_ix \right)} $$

where we dont have the square in the denominator. Then defining the norm as

$ \| x \|_{\mathcal{B}} = \sqrt{\sum_i \| x \|_{B_i}} = \sqrt{\sum_i \left( x^T,B_ix \right)} $

the power iteration can be applied. For the original problem this not valid.