5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It seems like the argument you want to make would be something like "this optimization problem looks like optimizing a Rayleigh quotient, which is known to be equivalent to solving an EVP". That said, the optimization problem you're posing does not quite look like an EVP, because it is not quite a Rayleigh quotient: it maximizes the sum of inner products squared, not a single inner product. $\endgroup$ – Geoff Oxberry Feb 11 '14 at 4:30
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Agreed. I don't see the scale-invariance property either; the sum of squares throws off everything. $\endgroup$ – Geoff Oxberry Feb 13 '14 at 9:43
  • 1
    $\begingroup$ You are right. I agree. Having the square in the denominators makes it not possible to add the constraint $y^Ty= 1$ or $\|y\|_{\mathcal{B}} = 1$. $\endgroup$ – sebas Feb 13 '14 at 10:18
  • 1
    $\begingroup$ Your reasoning is correct but only for positive-(semi)definite matrices A. If you consider $A = -I$, then it can have better solutions than 0. $\endgroup$ – Artem Sobolev Feb 14 '14 at 6:02
  • $\begingroup$ I assume it is psd since the original question involves a Cholesky factorization $A = LL^T$. Either way, if A could be negative definite, the arguments apply, but now you simply let $\alpha$ tend to zero instead. $\endgroup$ – Johan Löfberg Feb 14 '14 at 7:16
  • $\begingroup$ ... and $x_0$ be an eigenvector associated with a negative eigenvalue of $A$ $\endgroup$ – Johan Löfberg Feb 14 '14 at 7:23
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I'd think you'd need to modify power iteration a bit to work here. In the standard Euclidean norm case, iterates converge to the eigenvalue of maximum magnitude and its eigenvector. (Assume a dimension 1 eigenspace.) Assuming that $A$ is positive-definite (not stated in the OP), obtaining the minimum magnitude eigenvalue should suffice, in which case inverse power iteration would work. I don't know if all of the theory carries over with a change of norm. $\endgroup$ – Geoff Oxberry Feb 12 '14 at 3:06

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.